NIZK (Non-interactive Zero Knowledge) Proofs of Discrete-log Equality

Chaum-Pedersen proof using Golang and Kryptology
Photo by Burst from Pexels: here

NIZK (Non-interactive Zero Knowledge) Proofs of Discrete-log Equality

Chaum-Pedersen proof using Golang and Kryptology

One of my highlights of 2022, will be the time that Torben Pryds Pedersen came to talk to our students. It was such a privilidge to meet the person who had created the Pederson Commitment, and who worked with David Chaum. And so, now is the time for David and Torben‘s work on privacy to furish, and build a more trusted and private digital work.

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=x.G and Z=x.M, can we prove that Y and Z use the same scalar value (x)?

For this, we then use G, Y, M and 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 x.G and x.M. We make it non-interactive, so that Victor does not have to challenge Peggy, but where Peggy can create her own challenge, and the associated proof.

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

Peggy will generator a random value (k) and then computes two points (A and B) based on the generator points used (G and M):

A=kG

B=kM

With non-interactive proofs, Peggy then creates a challenge (c) 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. As the proof, Peggy then sends the following to Victor:

(c,s)

The verifier (Victor) then computes:

A′=sG+cY

B′=sM+cZ

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

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

This works because:

A′+B′=sG+cY+sM+cZ
=(k−cx)G+cY+(k−cx)M+cZ
=kG+cxG+cY+kM−cxM+cZ
=kG−cY+cY+kM−cZ+cZ
=kG+kM=A+B

I have created some Golang code here:

A sample run is [here]:

x= 35941013729899155577183851063424067791539202373825121472640549793638704148314
xG 03b236c5629cd22500493ab48ac161b72fe7574be5efaa14acd856e74f483279f8
xM 0271059ddcb8bebffcf6292bf803d8efed0dd2f1fbd9a2da0c3ce2f6ca0cbf8718
A 02b7deff4d253f2e8716b1f4b3fca3bdf70fb5605092bf7e557918ddcce8a91ce3
B 033cecbdd73f448339715bb9cadeb577fae8f53e954aad484bad5fec2f2946558d
A_ 02b7deff4d253f2e8716b1f4b3fca3bdf70fb5605092bf7e557918ddcce8a91ce3
B_ 033cecbdd73f448339715bb9cadeb577fae8f53e954aad484bad5fec2f2946558d
A+B 02bfe5e827393f6bdba21aa094bf28110f9cb0a364b5e5017c0054dcade07f5b0c
A_+B_ 02bfe5e827393f6bdba21aa094bf28110f9cb0a364b5e5017c0054dcade07f5b0c
c=2c8184a38b5d514a99d7e25933d467f238ab27a9d654c57e0f3d2cf348380640
c2=2c8184a38b5d514a99d7e25933d467f238ab27a9d654c57e0f3d2cf348380640B_x=37944664236701417783091257402619603205531606235126016164345783936286432951278

You can try the method here:

https://asecuritysite.com/zero/logeq2

Conclusions

And there you go … a method fit for the 21st Century, and which moves away from our 20th Century approaches for privacy.

References

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