proof

This code creates an And predicate indicating that the prover knows two different secrets x and y, such that point X is equal to x*B and point Y is equal to y*B. This predicate might be used to prove knowledge of the private keys corresponding to two public keys X and Y, for example.

pred := And(Rep("X", "x", "B"), Rep("Y", "y", "B"))
fmt.Println(pred.String())

Output:

X=x*B && Y=y*B

This code creates an And predicate indicating that the prover knows a single secret value x, such that point X1 is equal to x*B1 and point X2 is equal to x*B2. Thus, the prover not only proves knowledge of the discrete logarithm of X1 with respect to B1 and of X2 with respect to B2, but also proves that those two discrete logarithms are equal.

pred := And(Rep("X1", "x", "B1"), Rep("X2", "x", "B2"))
fmt.Println(pred.String())

Output:

X1=x*B1 && X2=x*B2

This example shows how to build classic ElGamal-style digital signatures using the Camenisch/Stadler proof framework and HashProver.

// Crypto setup
rand := blake2xb.New([]byte("example"))
suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)
B := suite.Point().Base() // standard base point

// Create a public/private keypair (X,x)
x := suite.Scalar().Pick(suite.RandomStream()) // create a private key x
X := suite.Point().Mul(x, nil)                 // corresponding public key X

// Generate a proof that we know the discrete logarithm of X.
M := "Hello World!" // message we want to sign
rep := Rep("X", "x", "B")
sec := map[string]kyber.Scalar{"x": x}
pub := map[string]kyber.Point{"B": B, "X": X}
prover := rep.Prover(suite, sec, pub, nil)
proof, _ := HashProve(suite, M, prover)
fmt.Print("Signature:\n" + hex.Dump(proof))

// Verify the signature against the correct message M.
verifier := rep.Verifier(suite, pub)
err := HashVerify(suite, M, verifier, proof)
if err != nil {
	fmt.Println("signature failed to verify: ", err)
	return
}
fmt.Println("Signature verified against correct message M.")

// Now verify the signature against the WRONG message.
BAD := "Goodbye World!"
verifier = rep.Verifier(suite, pub)
err = HashVerify(suite, BAD, verifier, proof)
fmt.Println("Signature verify against wrong message: " + err.Error())

Output:

Signature:
00000000  e9 a2 da f4 9d 7c e2 25  35 be 0a 15 78 9c ea ca  |.....|.%5...x...|
00000010  a7 1e 6e d6 26 c3 40 ed  0d 3d 71 d4 a9 ef 55 3b  |..n.&.@..=q...U;|
00000020  64 76 55 7b 3c 63 20 d8  4b 29 3a 1c 7f 44 59 ad  |dvU{<c .K):..DY.|
00000030  ff 5d c1 ff 06 1d 97 0c  59 06 3c 4b aa 7b 7c 0c  |.]......Y.<K.{|.|
Signature verified against correct message M.
Signature verify against wrong message: invalid proof: commit mismatch

This example implements Linkable Ring Signatures (LRS) generically using the Camenisch/Stadler proof framework and HashProver.

A ring signature proves that the signer owns one of a list of public keys, without revealing anything about which public key the signer actually owns. A linkable ring signature (LRS) is the same but includes a linkage tag, which the signer proves to correspond 1-to-1 with the signer's key, but whose relationship to the private key remains secret from anyone who does not hold the private key. A key-holder who signs multiple messages in the same public "linkage scope" will be forced to use the same linkage tag in each such signature, enabling others to tell whether two signatures in a given scope were produced by the same or different signers.

This scheme is conceptually similar to that of Liu/Wei/Wong in "Linkable and Anonymous Signature for Ad Hoc Groups". This example implementation is less space-efficient, however, because it uses the generic HashProver for Fiat-Shamir noninteractivity instead of Liu/Wei/Wong's customized hash-ring structure.

// Crypto setup
rand := blake2xb.New([]byte("example"))
suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)
B := suite.Point().Base() // standard base point

// Create an anonymity ring of random "public keys"
X := make([]kyber.Point, 3)
for i := range X { // pick random points
	X[i] = suite.Point().Pick(suite.RandomStream())
}

