「P⊂NP」は成り立つ。直観的に「P≠NP」であることはわかるが、まだ証明はされていない。†NP-Pの問題は一般的に難問であり、暗号ではここの問題が使われる。数論的問題(問題を解く基本アルゴリズム:数体ふるい法)素因数分解問題→RSA暗号が作られる。Vector問題→MH暗号(Merkle-Hellman暗号)、NTRU暗号が作られる。多項式の零点問題(問題を解く基本アルゴリズム:ブッフバーガーアルゴリズム)→HFE暗号、持駒暗号が作られる。†1976年に、DiffieとHellmanは、暗号アルゴリズムの設計において計算的複雑性を適用することを示唆した。NP完全問題が暗号に関する有力な候補となりえるということを示したのである。いうのも、NP完全問題なら、既知のいかなる技法をもってしても、多項式的時間内に解けないからである。NP内の問題よりも計算上難しい問題は暗号には適さない。暗号および復号の変換時には高速、即ち多項式的時間内でなければならないからである。アドバーサリーが多項式的時間内に鍵を推測して解をチェックできることを意味する。既知の平文を暗号化して、比較チェックするなどがそうである。よって、多項式的時間の暗号アルゴリズムを破る解読作業はNP内になければならない。DiffieとHellmanは、NP完全問題が暗号法の用途に適するかどうかを検証する方法によって、暗号法がNP複雑性の理論から引き出せるのではないかと予測した。情報は、NP完全問題内でそれをコード化することによって暗号化される。その場合の方法は、暗号解読が問題を通常の方法で解くのに必要とするであろう方法である。復号鍵を使えば解を求める近道になるわけだ。した暗号を構築するために、秘密の落とし戸(trapdoor)情報が計算上固い問題に内挿される。したものの代表例として一方向性関数の逆関数がある。function)であるという。function)である。この追加の情報は秘密の復号鍵である。公開鍵暗号系は、こうした原理に基づいている。落とし戸ナップザック方式は、ナップザック問題に基づく。RSA暗号は、素でない数の因数分解に基づく。†トラップドアを持つ暗号の強度は、その暗号が基としている問題の計算上の複雑性に依存している。Shamirはそれに対して、3つの理由を挙げている。複雑性問題は、通常ひとつの問題の中の単一で隔離された事例を取り扱う。暗号解読者は通常解くべき問題に十分に関連したコレクションを多く持っている。同じ鍵で暗号化された何通かの暗号文である。ある問題の計算上の複雑性は、その最悪ケースあるいは平均的ケースにおける様子で測られる。暗号として有用でありうるには問題はほんどすべてのケースにおいて解きにくいものでなければならない。ある任意の難解な問題は必ずしも暗号システムに変換しえない。近道の解が落とし戸情報を使うことによってのみ得られるように、問題の中に落とし戸情報を挿入できねばならない。†[定理]Lempelあるブロックの暗号文に対応する平文が既知のとき、nビット鍵探索問題がNP完全であるようなブロック暗号に生ずる。十分な既知平文が与えられると、問題はn個の未知数を持つn個の1次方程式を解く問題になる。†Shamirは第2の難点を取り扱うための新しい複雑性手法を提案した。0≦r≦1であるような有理数rが与えられたとする。complexity)T(n,r)は、サイズnの問題事例の最も平易な割合rをとくのに要する時間を表す。例:T(n,0.5)は、メジアン複雑性を表す。サイズnの事例中少なくとも半分は、時間T(n,0.5)以内に解ける。[定理]与えられた整数が素数であるかどうかを決定する問題は、O(1)のメジアン複雑性を持つ。[証明]数の半分のうちは、因数として2を持つからであり、これは一定時間内に試しうる。†Brassardは、落とし戸付き一方向性関数の逆関数を求めるための解読作業がNP完全であることを証明するのは、おそらく不可能であることを示した。擬似乱数生成器(2806d)。