Computational hardness assumption とは

計算複雑性理論では、計算硬度仮定は、特定の問題を効率的に解決することができないという仮説である(効率的な場合、通常、「多項式時間」を意味する)。本質的にあらゆる有用な問題のために(無条件の)硬度をどのように証明するかは知られていない。その代わりに、コンピュータ科学者は、新しい問題または複雑な問題の硬度をよりよく理解されている問題についての計算上の硬度の仮定に正式に関連付けるための削減に頼っている。
計算上の硬さの仮定は、暗号において特に重要である。暗号化の主な目的は、証明可能なセキュリティで暗号化プリミティブを作成することです。場合によっては、暗号プロトコルに情報理論上のセキュリティがあることが判明している。ワンタイムパッドは一般的な例です。しかし、情報理論上のセキュリティは必ずしも達成できません。そのような場合には、暗号技術者は計算上のセキュリティに落ちる。おおまかに言えば、これは、これらのシステムがすべての敵対者が実際にいるように、敵対者が計算上制限されていると仮定して安全であることを意味します。
計算硬度の仮定は、アルゴリズム設計者を導くためにも有用である。簡単なアルゴリズムは、P≠NPのような十分に研究された計算硬度仮定を反論する可能性は低い。