// Make just one of them an actual public/private keypair (X[mine],x)
mine := 2                                      // only the signer knows this
x := suite.Scalar().Pick(suite.RandomStream()) // create a private key x
X[mine] = suite.Point().Mul(x, nil)            // corresponding public key X

// Produce the correct linkage tag for the signature,
// as a pseudorandom base point multiplied by our private key.
linkScope := []byte("The Linkage Scope")
linkHash := suite.XOF(linkScope)
linkBase := suite.Point().Pick(linkHash)
linkTag := suite.Point().Mul(x, linkBase)

// Generate the proof predicate: an OR branch for each public key.
sec := map[string]kyber.Scalar{"x": x}
pub := map[string]kyber.Point{"B": B, "BT": linkBase, "T": linkTag}
preds := make([]Predicate, len(X))
for i := range X {
	name := fmt.Sprintf("X[%d]", i) // "X[0]","X[1]",...
	pub[name] = X[i]                // public point value

	// Predicate indicates knowledge of the private key for X[i]
	// and correspondence of the key with the linkage tag
	preds[i] = And(Rep(name, "x", "B"), Rep("T", "x", "BT"))
}
pred := Or(preds...) // make a big Or predicate
fmt.Printf("Linkable Ring Signature Predicate:\n%s\n", pred.String())

// The prover needs to know which Or branch (mine) is actually true.
choice := make(map[Predicate]int)
choice[pred] = mine

// Generate the signature
M := "Hello World!" // message we want to sign
prover := pred.Prover(suite, sec, pub, choice)
proof, _ := HashProve(suite, M, prover)
fmt.Print("Linkable Ring Signature:\n" + hex.Dump(proof))

// Verify the signature
verifier := pred.Verifier(suite, pub)
err := HashVerify(suite, M, verifier, proof)
if err != nil {
	fmt.Println("signature failed to verify: ", err)
	return
}
fmt.Println("Linkable Ring Signature verified.")

Output:

