DLEQ - Non-interactive zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL)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\)) from her password (\(x=Hash(Password)\)), and then calculates \(xG\) and \(xH\), and where \(G\) and \(H\) are two random points on an elliptic curve (in this case it is from an Edwards 25519 curve). |
Method
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\)) from her password (\(x=Hash(Password)\)), 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\)
Over 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:
Outline
The following is the code [taken from here]:
// Code from https://github.com/dedis/kyber package main import ( "fmt" "go.dedis.ch/kyber" "go.dedis.ch/kyber/proof/dleq" "go.dedis.ch/kyber/suites" "go.dedis.ch/kyber/group/edwards25519" "go.dedis.ch/kyber/util/random" "crypto/sha256" "os" "errors" ) var rng = random.New() func NewDLEQProof(suite suites.Suite, G kyber.Point, H kyber.Point, x kyber.Scalar) (proof *dleq.Proof, xG kyber.Point, xH kyber.Point, v kyber.Scalar,err error) { // Encrypt base points with secret xG = suite.Point().Mul(x, G) xH = suite.Point().Mul(x, H) // Commitment v = suite.Scalar().Pick(suite.RandomStream()) vG := suite.Point().Mul(v, G) vH := suite.Point().Mul(v, H) // Challenge h := suite.Hash() xG.MarshalTo(h) xH.MarshalTo(h) vG.MarshalTo(h) vH.MarshalTo(h) cb := h.Sum(nil) c := suite.Scalar().Pick(suite.XOF(cb)) // Response r := suite.Scalar() r.Mul(x, c).Sub(v, r) return &dleq.Proof{c, r, vG, vH}, xG, xH, v,nil } func Verify(p *dleq.Proof, suite suites.Suite, G kyber.Point, H kyber.Point, xG kyber.Point, xH kyber.Point) error { rG := suite.Point().Mul(p.R, G) rH := suite.Point().Mul(p.R, H) cxG := suite.Point().Mul(p.C, xG) cxH := suite.Point().Mul(p.C, xH) a := suite.Point().Add(rG, cxG) b := suite.Point().Add(rH, cxH) if !(p.VG.Equal(a) && p.VH.Equal(b)) { return errors.New("invalid proof") } return nil } func main() { suite := edwards25519.NewBlakeSHA256Ed25519() m:="Hello" argCount := len(os.Args[1:]) if (argCount>0) {m= string(os.Args[1])} message := []byte(m) scal := sha256.Sum256(message[:]) x := suite.Scalar().SetBytes(scal[:32]) g := suite.Point().Pick(rng) h := suite.Point().Pick(rng) proof, xG, xH, v, err := NewDLEQProof(suite, g, h, x) if (err==nil) { fmt.Printf("Secret: %s\n",m) fmt.Printf("x: %x\n\n",scal) fmt.Printf("G: %s\nH: %s\n",g,h) fmt.Printf("xG %s\nxH %s\n",xG,xH) fmt.Printf("\nProof created\nChallenge (c): %s\nResponse (r): %s\nvG: %s\nvH: %s\nv: %s",proof.C,proof.R,proof.VG,proof.VH,v) } rtn:=Verify(proof,suite, g, h, xG, xH) if (rtn==nil) { fmt.Printf("\n\nPeggy has proven she still knows her secret") } }
A sample run is:
Secret: Testing 123 x: 9734aef6d3788ba985e78f7b3785dc4817e770be92a4e5e57e64a92cc9c2fc25 G: 5c72b580b791ee5a699c71dcb40d417850eef748b2812dad0413a2d7b962e15b H: 9c26104e3904e7a60a57492080c00218c4fa71de4ca291a59585a681e378e463 xG a36bbfe5e20f41da437c03fa7f7864bf02d7dee029732f826dc172d36aa6706a xH ce37afe095f099d0f1cbcf41e11ba6abad716426ac49c044bdbce343f0c000bb Proof created Challenge (c): 4e65bfc0346a049d8ebec91e47693d51565f00719e842412a832ef582b92500c Response (r): 307ede7a7d0a3507512f3963a7d2e91436c077085455fe9b016731214832320e vG: 10fa72e0636b63593ffb8d9ada2d2960adc7b297f8b45730d5334e8339576b15 vH: 320041b2907ab8b6f84dc7566ee58a449d3bd19d02a750129c9eb785daff6f8e v: 9cc4bb3a257874799514d5380227919c7b52a13c11777f2de8fac46fb796e00a Peggy has proven she still knows her secret
For NIST P-256, we just add:
import ( "go.dedis.ch/kyber/group/nist" ) suite := nist.NewBlakeSHA256P256()
For BN256 pairing, we just add:
import ( "go.dedis.ch/kyber/pairing" ) suite := pairing.NewSuiteBn256()