Photo by Charl Folscher on Unsplash

Non-interactive Zero-Knowledge Proof of Discrete Log Equality

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=kcx (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.nprint (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=14636018495143715303382353400769555713839065472325893247770338859312295689520Proven!
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].

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store