Top / 計算量的アプローチと数理的技法によるアプローチ

計算量的アプローチと数理的技法によるアプローチ

目次 †

宣伝 †

　当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

　暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

　興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

暗号の分類 †

　暗号の安全性について解説する前に簡単に暗号を分類しておく。

basic primitive †

• 暗号化
• 認証（署名）

暗号プロトコル †

• 電子投票
• 電子マネー

暗号の証明 †

　暗号スキームや暗号プロトコルの証明は2つのアプローチに大別できる。

1. 計算量的なアプローチ（computational approach）
2. 数理的技法によるアプローチ（formal method approach）

計算量的なアプローチ †

• PPT-TM（probabilistic polynomial-time turing machine）を敵のモデルとして捉えて、いかなるPPT-TMに対しても安全であることを示す。
• 暗号コミュニティでは広く受け入れられている。
• 証明が複雑で、証明を誤りやすい。実際に間違っている証明の論文もある。

　さらにこれは2つに分類できる。

アタックベースフォーミュレーション（attack-based formulation） †

• アタッカーとチャレンジャーによるどちらが勝つかという一種のゲームとして捉える。
• 例：公開鍵暗号系のIND-CCA、デジタル署名のEUF-CMA

シミュレーションベースフォーミュレーション（simulation-based formulation） †

• REALとIDEALを区別するというゲームとして捉える。
• 例：UCフレームワーク

数理的技法によるアプローチ †

• UCのハイブリッドモデルと親和性が高い。
• 対象となる暗号プロトコルを記号列で表現し、その記号列に対する論理的推論や書換規則などにより安全性を示す。よって、証明が明瞭で、自動化できる。

[補講]結果

• （Abadi-Rogaway 2000）数理的アプローチの健全性を示す。
• （Canetti-Herzog 2006）Dolev-Yao流の数理的アプローチにおいて、理想的公開鍵暗号機能。