計算量的安全性を持つ暗号

暗号理論において、計算量的安全性（けいさんりょうてきあんぜんせい）とは、暗号解読に必要なアルゴリズムの計算量に着目した暗号の安全性に関する概念の一つである。

具体的には、ある暗号を解読するための計算量が多項式時間に収まらない場合、その暗号は計算量的に安全という。実際に製品に組み込まれている暗号では鍵長などのパラメータが固定されていて解読計算量は定数時間になっているが、パラメータ選択時に現状及び今後の計算機能力の見積りを行い、安全性を保ちたい期間内には解読可能にならないような値を設定する。

このような計算量的安全性は、安全性の十分条件を与える情報理論的安全性よりは弱い安全性であるが、必要条件を与えるに過ぎない統計量的安全性よりは強い安全性であり、一般に広く利用されている暗号の多くはこの安全性に依拠している。

概要

暗号の安全性について数理的分析を行ったのは、シャノンによる1949年の論文「秘匿系での通信理論」が始まりとされる。シャノンは、暗号が情報理論的な意味で無条件に安全であるためには「平文サイズ≦鍵サイズ」を満たすことが必要十分条件であることを示した。この条件を満たすワンタイムパッドは、情報理論的に安全であるので、どれだけの暗号文を集めても、無限大の計算能力を持ってしても、解読できない。しかし、平文と同じサイズの秘密鍵を事前に通信者間で共有する必要があり、情報理論的に安全な暗号を維持運用にするには多くの費用がかかる。このため、情報理論的に安全な暗号は特別な用途を除いてあまり広くは使用されない。

一方、計算量的安全性では、暗号の解読や署名の偽造などを計算問題として定式化し、これを解く最も効率のよいアルゴリズムの計算量をもって暗号の安全性の評価尺度とする。そして、暗号解読に必要な計算量が利用できる計算機の能力に比較して膨大であり、現実的時間では実行不可能である場合に計算量的に安全と考える。

計算機の能力は時間と共に向上するため（ムーアの法則）、新型のコンピュータが登場することによって利用可能な計算機能力は増加する。この計算機の計算能力の増大はある程度予測可能であるため、新たな暗号標準を採用する際には、計算機能力の増大に備えた十分なマージンを持たせ、所定期間内に暗号解読が現実化することのないような値を選択する。

このため、計算量的に安全な暗号は、計算時間を無限にすれば原理的には解読可能であり、前提とした利用可能な計算機とは異なる能力の計算機が開発された場合には安全性が失われる可能性はある。場合によっては、特定の暗号解読に特化したハードウェアが開発されることで安全性が激減することもある。

安全性の確認

ある計算問題の計算量の下界を与える一般な解法は未だなく、ある暗号方式がどのような解読方法についても安全であるということを証明するのは困難である（P≠NP予想を参照、計算問題の複雑性については計算複雑性理論#計算問題と計算量・複雑性を参照）。このため、暗号方式が計算量的安全性を備えていることを主張するためには、暗号を解読する問題をよく知られた困難だと考えられている計算問題に帰着させることで、安全性を示すことが行われる。根拠となる計算問題への帰着を証明することで示される安全性を、証明可能安全性という。

そのような根拠となる問題のクラスにNP困難があり、ナップサック問題など多くの問題が知られている。ナップサック問題を利用した暗号方式にMerkle-Hellmanナップサック暗号などがある。その他、公開鍵暗号では、素因数分解問題（RSA暗号、Rabin暗号）や離散対数問題（ElGamal暗号）、DH判定問題（Cramer-Shoup暗号）など、NP困難ではないが多項式時間の解法は存在しないと考えられている問題が利用されている。そして、既存の暗号について、できる限り少ない仮定でより強固な問題への帰着を与えること、あるいは帰着可能な新たな暗号を構成することが暗号研究の課題となっている。

計算量的に安全なパラメータ

2000年初頭においては、解読に要する計算量が 2^64 以下の場合には安全とは言えず、2^100 以上であれば当面の安全性を有するとされる。

暗号の危殆化

計算量的安全性は、大きく分けて2つの要因により低下する。

• 新たな解読手法が発見され、解読に必要な計算量が減少する場合
• 新型の計算機(パソコンからスパコンまで含む)が登場することで、解読に利用できる計算機能力が増大する場合

暗号の歴史は、暗号作成者が解読の手間が莫大で事実上解読は不可能（つまり計算量的に安全）だと考えて使用した暗号を、暗号解読者が数学的抜け道を発見することで解読した歴史でもある。計算量的安全性に加えて証明可能安全性を与えることで抜け道が残存する可能性を少なくすることができるが、サイドチャネル攻撃のように安全性に関する既存の前提を覆すような攻撃条件が見つかることもある。

20世紀末に実用化された電子式計算機で、大きな桁数の自然数の素因数分解を求めるには準指数時間という長い計算時間を要するが、量子コンピュータでは素因数分解を多項式時間で実行できる。したがって、量子コンピュータが実現されたならばRSA暗号などの安全性は失われると考えられている。

関連項目

• 計算量的識別不能
• 量子暗号
• 暗号理論