はじめに - 暗号理論教室

---

はじめに

暗号を安全というためには

• 暗号はなんらかの計算問題を用いる。
• 暗号の安全性は、用いる計算問題の困難さを根拠とする。

• しかし、「暗号を破ることが、本当に計算問題を解くこと以上に難しくなっている」かどうかは、多くの場合、微妙な問題となる。
• 実際、設計者の意図に反し、正面から計算問題を解くことなく、いわば脇道から暗号が解けてしまうことも少なくない。
• 「暗号を破ることが、本当に計算問題を解くこと以上に難しくなっている」ことには証明が必要である。

• そのような証明は、以下のようなステップを踏む：

1. 暗号Πと計算問題Σの関係を詳細に考察する。
2. 暗号Πを破ることのできる、なんらかの攻撃アルゴリズムAを仮定してみる。
3. 攻撃アルゴリズムAを（仮想の）部品として用いて、計算問題Σを解く新たなアルゴリズムBを設計する。
4. さらに、攻撃アルゴリズムAが暗号Πを破るなら、アルゴリズムBも計算問題Σをちゃんと解くことを確認する。

• このようにして、「暗号Πを破ることが計算問題Σを解くこと以上に難しい」ことが証明可能であるならば、
• 計算問題Σを解くことが難しいとの仮定のもと、暗号Πは安全であるといえる。

• ただし、このとき、暗号Πが無条件に安全であると言えているわけではないことに注意する。
• （計算的）暗号理論の多くの主張は、要素に還元されるよりも、関係に還元されることとなる。

上へ

---