Zero-Knowledge Proof Learning

241219 read "Chameleon-Hashes with Ephemeral Trapdoors And Applications to Invisible Sanitizable Signatures" encountered NIZKPoK, so learning about it

NIZKPoK#

Non-Interactive Zero-Knowledge Proof

Manifestation in the Paper#

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

Explanation#

The prover wants to prove that they know a certain value $x$ without revealing $x$ itself.

Fiat-Shamir Transformation (Simplified Non-Interactive Proof)#

Initialization: $g$ and $h$ are public parameters, $x$ is secret (known to the prover).
Generate proof: randomly choose a random value $r$, calculate the commitment $t=h*g^r$.
Calculate challenge: generate a challenge $c$ (usually generated through a hash function).
Calculate response: compute $z=r+c*x$.
Send proof: send the triple $(t,c,z)$.
Verification: the verifier checks if $g^z=t*h^c$ holds.

Experimental Code#

# This is hand-crafted, successfully reproduced in code
def gen_NIZK( g , x , p ):
    h = pow( g , x , p )
    r = random.randint( 1 , p )
    t = pow( g , r , p )
    c = SM3("A challenge")
    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

Complete Code

# This is written by gpto1, but based on elliptic curves
from ecdsa import SECP256k1, SigningKey, VerifyingKey
import hashlib

# Curve parameters
curve = SECP256k1
G = curve.generator  # Base point g
n = curve.order      # Order

# Private key x (randomly generated)
x_sk = SigningKey.generate(curve=curve)
x = x_sk.privkey.secret_multiplier  # Value of x
# Public key h = g^x
h_vk = x_sk.verifying_key
h = h_vk.pubkey.point

def nizkpok_prove(x):
    # Prover generates random number r
    r_sk = SigningKey.generate(curve=curve)
    r = r_sk.privkey.secret_multiplier
    # Calculate commitment t = g^r
    t = r * G
    # Calculate challenge 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
    # Calculate response 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
    # Calculate t' = g^s + (-h^e)
    sG = s * G
    eH = e_int * h
    # Get the negative of eH
    neg_eH = (n - 1) * eH
    # Calculate t' = sG + (-eH)
    t_prime = sG + neg_eH
    # Recalculate challenge 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
    # Verify if e equals e'
    return e_int == e_prime_int

# Generate proof
proof = nizkpok_prove(x)

# Verify proof
is_valid = nizkpok_verify(h, proof)
print("Is the proof valid:", is_valid)