証明可能安全性を持つ暗号

通常、安全性の形式定義は "攻撃者モデル" という形で攻撃条件と、ゴールを形式的に表現することでなされ（幾らかの仮定の下で）、暗号を解読する問題をよく研究されて誰もが困難と信じる問題(安全性の根拠となる問題)に帰着できることの証明を与えることでなされる。根拠となる問題は、公開鍵暗号の安全性証明では、素因数分解問題や離散対数問題などがよく使われる。

証明の際には、ランダムオラクルモデル（ROM）などの現実には true とは言えないモデルを仮定することもあるし、困難な問題と言っても真に困難であるかの証明は無いことから、安全性証明とは何を証明しているのか注意すべきである。それでも、経験的な安全性とは質の異なる安全性を提供できる点に大きな意味があると考えられている。

ブロック暗号において、証明可能安全性（しょうめいかのうあんぜんせい、provable security）とは、ある種の攻撃法に対する暗号の安全性を数学的証明によって保障する手法である。

MISTY1は差分解読法及び線形解読法に対して証明可能安全性を有するように設計された。

ただし、この証明可能安全性はほかの攻撃法に対する安全性を保証するものではない。 SNAKE暗号は差分解読法及び線形解読法に対して証明可能安全性を有するように設計されたが、補間攻撃法によって全数探索より少ない計算量で解読可能なことが知られている。

• 暗号理論
• 情報理論的安全性
• 計算量的安全性

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集