ZK-SNARKs 相関テストと仮説
要約
AliceからBobに$ aを送り、BobからAliceに$ \gamma * aを送る。
$ \mathbb Z_pに関してpの数が大きくなると$ \mathbb Z_pの中の要素をhとし$ \{0,\cdots,p-2\}の中のaから、$ g^a = h ({\rm mod}\ p)を探すのが困難になる。
KC Test
$ \alpha \in \mathbb{F^*p}を条件とし、$ Gの中の（$ a,b）かつ$ a,b \neq 0かつ$ b = \alpha * aを満たすものを$ \alphaペアと呼ぶ。
⚠$ \mathbb{F^*p}は$ \mathbb{Fp}の要素の中から0を除いたもの。
⚠$ \alpha * aとは、$ aに演算を$ \alpha回させたもの。$ a^\alphaのイメージか？
Bobがランダムに$ \alpha \in \mathbb{F^*p}と$ a \in Gを選択する
Bobが$ \alphaと$ aから$ b = \alpha*aを計算する
計算結果からBobはAliceに$ \alphaペアである$ a,bを送る（このペアを"Challnge"ペアと呼ぶ）
Aliceは同様に$ \alphaペアである$ a',b'を送り返す
BobはAliceの返答が$ \alphaペアであった場合のみ受け取る。$ \alphaペアであるかどうかは、Bobは$ \alphaを既知なので、$ b' = \alpha * a'を計算するだけで良い。
Aliceがいかにして$ \alphaペアを見つけるかに関して、もしAliceが$ \alphaを知っていた場合、Aliceは$ G内にある任意の$ a'
を選び、計算することで$ \alphaペアを見つけることができる。しかし、Aliceの知りうる情報は、$ a,b、つまり$ \alphaを知らない。
なので問題は$ \alphaなしでAliceはいかにして返答するか？ということになる。
返答方法としては以下があげられる。
Aliceは$ \gamma \in \mathbb{F_p^*}を任意で選び、$ (a',b') = (\gamma*a, \gamma*b)を計算して返す。
$ b' = \gamma*b = \gamma\alpha*a = \alpha(\gamma*a) = \alpha*a'なので$ a',b'は$ \alphaペア
この場合、$ \gammaが$ aと$ \alphaの比率となっている。
$ a' = \gamma*a
AliceはBobから$ a,bが送られてくることで$ \gammaを判別できるようになる。
この比率はThe Knowledge of Coefficient Assumption (KCA)と呼ばれる。