Non-interactive Zero-Knowledge Proof of Discrete Log Quality

I love zero-knowledge proofs (ZKPs), and I think we can build a new privacy-prespecting world where we do not have to give away personal…

Non-interactive Zero-Knowledge Proof of Discrete Log Equality

I love zero-knowledge proofs (ZKPs), and I think we can build a new privacy-respecting world where we do not have to give away personal information. Normally within the interactive mode, Victor (the verifier) sends Peggy (the prover) a challenge (c), and Peggy sends back a proof. This can be improved with a non-interactive form and where Peggy can generate her own challenge and proof. This is known as a Non-interactive Zero-knowledge Proof (NIZK).

So let’s look at an example of producing two public keys, and where Peggy can prove they both have the same private key. A use case of this, is where Peggy will digitally sign somewhere, and where the public keys cannot be linked, but where she can prove that she was the one that signed them. Let’s say we have two base points on an elliptic curve (G and M), and then have two random values (k and x). If we have Y=xG and Z=xM, can we prove that Y and Z use the same scalar value (x)? We can then use G,Y,M,Z within a Chaum-Pedersen proof [1] to provide a zero-knowledge proof that log_G(Y)==log_M(Z). This is defined as DLEQ(Z/M == Y/G) — discrete log equality. With this we can prove that the same private key has been used for xG and xM.

Let say Peggy (the prover) needs to prove that two public keys use the same private key (x) but with different base points:

Y=xG

Z=xM

The prover will generate a random value (k) and then commits two values:

A=kG

B=kM

With non-interactive proofs, the prover then creates the challenge of:

c=Hash(G,Y,M,Z,A,B)

And then calculates:

s=k−cx (mod n)

and where n is the order of the curve. The prover then sends:

(c,s)

The verifier (Victor) then computes:

c′=H3(G,Y,M,Z,A′,B′)

A′=sG+cY

B′=sM+cZ

If c==c’, the proof has been proven.

Code

Here is the code for secp256k1 [here]:

import random
import hashlib
from secp256k1 import curve,scalar_mult,point_add

# Can we prove
x = random.randint(0, curve.n-1)
k = random.randint(0, curve.n-1)
r = random.randint(0, curve.n-1)
G= curve.g

M = scalar_mult(r,G)
A = scalar_mult(k,G)
B = scalar_mult(k,M)
Y = scalar_mult(x,G)
Z = scalar_mult(x,M)

print (f"x={x}, k={k}\nG={G}\nM={M}\nA={A}\nB={B}\nY={Y}\nZ={Z}\n")

G_x,_ = G
M_x,_ = M
A_x,_ = A
B_x,y = B
Y_x,y = Y
Z_x,_ = Y

# G,Y=xG, M , Z=xM, A=kG, B=kM
c=hashlib.sha256(str(G_x+Y_x+M_x+Z_x+A_x+B_x).encode())

digest = c.hexdigest()
c = int(digest, 16)

s=(k-c*x) % curve.n

print (f"c={c}, s={s}\n\n")

A_ = point_add(scalar_mult(s,G), scalar_mult(c,Y))

B_ = point_add(scalar_mult(s,M), scalar_mult(c,Z))

A_x,y = A_
B_x,y = B_

c_=hashlib.sha256(str(G_x+Y_x+M_x+Z_x+A_x+B_x).encode())

digest = c_.hexdigest()
c_ = int(digest, 16)
print (f"c={c_}")

if (c==c_): print("\nProven!")
else: print("\nNot proven!")
print (f"\n\nA_x={A_x}, B_x={B_x}\n")

A sample run is [here]:

x=35416836453933982290692276802598715692905104517036468320404568776284340190568, k=61373966280138216830657815314248992751337679135921632607587699413140057084241
G=(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
M=(109313334810958477418321835497480696076356416408825979038916417641071785535510, 42436860500151098909615340702882320805111643294553141226977160459787210738143)
A=(26826796251558955079235317283165928536253935451929951990183532315705741952623, 53202342644011362078490686414790012377384041579381932109021711369293617190511)
B=(37944664236701417783091257402619603205531606235126016164345783936286432951278, 19113513177578213715672495528475763450271451179938795510108690299122769339603)
Y=(106019702204816351426185591575742138944700259248555020992462182754709470335838, 26181941002749499427020424114275285554323295122454952021326958976654928222676)
Z=(23511017161302932771891246196142291697198231493335006173532379876249399496914, 96295158920223023012699200915630000951625615202868968718354010341712645117480)

c=14636018495143715303382353400769555713839065472325893247770338859312295689520, s=52676127977070219726246270185135606392788025498048831023138207679810143799338

c=14636018495143715303382353400769555713839065472325893247770338859312295689520

Proven!

A_x=26826796251558955079235317283165928536253935451929951990183532315705741952623, B_x=37944664236701417783091257402619603205531606235126016164345783936286432951278

References

[1] Chaum, David, and Torben Pryds Pedersen. “Wallet databases with observers.” Annual international cryptology conference. Springer, Berlin, Heidelberg, 1992 [paper].