When Peggy Met Victor in Go

When Peggy Met Victor in Go

The demo of the method defined is given here.

So how does Peggy prove her password to Victor, without Victor knowing what her password is. With this we need to define the concept of proof of knowledge, Peggy (the prover) must verify to Victor (the verifier) that she can solve a difficult problem. we must then have:

• An honest prover who can verify themselves to the verifier (completeness).
• A high probability that prover cannot cheat, and thus guess the solution (soundness).
• The prover cannot guess the secret from the proof (zero knowledge, witness hiding and minimum-disclosure).

A standard proof in discrete logs, is to show that Peggy still knows the value of x given that the prover knows (X) and where q is a prime number:

X=g^x (mod q)

The following [taken from here]. In this case we will create:

X=xB

Y=yB

R=xB+yB

and where B is a base point on the elliptic curve, and x and y are secrets. We will then prove that X=xB and R=xB+yB, but that X=yB is false [here]:

package main

import (

    "fmt"
    "go.dedis.ch/kyber"
    "go.dedis.ch/kyber/group/edwards25519"

    "go.dedis.ch/kyber/proof"
    "go.dedis.ch/kyber/xof/blake2xb"

    "encoding/hex"
)

func main() {
    
    rand := blake2xb.New([]byte("example"))
    suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)

    x := suite.Scalar().Pick(rand)
    y := suite.Scalar().Pick(rand)
    B := suite.Point().Base()
    X := suite.Point().Mul(x, nil)
    Y := suite.Point().Mul(y, X)
    R := suite.Point().Add(X, Y)
    
    
    fmt.Printf("X=xB and Y=yB and R=xB+yB\n")
    fmt.Printf("x=%s, B=%s, X=%s, y=%s, Y=%s, R=%s\n\n",x,B,X,y,Y,R)

    // X = xB
    pred := proof.Rep("X", "x", "B")
    fmt.Println(pred.String())

    sval := map[string]kyber.Scalar{"x": x}
    pval := map[string]kyber.Point{"B": B, "X": X}

    prover := pred.Prover(suite, sval, pval, nil)
    proof_, _ := proof.HashProve(suite, "TEST", prover)

    fmt.Printf("We need to prove that we known the discrete log of X\n")
    fmt.Print("Proof:\n" + hex.Dump(proof_))

    
    // Verify this knowledge proof.
    verifier := pred.Verifier(suite, pval)
    err := proof.HashVerify(suite, "TEST", verifier, proof_)
    if err != nil {
        fmt.Println("Proof failed to verify: ", err)
        return
    }

    fmt.Println("Proof verified.\n\n")

    pred = proof.Rep("X", "y", "B")
    fmt.Println(pred.String())

    sval = map[string]kyber.Scalar{"y": y}
    pval = map[string]kyber.Point{"B": B, "X": X}
    prover = pred.Prover(suite, sval, pval, nil)
    proof_, _ = proof.HashProve(suite, "TEST", prover)
    fmt.Print("Proof:\n" + hex.Dump(proof_))
    verifier = pred.Verifier(suite, pval)
    err = proof.HashVerify(suite, "TEST", verifier, proof_)
    if err != nil {
        fmt.Println("Proof failed to verify: ", err)
        return
    }

    fmt.Println("Proof verified.")

}

The following is a sample run [here]:

X=xB and Y=yB and R=xB+yB
x=d91cf8c3dfc7c2b8f85220e88078617a680a9305bf1cd4479773423b6641ef04, B=5866666666666666666666666666666666666666666666666666666666666666, X=2b6691aafccb1957c4e0599a05345e33477a50f0e90e76907a3d260ed6fb5996, y=41806461e988fd866c24303a869b1c9c502be96aabd5846f99cc72ac6fdbf003, Y=ab4458a44bf14c02c1c8e54821874df9ff7c659484d4187d128b39a616c87eee, R=dfd96cdecc9fcd17f855b9ad8e8577893491eaed17a95c5894927e084d112a31

X=x*B
We need to prove that we known the discrete log of X
Proof:
00000000  ed 23 bc a3 a5 07 a7 79  7c bc ff 36 2f e4 72 66  |.#.....y|..6/.rf|
00000010  03 65 b8 ad 7b 56 61 55  38 57 83 75 0b 87 e1 4d  |.e..{VaU8W.u...M|
00000020  89 b9 09 19 f3 b9 a4 65  3c d9 e3 9f 84 b3 13 3b  |.......e.......;|
00000030  89 58 4f f9 df be 22 67  0a eb 7f 70 a8 7d f1 0a  |.XO..."g...p.}..|
-- Proof verified.

R=x*B+y*B
Proof:
00000000  07 30 df 5d 3b 6a 24 41  81 44 81 65 54 ef b9 3c  |.0.];j$A.D.eT...|
00000010  88 d6 82 56 76 98 79 34  5e 54 34 a2 7b ae 43 d1  |...Vv.y4^T4.{.C.|
00000020  31 af 5f dc fe ec aa a2  4a 4d 96 09 88 81 be dc  |1._.....JM......|
00000030  92 ab d3 ff 5b ba 75 2e  6e a0 2d 3c 86 a1 86 09  |....[.u.n.-.....|
00000040  88 cf 11 bf 25 7f 95 b9  9b 99 fe 08 3f 46 01 12  |....%.......?F..|
00000050  af 09 6c d0 be ac f8 d9  29 08 ca 03 1d 99 6a 05  |..l.....).....j.|
-- Proof verified.

X=y*B
Proof:
00000000  fb 1f 44 72 8a 95 68 37  89 58 54 4e 01 fb 9f 5c  |..Dr..h7.XTN...\|
00000010  68 61 e0 64 52 ec f1 ae  ae 4f 12 96 30 2d ea 9f  |ha.dR....O..0-..|
00000020  43 40 af fd 57 a3 2a b8  31 a5 d5 82 d9 10 79 7d  |C...W.*.1.....y}|
00000030  74 08 15 3a 7e 12 28 9f  e4 18 f1 c2 8f bc 4e 08  |t..:~.(.......N.|
Proof failed to verify:  invalid proof: commit mismatch

At the core of the method is the Fiat-Shamir construct:

You can learn more here: