書記が数学やるだけ#890 公開鍵暗号の安全性
公開鍵暗号の理論に触れていく。
問題
説明
公開鍵暗号とは、暗号化と復号に異なる鍵を用い、暗号化用の鍵を公開できるようにした暗号方式である。共通鍵暗号においては、共通鍵の受け渡しの過程で盗聴されるリスクが存在し、共通鍵を秘匿して配送するにはコストのかかる方法を要した。こうした鍵配送の問題を解決したのが公開鍵暗号である。
公開鍵暗号を用いた通信手順の概略：
1. 通信を受ける者（受信者）は自分の公開鍵（暗号化のための鍵）p を全世界に公開する。
2. 受信者に対して暗号通信をする者（送信者）は、公開鍵 p を使ってメッセージを暗号化してから送信する。
3. 受信者は、公開鍵 p と対になる秘密鍵（復号のための鍵）s を密かにもっている。この s を使って受信内容を復号し、送信者からのメッセージを読む。
暗号理論における攻撃モデルとして，選択平文攻撃（CPA），選択暗号文攻撃（CCA），適応的選択暗号文攻撃（CCA2）などが挙げられる。この中でCCA2は最も強力な攻撃であり，これに対するCCA2安全性がしばしば要請される。
一方で解読モデルには，一方向性（OW），Semantic Security（SS），識別不可能性（IND），頑強性（NM）がある。CCA2の元ではINDとNMは等価であり，現在の暗号ではIND-CCA2安全を満たすことが求められる。
解答
共通鍵暗号では，各ペアのユーザが秘密鍵を共有する必要があることから，鍵の数は組合せで求まる：一方で公開鍵暗号では，各ユーザは公開鍵・秘密鍵のペアを1組持てばよい。
IND-CPA安全の定式化について，以下の様なゲームに対し攻撃者の優位性が無視できる関数であることを要求する。
OWは「復号困難性」を保証するだけ一方で，SSは「情報漏洩が無い」ことまで保証する。OWを満たすがSSを満たさない例として，通常のRSA暗号が挙げられる。これは暗号文から平文を直接計算するのは困難（OWは成り立つ）だが，しかし決定的暗号なので暗号文の比較により情報が得られることからSSは成り立たない。
本記事のもくじはこちら：
