241219阅读《Chameleon-Hashes with Ephemeral Trapdoors And Applications to Invisible Sanitizable Signatures》遇到了NIZKPoK，故学习一下

NIZKPoK

Non-Interactive Zero-Knowledge Proof 非交互零知识证明

论文中的体现

解释

证明着想要证明自己知道某个值$x$，而不透露$x$本身

Fiat-Shamir变换（简化的非交互证明）

  1. 初始化：$g$和$h$是公开的参数，$x$是秘密（证明者知道它）
  2. 生成证明：随机选择一个随机值$r$，计算承诺值$t=h*g^r$
  3. 计算挑战：生成一个挑战$c$（通常通过哈希函数生成）
  4. 计算响应：计算 $z=r+c*x$
  5. 发送证明：发送三元组$(t,c,z)$
  6. 验证：验证者检查是否满足$g^z=t*h^c$

实验代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#这份是手搓的，放进代码复现成功
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

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#这份是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)