計算量的安全性を持つ暗号
暗号の安全性について数理的分析を行ったのは、シャノンによる1949年の論文「秘匿系での通信理論」が始まりとされる。シャノンは、暗号が情報理論的な意味で無条件に安全であるためには「平文サイズ≦鍵サイズ」を満たすことが必要十分条件であることを示した。この条件を満たすワンタイムパッドは、情報理論的に安全であるので、どれだけの暗号文を集めても、無限大の計算能力をもってしても、解読できない。しかし、平文と同じサイズの秘密鍵を事前に通信者間で共有する必要があり、情報理論的に安全な暗号を維持運用にするには多くの費用がかかる。このため、情報理論的に安全な暗号は特別な用途を除いてあまり広くは使用されない。
一方、計算量的安全性では、暗号の解読や署名の偽造などを計算問題として定式化し、これを解く最も効率のよいアルゴリズムの計算量をもって暗号の安全性の評価尺度とする。そして、暗号解読に必要な計算量が利用できる計算機の能力に比較して膨大であり、現実的時間では実行不可能である場合に計算量的に安全と考える。
計算機の能力は時間と共に向上するため(ムーアの法則)、新型のコンピュータが登場することによって利用可能な計算機能力は増加する。この計算機の計算能力の増大はある程度予測可能であるため、新たな暗号標準を採用する際には、計算機能力の増大に備えた十分なマージンを持たせ、所定期間内に暗号解読が現実化することのないような値を選択する。
このため、計算量的に安全な暗号は、計算時間を無限にすれば原理的には解読可能であり、前提とした利用可能な計算機とは異なる能力の計算機が開発された場合には安全性が失われる可能性はある。場合によっては、特定の暗号解読に特化したハードウェアが開発されることで安全性が激減することもある。