Linkable Ring Signature Predicate:
(X[0]=x*B && T=x*BT) || (X[1]=x*B && T=x*BT) || (X[2]=x*B && T=x*BT)
Linkable Ring Signature:
00000000  d6 73 58 df 19 52 fc a7  70 2b 42 00 83 03 bd 5f  |.sX..R..p+B...._|
00000010  4d 86 4b 8d db 3d 76 17  00 17 2c b9 a3 6b 54 57  |M.K..=v...,..kTW|
00000020  e1 fd c0 d4 00 9b ea 5d  85 2b f1 83 41 80 ec 83  |.......].+..A...|
00000030  ac b2 f4 0c e4 01 35 61  34 ef 94 34 0b 77 44 3e  |......5a4..4.wD>|
00000040  e3 bd 92 b2 f8 f5 85 97  c4 dd 39 f7 a0 b6 ef b1  |..........9.....|
00000050  65 c6 53 80 e4 78 07 52  62 a5 0b a5 f1 0b 33 2b  |e.S..x.Rb.....3+|
00000060  c8 f5 43 9b 1c bf c2 1a  4a 5b ea b0 e9 18 d1 db  |..C.....J[......|
00000070  a3 57 eb e0 5b d4 99 0e  af f2 10 d4 29 a9 0e 43  |.W..[.......)..C|
00000080  fd 20 a1 42 01 ef 68 a0  43 64 70 f4 f9 09 0f 77  |. .B..h.Cdp....w|
00000090  b3 b0 82 0a 31 8a 66 41  a8 d0 f4 5f 1e da 6e 63  |....1.fA..._..nc|
000000a0  a0 46 74 75 86 6f 3e 85  52 f0 74 6c 74 3b 00 1b  |.Ftu.o>.R.tlt;..|
000000b0  b2 4b 93 95 33 1d 9e 6a  96 43 e5 e2 30 46 6e e5  |.K..3..j.C..0Fn.|
000000c0  2b e0 be 8d 56 55 1a d1  6e 11 21 fc 20 3e 0f 5f  |+...VU..n.!. >._|
000000d0  4d 97 a9 bf 1a 28 27 6d  3b 71 04 e1 c0 86 96 08  |M....('m;q......|
000000e0  8d 0e c0 14 e3 eb 8b e9  16 40 29 60 ab bd e6 1a  |.........@)`....|
000000f0  68 54 5e 29 c8 85 05 bc  4a 27 83 d9 32 cc 74 0f  |hT^)....J'..2.t.|
00000100  5e 16 30 25 e2 d6 35 2a  d4 3e b5 07 1f d4 0a eb  |^.0%..5*.>......|
00000110  5d ef 3b 84 35 39 90 0c  3a 02 bb ee c7 9a e7 09  |].;.59..:.......|
00000120  d1 cc 1e e1 f4 3b 88 52  e5 99 ed 50 d7 66 b5 76  |.....;.R...P.f.v|
00000130  59 6c c1 66 98 07 e5 73  e7 b8 fe 48 43 a0 74 09  |Yl.f...s...HC.t.|
00000140  84 9a 7b ec 21 aa ff c7  fc 79 c6 8f f4 23 82 e7  |..{.!....y...#..|
00000150  d3 71 69 20 d6 94 27 ef  11 0b 4c a5 79 54 1f 09  |.qi ..'...L.yT..|
00000160  6b ec 50 c2 1f 98 38 ea  a7 02 da ca aa 1b 6b 39  |k.P...8.......k9|
00000170  70 b8 35 6c fe 03 1f b0  08 42 e0 5d b2 5e 40 04  |p.5l.....B.].^@.|
Linkable Ring Signature verified.

This code creates an Or predicate indicating that the prover either knows a secret x such that X=x*B, or the prover knows a secret y such that Y=y*B. This predicate in essence proves knowledge of the private key for one of two public keys X or Y, without revealing which key the prover owns.

pred := Or(Rep("X", "x", "B"), Rep("Y", "y", "B"))
fmt.Println(pred.String())

Output:

X=x*B || Y=y*B

This code shows how to create and verify Or-predicate proofs, such as the one above. In this case, we know a secret x such that X=x*B, but we don't know a secret y such that Y=y*B, because we simply pick Y as a random point instead of generating it by scalar multiplication. (And if the group is cryptographically secure we won't find be able to find such a y.)

// Create an Or predicate.
pred := Or(Rep("X", "x", "B"), Rep("Y", "y", "B"))
fmt.Println("Predicate: " + pred.String())

// Crypto setup
rand := blake2xb.New([]byte("example"))
suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)
B := suite.Point().Base() // standard base point

// Create a public/private keypair (X,x) and a random point Y
x := suite.Scalar().Pick(rand) // create a private key x
X := suite.Point().Mul(x, nil) // corresponding public key X
Y := suite.Point().Pick(rand)  // pick a random point Y

// We'll need to tell the prover which Or clause is actually true.
// In this case clause 0, the first sub-predicate, is true:
// i.e., we know a secret x such that X=x*B.
choice := make(map[Predicate]int)
choice[pred] = 0

// Generate a proof that we know the discrete logarithm of X or Y.
sval := map[string]kyber.Scalar{"x": x}
pval := map[string]kyber.Point{"B": B, "X": X, "Y": Y}
prover := pred.Prover(suite, sval, pval, choice)
proof, _ := HashProve(suite, "TEST", prover)
fmt.Print("Proof:\n" + hex.Dump(proof))

// Verify this knowledge proof.
// The verifier doesn't need the secret values or choice map, of course.
verifier := pred.Verifier(suite, pval)
err := HashVerify(suite, "TEST", verifier, proof)
if err != nil {
	fmt.Println("Proof failed to verify: " + err.Error())
}
fmt.Println("Proof verified.")

Output:

Predicate: X=x*B || Y=y*B
Proof:
00000000  44 bb 0f bb 2b 06 29 a6  73 59 0f c1 5a ca de 36  |D...+.).sY..Z..6|
00000010  4c c8 15 ed b1 eb 50 d3  d9 d2 9b 31 6c d3 0f 6b  |L.....P....1l..k|
00000020  a2 a9 bc d2 8c 6d d0 5e  9a 8e d1 8e 04 fb 88 af  |.....m.^........|
00000030  fb 90 8a 2a 71 ac 34 08  f9 bc 07 78 08 44 40 07  |...*q.4....x.D@.|
00000040  ab 1f 36 7e 7b db 50 7d  49 38 34 75 69 07 67 4b  |..6~{.P}I84ui.gK|
00000050  55 cb 28 f2 50 ad d1 4b  24 d2 d1 44 fe 44 b0 0e  |U.(.P..K$..D.D..|
00000060  00 e8 d3 8b 37 76 4f 47  d1 4a 93 0c cd df 20 08  |....7vOG.J.... .|
00000070  fc 0f ad f9 01 6c 30 c0  02 d4 fa 1b 1f 1c fa 04  |.....l0.........|
00000080  6d 2a a7 d8 8e 67 72 87  51 0e 16 72 51 87 99 83  |m*...gr.Q..rQ...|
00000090  2e c9 4e a1 ca 20 7d 64  33 04 f5 66 9b d3 74 03  |..N.. }d3..f..t.|
000000a0  2b e0 be 8d 56 55 1a d1  6e 11 21 fc 20 3e 0f 5f  |+...VU..n.!. >._|
000000b0  4d 97 a9 bf 1a 28 27 6d  3b 71 04 e1 c0 86 96 08  |M....('m;q......|
Proof verified.

This code creates a simple discrete logarithm knowledge proof. In particular, that the prover knows a secret x that is the elliptic curve discrete logarithm of a point X with respect to some base B: i.e., X=x*B. If we take X as a public key and x as its corresponding private key, then this constitutes a "proof of ownership" of the public key X.

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

Output:

X=x*B

This example shows how to generate and verify noninteractive proofs of the statement in the example above, i.e., a proof of ownership of public key X.

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

// Crypto setup
rand := blake2xb.New([]byte("example"))
suite := edwards25519.NewBlakeSHA256Ed25519WithRand(rand)
B := suite.Point().Base() // standard base point

// Create a public/private keypair (X,x)
x := suite.Scalar().Pick(rand) // create a private key x
X := suite.Point().Mul(x, nil) // corresponding public key X

// Generate a proof that we know the discrete logarithm of X.
sval := map[string]kyber.Scalar{"x": x}
pval := map[string]kyber.Point{"B": B, "X": X}
prover := pred.Prover(suite, sval, pval, nil)
proof, _ := HashProve(suite, "TEST", prover)
fmt.Print("Proof:\n" + hex.Dump(proof))

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

Output:

X=x*B
Proof:
00000000  e9 a2 da f4 9d 7c e2 25  35 be 0a 15 78 9c ea ca  |.....|.%5...x...|
00000010  a7 1e 6e d6 26 c3 40 ed  0d 3d 71 d4 a9 ef 55 3b  |..n.&.@..=q...U;|
00000020  c1 84 20 a6 b7 79 86 9c  f8 dd 09 82 1e 48 a9 00  |.. ..y.......H..|
00000030  3e f3 68 66 3f a0 58 f9  88 df b4 35 1b 2f 72 0d  |>.hf?.X....5./r.|
Proof verified.

This code creates a predicate stating that the prover knows a representation of point X with respect to two different bases B1 and B2. This means the prover knows two secrets x1 and x2 such that X=x1*B1+x2*B2.

Point X might constitute a Pedersen commitment, for example, where x1 is the value being committed to and x2 is a random blinding factor. Assuming the discrete logarithm problem is hard in the relevant group and the logarithmic relationship between bases B1 and B2 is unknown - which we would be true if B1 and B2 are chosen at random, for example - then a prover who has committed to point P will later be unable to "open" the commitment using anything other than secrets x1 and x2. The prover can also prove that one of the secrets (say x1) is equal to a secret used in the representation of some other point, while leaving the other secret (x2) unconstrained.

If the prover does know the relationship between B1 and B2, however, then X does not serve as a useful commitment: the prover can trivially compute the x1 corresponding to an arbitrary x2.

pred := Rep("X", "x1", "B1", "x2", "B2")
fmt.Println(pred.String())

Output:

X=x1*B1+x2*B2