安全性の確認
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/04/20 08:31 UTC 版)
「計算量的安全性を持つ暗号」の記事における「安全性の確認」の解説
ある計算問題の計算量の下界を与える一般な解法は未だなく、ある暗号方式がどのような解読方法についても安全であるということを証明するのは困難である（P≠NP予想を参照、計算問題の複雑性については計算複雑性理論#計算問題と計算量・複雑性を参照）。このため、暗号方式が計算量的安全性を備えていることを主張するためには、暗号を解読する問題をよく知られた困難だと考えられている計算問題に帰着させることで、安全性を示すことが行われる。根拠となる計算問題への帰着を証明することで示される安全性を、証明可能安全性という。 そのような根拠となる問題のクラスにNP困難があり、ナップサック問題など多くの問題が知られている。ナップサック問題を利用した暗号方式にMerkle-Hellmanナップサック暗号などがある。その他、公開鍵暗号では、素因数分解問題（RSA暗号、Rabin暗号）や離散対数問題（ElGamal暗号）、DH判定問題（Cramer-Shoup暗号）など、NP困難ではないが多項式時間の解法は存在しないと考えられている問題が利用されている。そして、既存の暗号について、できる限り少ない仮定でより強固な問題への帰着を与えること、あるいは帰着可能な新たな暗号を構成することが暗号研究の課題となっている。
※この「安全性の確認」の解説は、「計算量的安全性を持つ暗号」の解説の一部です。
「安全性の確認」を含む「計算量的安全性を持つ暗号」の記事については、「計算量的安全性を持つ暗号」の概要を参照ください。
ウィキペディア小見出し辞書の「安全性の確認」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 安全性の確認のページへのリンク
