【Python】ゼロ知識証明

ゼロ知識証明とは、証明者がその事実を提示するだけで、その事実の内容を隠すことができる証明方法
Zero-knowledge Proofとしてよく使われるのが、ハミルトングラフの知識を持っていることや秘密のパスワードを証明せず知っていることを示す。

xを知っていおり、 y = x^2 mod p を示す。

import random

p = 23
x = 5
y = pow(x, 2, p)

print(" y =", y)

def prover_step():
    r = random.randint(1, p - 1)
    a = pow(r, 2, p)
    return r, a

def verifier_challenge():
    return random.randint(0, 1)

def prover_response(r, c):
    if c == 0:
        return r
    else:
        return (r * x) % p

def verifier_check(a, z, c):
    if c == 0:
        return pow(z, 2, p) == a
    else:
        return pow(z, 2, p) == (a * y) % p

r, a = prover_step()
print("Prover: 提出 a=", a)

c = verifier_challenge()
print("Verifier: チャレンジ c=", c)

z = prover_response(r, c)
print("Prover: 応答 z =", z)

ok = verifier_check(a, z, c)
print("Verifier: 検証結果 =", ok)

$ python3 zkp.py
y = 2
Prover: 提出 a= 4
Verifier: チャレンジ c= 1
Prover: 応答 z = 10
Verifier: 検証結果 = True

—– 実際の計算
r = ?,
a = 4,
c = 1
z = 10
10 * 10 % 23 = 5 * 2 / 23

x の値を知らせずに、y = x^2 mod p　を証明している。証明の際には、c != 0 の時にのみyの値を利用する
zkpの概念は理解できたが、なぜこれが証明になるのかのロジックはよくわからない..