職場の先輩に社の近くの鯛めしの店に連れて行ってもらいました.
美味しい!美味しい!
意外と安かったので,後でまた行きます.(断言)
それはそうと今回はですね,おもしろそうな本を見つけたのでチラッと読んでみます.
Rosulek『The Joy of Cryptography』です.
この本は著者によるHPで無料公開されています.
演習1.2をやります.
問題文
Alice is using one-time pad and notices that when her key is the all-zeros string $k = 0^{λ}$, then $\mathrm{Enc}(k,m) = m$ and her message is sent in the clear! To avoid this problem, she decides to modify $\mathrm{KeyGen}$ to exclude the all-zeros key. She modifies $\mathrm{KeyGen}$ to choose a key uniformly from $\{ 0,1 \}^ λ \setminus \{ 0^ λ \}$, the set of all λ-bit strings except $0^ λ$. In this way, she guarantees that her plaintext is never sent in the clear.
Is it still true that the eavesdropper's ciphertext distribution is uniformly distributed on $\{ 0,1 \}^ λ$? Justify your answer.
Rosulek『The Joy of Cryptography』Ex1.2
問題の背景
One-time Pad という暗号の話が背景になっています.
One-time Pad(OTP)というのは,その名前の通り鍵を一回一回ランダムに生成して使い捨てる暗号です.
仕組みを説明しておきます.
まず平文 $m$ をバイナリコードで用意しておきます.
次に $m$ と同じ長さの $0,1$ 列 $k \leftarrow {0,1}^ λ$ を一様ランダムに選びます.$m$ と $λ$ のXOR $m \oplus λ$ を計算し,それを $c$ とします.
$c$ が,暗号化された文章です.
この暗号の特筆すべき特徴は,安全性が証明できるという点です.
$c$ は一様分布に従うので,とくに平文 $m$ にまったく依存しません.したがって攻撃者は暗号文 $c$ から平文 $m$ に関する情報を何も得ることができないというわけです.
回答
$k$ がゼロにならないようにしたら,安全性はどうなるかという問題です.
よくわかっていないのですが,$k \neq 0$ という条件を課してしまうと,$c$ の分布が 一様分布でなくなり,$m$ 以外の値を等しい確率でとるようになります.つまり $c$ の分布が $m$ に依存するようになります.
したがって答えはNOです.
感想
数学のひとが書いた暗号理論の本は,いきなり公開鍵暗号の話から始まります.
しかしこの本は公開鍵暗号がゴールです.
丁寧に書いてありそうな予感がします.
特に,暗号の安全性をきっちり定義して証明するという話が書かれているのはよいです.