This page outlines a Schnorr NIZK (Non-interactive Zero Knowledge) discrete-log proof [1]. It uses the Fiat-Shamir transformation.Peggy first creates her secret (\(x\)), and then calculates \(xG\), and where \(G\) is a two random point on an elliptic curve. She sends this to Victor. To create a proof, Peggy generates a random value (\(v\)) and computes \(V=vG\). Next she creates a challenge (\(c\)) and which is a hash of \(G,V,kG,userID\). She then computes \(r= v - c.x\), and sends the proof of \((c,r,vG\). Victor can then prove that Peggy still knows \(x\). We also create a domain separation tag (dst) for the hash to scalar function.
Schnorr NIZK (Non-interactive Zero Knowledge) discrete-log proof using CIRCL |
Method
Peggy first creates her secret (\(x\)), and then calculates \(xG\), and where \(G\) is a two random point on an elliptic curve. She sends this to Victor.
Peggy generates a random value (\(v\)) and computes \(V=vG\). Next she creates a challenge (\(c\)) and which is a hash of \(G,V,kG,userID)\):
\(c = H(G,vG,xG,userID)\)
Peggy then responds back with:
\(r= v - c.x\)
The proof this then \((c,r,vG\).
Victor then proves that Peggy still knows the secret with:
\(vG == rG + c.(xG)\)
If both are equal, Peggy has proven that she still knows \(x\).
This works because:
\(rG + c(xG) = (v-cx)G + c(xG) = vG - cxG + cxG = vG\)
Coding
We can use the Circl library from Cloudflare to implement [here]:
package main import ( "crypto/rand" "fmt" "os" "github.com/cloudflare/circl/group" "github.com/cloudflare/circl/zk/dl" ) func main() { dst := "Zero" g := group.P256 curvetype := "P256" argCount := len(os.Args[1:]) if argCount > 0 { curvetype = os.Args[1] } if argCount > 1 { dst = os.Args[2] } switch curvetype { case "P256": g = group.P256 case "P384": g = group.P384 case "P521": g = group.P521 case "Ristretto255": g = group.Ristretto255 } kA := g.RandomNonZeroScalar(rand.Reader) DB := g.RandomElement(rand.Reader) R := g.NewElement() R.Mul(DB, kA) rnd := rand.Reader proof := dl.Prove(g, DB, R, kA, []byte("Prover"), []byte(dst), rnd) verify := dl.Verify(g, DB, R, proof, []byte("Prover"), []byte(dst)) fmt.Printf("kA: %v\n\n", kA) fmt.Printf("DB: %v\n\n", DB) fmt.Printf("Proof: %v\n\n", proof) if verify == false { fmt.Printf("zk/dl verification failed") } else { fmt.Printf("zk/dl verified") } }
A sample run:
x: 0x8bd5aa606bdab878f5fbbdb8d81775b80adea9b7406a58346830d8d2724f38e0 G: x: 0x1720304217a2a36c16ed9449c6b7212e7625f331265b97b6fc1f80c3f1597833 y: 0x3b148d4b7bddfd897c8bcb1c3b4df2bc3a4d7e10e7481ce1fe85c10615eee1fc xG: x: 0xfd37156a064208515d2ca8c5dc85307c1f91315a3ca2760aa43fdb67affb3be6 y: 0x8516c8fcc6334241b7002a0f0ee437db3c75540f0bafa243cdbf0b72525ba55c Proof: {x: 0xfb89da879f62482185671e7313a383fd66ca9da9cfe694f81454f8cf467655f2 y: 0xf6926edcea546515b7848ce53f1c3b14b3f31e2050fbebb20293cdfee7c9ede6 0xab8c64c9c13070cbefddcce4285a6a2886c3c4b8ca2a2bfe3410091bd2524e82} zk/dl verified
Reference
[1] Fiat, A., & Shamir, A. (1986, August). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques (pp. 186-194). Berlin, Heidelberg: Springer Berlin Heidelberg.