零知識證明學習

2024年12月19日#Crypto158

AI 翻譯

這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文

AI 生成的摘要

這篇文章介紹了非交互零知識證明（NIZKPoK）的基本概念及其在數位簽名中的應用。NIZKPoK允許證明者證明自己知道某個秘密值$x$而不透露該值。文中詳細描述了生成證明的過程，包括初始化參數、生成隨機數、計算承諾值、挑戰和響應，並提供了實驗代碼來實現這一過程。此外，文章還展示了基於椭圓曲線的NIZKPoK實現，並提供了生成和驗證證明的完整代碼。最後，驗證者可以檢查證明的有效性。

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)