Security事情

ゼロ知識対話証明とは　その２

次に数値例でやってみましょう。
Z = 16 と m = 77 とし、P は T = 18 を知っているとします。
Z = T^2 (mod m) = 18^2 mod 77 = 16

最初のラウンドで、R を 4、b = 1 とします。
Step1 P：さいころをふり、乱数 R = 4, X = 4^2 mod 77 = 16, X = 16 を V に送る。
Step2 V：コインを投げ、b = 1 を P に送る。
Step3 P：Y = T^b * R = 18*4 = 72 (mod 77) を V に送る。
Step4 P：Z^b * X = 16 * 9 = 25, Y^2 = 72^2 = 25 (mod 77)

次のラウンドでは、R を11、b を 0 とします。
Step1 P：さいころをふり、R = 11, X = 11^2 mod 77 = 44 を V に送る。
Step2 V：コインを投げ、b = 0を P に送る。
Step3 P：Y = T^b * R = 11 = 11 (mod 77) を V に送る。
Step4 V：Z^b * X = 44, Y^2 = 11 ^2 = 44 (mod 77)
...
以下、R と b を変化させながら k 回繰り返します。

上の数値例を参考に、ゼロ知識性を見てみましょう。
Step4で V が得る値は、乱数か、T に乱数を掛けたもののいずれかであり、T の値は V はわかりません。
ただし、R が毎回同じだった場合は b = 0 と b = 1 の2つの場合を送ることで、R を求めることができ、そこから T も求めることができます。
しかし R は P が決め、毎回違った数を出力するため、V は T を知ることはできません。

しかし、平方根を求める問題がそもそも簡単な問題であったら、この方法は意味がありません。
m を法とした平方根を計算する問題は、はたして困難な問題なのでしょうか?

まず、次のよく知られた事実があります。
(1) 大きな素数の積 n = p * q が与えられた時、n を素因数分解するのは非常に難しい。
(2) 整数 m と整数 y(<m) が与えられた時、y = x^2 mod m なる整数解 x が存在すれば、y は mod m で平方剰余であるという。x を mod m での y の平方根という。
(3) m が素数の時、平方剰余の判定や、平方根の求解は簡単である。
(4) m が合成数の時、m を素因数分解できれば任意の y の mod m での平方根を簡単に求めることができる。逆に任意の y に対する mod m での平方根が求まるならば、m を簡単に素因数分解できる。
(5) m を素因数分解できれば、任意の y に対し mod m での平方剰余性を簡単に判定できる。
ここで「簡単」というのは、多項式時間で計算できるアルゴリズムがあるということです。

この(1)から(5)から m の素因数分解の困難さと、任意の y について m を法とした平方根を求める問題とは困難さが同等であるということが分かります。
すなわち、このゼロ知識対話証明の安全性は、m の素因数分解と同じ程度に困難な問題であることに根拠を置いているといえます。
これはRSA暗号などと同じ数学的根拠があるということですので、まぁ安心といえるでしょう。
したがって、m としてはできるだけ大きな複数の素数の積を選択する必要があります。