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\))? For this, we 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\). It outlines zero-knowledge proof of log equality to prove Peggy's password (Chaum-Pedersen proof)
Proving your password with NIZK proofs of discrete-log equality (Chaum-Pedersen proof) |
Theory
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\))? For this, we 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\)
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 \pmod 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:
\( \begin{align} 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 \end{align} \)
The only modification we have to do here, is to take a hash of Peggy's password, and assign it to /(x/).
Code
Here is the code:
package main import ( "crypto/rand" "crypto/sha256" "fmt" "os" "github.com/coinbase/kryptology/pkg/core/curves" ) func main() { curve := curves.K256() G := curve.Point.Generator() x := curve.Scalar.Random(rand.Reader) M := G.Mul(x) m := "Hello" argCount := len(os.Args[1:]) if argCount > 0 { m = os.Args[1] } msg := []byte(m) h := sha256.New() h.Write(msg) x, _ = curve.Scalar.SetBytes(h.Sum(nil)) Y := G.Mul(x) Z := M.Mul(x) k := curve.Scalar.Random(rand.Reader) A := G.Mul(k) B := M.Mul(k) h = sha256.New() h.Write(G.ToAffineCompressed()) h.Write(Y.ToAffineCompressed()) h.Write(M.ToAffineCompressed()) h.Write(Z.ToAffineCompressed()) h.Write(A.ToAffineCompressed()) h.Write(B.ToAffineCompressed()) c, _ := curve.Scalar.SetBytes(h.Sum(nil)) // s=k-h*x % o s := c.Mul(x).Sub(k) s = s.Neg() sG := G.Mul(s) cY := Y.Mul(c) A_ := sG.Add(cY) sM := M.Mul(s) cZ := Z.Mul(c) B_ := sM.Add(cZ) h = sha256.New() h.Write(G.ToAffineCompressed()) h.Write(Y.ToAffineCompressed()) h.Write(M.ToAffineCompressed()) h.Write(Z.ToAffineCompressed()) h.Write(A_.ToAffineCompressed()) h.Write(B_.ToAffineCompressed()) c2, _ := curve.Scalar.SetBytes(h.Sum(nil)) fmt.Print("Peggy's secret:\n") fmt.Printf("Password= %s\n", m) fmt.Printf("x= %s\n", x.BigInt()) fmt.Print("\nPeggy sends these to Victor:") fmt.Printf("\nxG %x\n", Y.ToAffineCompressed()) fmt.Printf("xM %x\n", Z.ToAffineCompressed()) fmt.Print("\nPeggy Computes:") fmt.Printf("\nA %x\n", A.ToAffineCompressed()) fmt.Printf("B %x\n", B.ToAffineCompressed()) fmt.Print("\nPeggy sends ZKP (s,c):") fmt.Printf("\ns %x\n", s.Bytes()) fmt.Printf("c %x\n", c.Bytes()) fmt.Print("\nVictor computes:") fmt.Printf("\nA_ %x\n", A_.ToAffineCompressed()) fmt.Printf("B_ %x\n", B_.ToAffineCompressed()) fmt.Printf("c2=%x", c2.Bytes()) if c.Cmp(c2) == 0 { fmt.Printf("\n\nPeggy's password has been proven!") } }
A sample run is:
Peggy's secret: Password= qwerty123 x= 98906048149852693632835231527654104973356176512273370103007009863493285004213 Peggy sends these to Victor: xG 02298bddf5494ab4e8918c19ac157164fc21e08809de931e7d2594845146728eee xM 032b6b6b6583da86273d768db61ae66459a6865c715475f6afb9df2e9d5acc85f9 Peggy Computes: A 03f0299346a35e4066cccbca2e50efb0b89e09a1599ed3f6bcca58bb7bef543560 B 03da7e0f54804aafcbc8b4fcb5ef39cd5499cee701082244701dc727832d688370 Peggy sends ZKP (s,c): s 5bc95fe53cae88ad9ed1064195e9dea794791e99f0ede2ec94774f92af169675 c 4f2e719009d439b12b4f64c0c4361ba5a2cd282af9ed0feb215fd36f3bc3350e Victor computes: A_ 03f0299346a35e4066cccbca2e50efb0b89e09a1599ed3f6bcca58bb7bef543560 B_ 03da7e0f54804aafcbc8b4fcb5ef39cd5499cee701082244701dc727832d688370 c2=4f2e719009d439b12b4f64c0c4361ba5a2cd282af9ed0feb215fd36f3bc3350e Peggy's password has been proven!
References
[1] Chaum, David, and Torben Pryds Pedersen. "Wallet databases with observers." Annual international cryptology conference. Springer, Berlin, Heidelberg, 1992 [paper].