Member-only story
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.
