零知識証明の学習

241219 読書《Chameleon-Hashes with Ephemeral Trapdoors And Applications to Invisible Sanitizable Signatures》で NIZKPoK に出会ったので、学んでみることにした

NIZKPoK#

非対話型ゼロ知識証明 Non-Interactive Zero-Knowledge Proof

論文での表現#

\begin{align} &Generate\ \pi\leftarrow NIZKPoK\{(x):h=g^x\}\\ &if\ \pi\ is\ not\ valid, return\perp \end{align}

説明#

証明者は自分がある値 $x$ を知っていることを証明したいが、$x$ 自体は明かさない

Fiat-Shamir 変換（簡略化された非対話証明）#

初期化：$g$ と $h$ は公開パラメータで、$x$ は秘密（証明者が知っている）
証明生成：ランダムに値 $r$ を選び、コミットメント値 $t=h*g^r$ を計算する
チャレンジ計算：チャレンジ $c$ を生成する（通常はハッシュ関数を使って生成）
応答計算：$z=r+c*x$ を計算する
証明送信：三つ組 $(t,c,z)$ を送信する
検証：検証者は $g^z=t*h^c$ が成り立つか確認する

実験コード#

#このコードは手作りで、コードを入れて再現成功
def gen_NIZK( g , x , p ):
    h = pow( g , x , p )
    r = random.randint( 1 , p )
    t = pow( g , r , p )
    c = SM3("チャレンジを一つ")
    z = r+c*x
    return (t,c,z),(g,p,h)

def verf_NIZK( pi ):
    ( t , c , z ) , ( g , p , h ) = pi
    if pow( g , z , p ) == t * pow( h , c , p ) % p:
        return True
    return False

完全なコード

#このコードはgpto1が書いたもので、楕円曲線に基づいている
from ecdsa import SECP256k1, SigningKey, VerifyingKey
import hashlib

# 曲線パラメータ
curve = SECP256k1
G = curve.generator  # 基点 g
n = curve.order      # 順序

# 秘密鍵 x（ランダム生成）
x_sk = SigningKey.generate(curve=curve)
x = x_sk.privkey.secret_multiplier  # x の値
# 公開鍵 h = g^x
h_vk = x_sk.verifying_key
h = h_vk.pubkey.point

def nizkpok_prove(x):
    # 証明者がランダム数 r を生成
    r_sk = SigningKey.generate(curve=curve)
    r = r_sk.privkey.secret_multiplier
    # コミットメント t = g^r を計算
    t = r * G
    # チャレンジ e = Hash(g || h || t) を計算
    e = hashlib.sha256()
    e.update(int(G.x()).to_bytes(32, 'big') + int(G.y()).to_bytes(32, 'big'))
    e.update(int(h.x()).to_bytes(32, 'big') + int(h.y()).to_bytes(32, 'big'))
    e.update(int(t.x()).to_bytes(32, 'big') + int(t.y()).to_bytes(32, 'big'))
    e_int = int(e.hexdigest(), 16) % n
    # 応答 s = r + e * x mod n を計算
    s = (r + e_int * x) % n
    return (e_int, s)

def nizkpok_verify(h, proof):
    e_int, s = proof
    # t' = g^s + (-h^e) を計算
    sG = s * G
    eH = e_int * h
    # eH の負元を取得
    neg_eH = (n - 1) * eH
    # t' = sG + (-eH) を計算
    t_prime = sG + neg_eH
    # チャレンジ e' = Hash(g || h || t') を再計算
    e_prime = hashlib.sha256()
    e_prime.update(int(G.x()).to_bytes(32, 'big') + int(G.y()).to_bytes(32, 'big'))
    e_prime.update(int(h.x()).to_bytes(32, 'big') + int(h.y()).to_bytes(32, 'big'))
    e_prime.update(int(t_prime.x()).to_bytes(32, 'big') + int(t_prime.y()).to_bytes(32, 'big'))
    e_prime_int = int(e_prime.hexdigest(), 16) % n
    # e が e' と等しいか検証
    return e_int == e_prime_int

# 証明を生成
proof = nizkpok_prove(x)

# 証明を検証
is_valid = nizkpok_verify(h, proof)
print("証明は有効ですか：", is_valid)