📂整数論

ゴールドワッサー-ミカリ確率的鍵暗号システムの証明

ビルドアップ

左から順に アリス、ボブ、イブとしよう。アリスとボブはメッセージを交換する当事者で、イブはメッセージに関心がある受動的な攻撃者だ。オレンジ色のボックスはアリスだけが知っている情報を、空色のボックスはボブだけが知っている情報を、黒色のボックスは公開された（イブも知っている）情報を表す。

アリスはボブから受け取るべきメッセージ$m \in \left\{ 0 , 1 \right\}$がある。$\displaystyle \left( {{ x } \over { y }} \right)$はヤコビ記号を意味する。

アルゴリズム ¹

キー設定: アリスは大きな素数 $p$、$q$ の積$N=pq$と$\displaystyle \left( {{ a } \over { p }} \right) = \left( {{ a } \over { q }} \right) = -1$を満たす$a$を選択して公開する。

---

暗号化: ボブがランダムな$1 < r < N$を選んで$c \equiv \begin{cases} r^2 &, m=0 \\ a r^2 &, m=1 \end{cases}$を計算して公開する。

---

復号化: アリスは$\displaystyle m = \begin{cases} 0 &, \left( {{ c } \over { p }} \right) = 1 \\ 1 &, \left( {{ c } \over { p }} \right) = -1 \end{cases}$を計算すれば良い。イブは現実的に$p$を知ることができないため$m$を知ることができない。

説明

ゴールドワッサー・ミカリ確率鍵暗号体系はシャフィ・ゴールドワッサー^{shafi Goldwasser}とシルビオ・ミカリ^{silvio Micali}によって開発された暗号体系で、この業績により2012年にチューリング賞を受賞した。

暗号体系が何であれ、平文の集合が小さいと暗号を解読するのではなく、直接暗号を作り出して比較することで侵入されうるが、たとえばメッセージが「攻撃」「防御」「撤退」程度だとすると、全て入れてみて暗号文を作り比較すると侵入される。

勿論これは極端な例で、平文が何か型をつかむ時の攻撃を防ぐ程度と考えればよい。しかし「その程度」で暗号体系は驚くほど強固になる。平文の集合は自然数と一対一対応が可能で、自然数は二進法で表現できるため、1ビットの平文$m \in \left\{ 0 , 1 \right\}$についての証明があれば十分だ。

名称の確率^{probabilistic}とは実際には数学で言う厳密な意味の確率を意味するわけではない。攻撃者の立場からは答えが高々$0$と$1$の二つのうちの一つであるため、$p$を知ろうと知るまいと大体$\displaystyle {{1} \over {2}}$の確率で答を当てることができる。しかし、$n$ビットの平文に対しては確率が$\displaystyle {{1} \over {2^n}}$に落ちる。攻撃者の立場からは当てることができないのではなく、当てても当たったかどうか分からないために確率という言葉が付いたのだ。だが、$N=pq$を計算するには素因数分解問題自体が簡単ではない。これでよい暗号体系になるのだ。

証明は驚くほどシンプルで、難しく複雑だからではなく、簡単で直接的だからである。整数論を勉強した人なら誰でもルジャンドル記号とガウスの二次相互法則に接したことがあるだろうが、そこからこんな実用的なアイデアが出てくるとは信じがたい。数学者という族が元々頭が良く、特に応用数学が特に独創的であるのは事実だが、これはまさに天才という賞賛が自然と出てくるような傑作である。

証明

復号化

アリスは$N$の素因数分解$N = pq$を知っているので、$\displaystyle \left( {{ c } \over { p }} \right)$を計算することができる。

---

ケース1. $m=0$

$$ \begin{align*} \displaystyle \left( {{ c } \over { p }} \right) =& \left( {{ r^2 } \over { p }} \right) \\ =& \left( {{ r } \over { p }} \right) \left( {{ r } \over { p }} \right) \\ =& 1 \end{align*} $$

---

ケース2. $m=1$

$$ \begin{align*} \displaystyle \left( {{ c } \over { p }} \right) =& \left( {{ a r^2 } \over { p }} \right) \\ =& \left( {{ a } \over { p }} \right) \left( {{ r } \over { p }} \right) \left( {{ r } \over { p }} \right) \\ =& \left( {{ a } \over { p }} \right) \\ =& -1 \end{align*} $$

■

暗号化

ケース1. $m=0$

$$ \begin{align*} \displaystyle \left( {{ c } \over { N }} \right) =& \left( {{ r^2 } \over { N }} \right) \\ =& \left( {{ r } \over { N }} \right) \left( {{ r } \over { N }} \right) \\ =& 1 \end{align*} $$

---

ケース2. $m=1$

$$ \begin{align*} \displaystyle \left( {{ c } \over { N }} \right) =& \left( {{ a r^2 } \over { N }} \right) \\ =& \left( {{ a } \over { N }} \right) \left( {{ r } \over { N }} \right) \left( {{ r } \over { N }} \right) \\ =& \left( {{ a } \over { N }} \right) \\ =& \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right) \\ =& (-1) \cdot (-1) \\ =& 1 \end{align*} $$

---

イブも$N$を知っているので$\displaystyle \left( {{ c } \over { N }} \right)$を計算することはできる。しかし、$m$が何であれ結果は常に$\displaystyle \left( {{ c } \over { N }} \right) = 1$なので、$m$が何か分からない。従って、素因数分解問題$N=pq$を解いて$\displaystyle \left( {{ c } \over { p }} \right)$を計算する必要がある。これは非常に難しいので、ボブはアリスにメッセージ$m$を安全に伝えることができる。

■