A non-interactive zero-knowledge proof (NI-ZKP) for discrete logarithm equivalence (DLEQ) creates VOPRF (Verifiable Oblivious Pseudorandom Function) and POPRF (Partially-oblivious PRF). It shows that two group elements have the same discrete logarithm. We can use Non-interactive zero-knowledge (NIZK) proofs, and where Peggy (the 'Prover') just has to prove that she still knows her secret. For this Victor (the 'Verifier') can send Peggy a challenge, and where Peggy can prove that she can provide a solution for it. Peggy creates a secret value (\(x\)) and then we creates two values \(xG\) and \(xH\), and can check that \(log_{G}(xG) == log_{H}(xH)\). Peggy first creates her secret (\(x\)), and then calculates \(xG\) and \(xH\), and where \(G\) and \(H\) are two random points on an elliptic curve. The secret in this case is \(x\).
Zero-knowledge proofs of Discrete-Logarithm Equivalence (DLEQ) using CIRCL |
Method
Peggy creates a secret value (\(x\)) and then creates two values \(xG\) and \(xH\), and can check that \(log_{G}(xG) == log_{H}(xH)\). Peggy first creates her secret (\(x\)), and then calculates \(xG\) and \(xH\), and where \(G\) and \(H\) are two random points on an elliptic curve.
With the challenge, Victor generates a random value (\(v\)) and computes \(vG\) and \(vH\).
Next Victor creates a challenge (\(c\)) and which is a hash of \(xG,xH,vG,vH\):
\(c = H(xG,xH,vG,vH)\)
Peggy then responds back with:
\(r= v - cx\)
The proof this then \((c,r,vG,vH)\).
Victor then proves that Peggy still knows the secret with:
\(vG == rG + c(xG)\)
\(vH == rH + c(xH)\)
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\)
Overall the method is based on the technique described in "Wallet Databases with Observers - David Chaum and Torben Pryds Pedersen" and defined in this [paper] here:
Coding
We can use the Circl library from Cloudflare to implement [here]:
package main import ( "crypto" "crypto/rand" "encoding/hex" "fmt" "os" "github.com/cloudflare/circl/group" "github.com/cloudflare/circl/zk/dleq" ) 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 } params := dleq.Params{g, crypto.SHA256, []byte(dst)} Peggy := dleq.Prover{params} Victor := dleq.Verifier{params} x := g.RandomScalar(rand.Reader) G := g.RandomElement(rand.Reader) A := g.NewElement().Mul(G, x) H := g.RandomElement(rand.Reader) B := g.NewElement().Mul(H, x) fmt.Printf("Value to prove: %v\n", x) fmt.Printf("Public value (A):\n%v\n", A) fmt.Printf("Public value (B):\n%v\n", B) fmt.Printf("Curve used: %s\n\n", curvetype) fmt.Printf("Domain seperation: %s\n\n", dst) proof, _ := Peggy.Prove(x, G, A, H, B, rand.Reader) p, _ := proof.MarshalBinary() fmt.Printf("Proof: %+v\n", hex.EncodeToString(p)) rtn := Victor.Verify(G, A, H, B, proof) fmt.Printf("Verification: %+v\n", rtn) rr := g.RandomScalar(rand.Reader) proof, _ = Peggy.ProveWithRandomness(x, G, A, H, B, rr) p, _ = proof.MarshalBinary() fmt.Printf("\nProof with randomness: %+v\n", hex.EncodeToString(p)) rtn = Victor.Verify(G, A, H, B, proof) fmt.Printf("Verification: %+v\n", rtn) }
A sample run:
Value to prove: 0xe79b521dad5ff52e2f63b5e29dc77e3b42f17a5ad4338faa464460ea13a61364 Public value (A): x: 0xe35845c8d58e8811352756d266bbe29cfc79874f26a5f47e5894de68d73fe5c6 y: 0xe2c75c88e7f471d3ae3ffbe5ff1c62ca10ed2cab953f297fd608f47ba625cedb Public value (B): x: 0xad5d89c3c26119a48fbdbb6ab974ee46b77ec4f6c600771475971ce042f1a95c y: 0xd770e0035c9eb72f8cac75ecaf5de949a3118d066eeb999938ac59b7960f7f68 Curve used: P256 Domain seperation: Hello Proof: f995ddc272677e86588102086aa34351db6600c51cace1ef3b59d36d7106b7d6be31edabe6525710f5ab41dd68f4bf1badfba224c19e2b974f8cefe4d9e12fa5 Verification: true Proof with randomness: a95744d8b12688a8f7fe674e90450a1efc74003513381caefeb42354fa8df1e7ac789ae7f1dcc7ed4556d17434d80272c4f9cc263b5376aa88a165b5481aedd3 Verification: true