`import "go.dedis.ch/kyber/proof"`

Package proof implements generic support for Sigma-protocols and discrete logarithm proofs in the Camenisch/Stadler framework. For the cryptographic foundations of this framework see "Proof Systems for General Statements about Discrete Logarithms" at ftp://ftp.inf.ethz.ch/pub/crypto/publications/CamSta97b.pdf.

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.

Code:

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.

Code:

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.

Code:

// 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.

Code:

// 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.

Code:

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.)

Code:

// 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.

Code:

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.

Code:

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.

Code:

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

Output:

X=x1*B1+x2*B2

- func HashProve(suite Suite, protocolName string, prover Prover) ([]byte, error)
- func HashVerify(suite Suite, protocolName string, verifier Verifier, proof []byte) error
- type Context
- type Predicate
- func And(sub ...Predicate) Predicate
- func Or(sub ...Predicate) Predicate
- func Rep(P string, SB ...string) Predicate
- type Protocol
- type Prover
- type ProverContext
- type Suite
- type Verifier
- type VerifierContext

- package (And1)
- package (And2)
- package (HashProve1)
- package (HashProve2)
- package (Or1)
- package (Or2)
- package (Rep1)
- package (Rep2)
- package (Rep3)

clique.go context.go deniable.go hash.go proof.go

HashProve runs a given Sigma-protocol prover with a ProverContext that produces a non-interactive proof via the Fiat-Shamir heuristic. Returns a byte-slice containing the noninteractive proof on success, or an error in the case of failure.

The optional protocolName is fed into the hash function used in the proof, so that a proof generated for a particular protocolName will verify successfully only if the verifier uses the same protocolName.

The caller must provide a source of random entropy for the proof; this can be random.New() to use fresh random bits, or a pseudorandom stream based on a secret seed to create deterministically reproducible proofs.

HashVerify computes a hash-based noninteractive proof generated with HashProve. The suite and protocolName must be the same as those given to HashProve. Returns nil if the proof checks out, or an error on any failure.

❖

type Context interface { // A follower calls Step to provide its message for the next step, // and wait for the leader to collect and distribute all messages. // Returns the list of collected messages, one per participant. // The returned message slice is positionally consistent across steps: // each index consistently represents the same participant every step. // One returned message will be the same slice as the one passed in, // representing the calling participant's own slot. Step(msg []byte) ([][]byte, error) // Get a source of private cryptographic randomness. Random() kyber.XOF }

Context represents a kyber.context for running a clique protocol. A clique protocol is initiated by a leader but incorporates a variable number of followers, all of whom operate in lock-step under the leader's direction. At each step, each follower produces one message; the leader aggregates all the followers' messages for that step and returns the vector of collected messages to each follower. Followers can drop out or be absent at any step, in which case they are seen as contributing an empty message in that step.

❖

type Predicate interface { // Create a Prover proving the statement this Predicate represents. Prover(suite Suite, secrets map[string]kyber.Scalar, points map[string]kyber.Point, choice map[Predicate]int) Prover // Create a Verifier for the statement this Predicate represents. Verifier(suite Suite, points map[string]kyber.Point) Verifier // Produce a human-readable string representation of the predicate. String() string // contains filtered or unexported methods }

A Predicate is a composable logic expression in a knowledge proof system, representing a "knowledge specification set" in Camenisch/Stadler terminology. Atomic predicates in this system are statements of the form P=x1*B1+...+xn+Bn, indicating the prover knows secrets x1,...,xn that make the statement true, where P and B1,...,Bn are public points known to the verifier. These atomic Rep (representation) predicates may be combined with logical And and Or combinators to form composite statements. Predicate objects, once created, are immutable and safe to share or reuse for any number of proofs and verifications.

After constructing a Predicate using the Rep, And, and Or functions below, the caller invokes Prover() to create a Sigma-protocol prover. Prover() requires maps defining the values of both the Scalar variables and the public Point variables that the Predicate refers to. If the statement contains logical Or operators, the caller must also pass a map containing branch choices for each Or predicate in the "proof-obligated path" down through the Or predicates. See the examples provded for the Or function for more details.

Similarly, the caller may invoke Verifier() to create a Sigma-protocol verifier for the predicate. The caller must pass a map defining the values of the public Point variables that the proof refers to. The verifier need not be provided any secrets or branch choices, of course. (If the verifier needed those then they wouldn't be secret, would they?)

Currently we require that all Or operators be above all And operators in the expression - i.e., Or-of-And combinations are allowed, but no And-of-Or predicates. We could rewrite expressions into this form as Camenisch/Stadler suggest, but that could run a risk of unexpected exponential blowup in the worst case. We could avoid this risk by not rewriting the expression tree, but instead generating Pedersen commits for variables that need to "cross" from one OR-domain to another non-mutually-exclusive one. For now we simply require expressions to be in the appropriate form.

And predicate states that all of the constituent sub-predicates are true. And predicates may contain Rep predicates and/or other And predicates.

Or predicate states that the prover knows at least one of the sub-predicates to be true, but the proof does not reveal any information about which.

Rep creates a predicate stating that the prover knows a representation of a point P with respect to one or more secrets and base point pairs.

In its simplest usage, Rep indicates that the prover knows a secret x that is the (elliptic curve) discrete logarithm of a public point P with respect to a well-known base point B:

Rep(P,x,B)

Rep can take any number of (Scalar,Base) variable name pairs, however. A Rep statement of the form Rep(P,x1,B1,...,xn,Bn) indicates that the prover knows secrets x1,...,xn such that point P is the sum x1*B1+...+xn*Bn.

Protocol represents the role of a participant in a clique protocol. A participant is represented as a higher-order function taking a StarContext, which invokes the StarContext's methods to send and receive messages, and finally returns once the protocol has concluded for all participants. Returns a slice of success/error indicators, one for each participant.

DeniableProver is a Protocol implementing an interactive Sigma-protocol to prove a particular statement to the other participants. Optionally the Protocol participant can also verify the Sigma-protocol proofs of any or all of the other participants. Different participants may produce different proofs of varying sizes, and may even consist of different numbers of steps.

❖

type Prover func(ctx ProverContext) error

Prover represents the prover role in an arbitrary Sigma-protocol. A prover is simply a higher-order function that takes a ProverContext, runs the protocol while making calls to the ProverContext methods as needed, and returns nil on success or an error once the protocol run concludes. The resulting proof is embodied in the interactions with the ProverContext, but HashProve() may be used to encode the proof into a non-interactive proof using a hash function via the Fiat-Shamir heuristic.

❖

type ProverContext interface { Put(message interface{}) error // Send message to verifier PubRand(message ...interface{}) error // Get public randomness PriRand(message ...interface{}) error // Get private randomness }

ProverContext represents the kyber.environment required by the prover in a Sigma protocol.

In a basic 3-step Sigma protocol such as a standard digital signature, the prover first calls Put() one or more times to send commitment information to the verifier, then calls PubRand() to obtain a public random challenge from the verifier, and finally makes further calls to Put() to respond to the challenge.

The prover may also call PriRand() at any time to obtain any private randomness needed in the proof. The prover should obtain secret randomness only from this source, so that the prover may be run deterministically if desired.

More sophisticated Sigma protocols requiring more than 3 steps, such as the Neff shuffle, may also use this interface; in this case the prover simply calls PubRand() multiple times.

❖

type Suite interface { kyber.Group kyber.HashFactory kyber.Encoding kyber.XOFFactory kyber.Random }

Suite defines the functionalities needed for this package to operate correctly. It provides a general abstraction to easily change the underlying implementations.

❖

type Verifier func(ctx VerifierContext) error

Verifier represents the verifier role in an arbitrary Sigma-protocol. A verifier is a higher-order function that takes a VerifierContext, runs the protocol while making calls to VerifierContext methods as needed, and returns nil on success or an error once the protocol run concludes.

❖

type VerifierContext interface { Get(message interface{}) error // Receive message from prover PubRand(message ...interface{}) error // Get public randomness }

VerifierContext represents the kyber.environment required by the verifier in a Sigma protocol.

The verifier calls Get() to obtain the prover's message data, interspersed with calls to PubRand() to obtain challenge data. Note that the challenge itself comes from the VerifierContext, not from the verifier itself as in the traditional Sigma-protocol model. By separating challenge production from proof verification logic, we obtain the flexibility to use a single Verifier function in both non-interactive proofs (e.g., via HashProve) and in interactive proofs (e.g., via DeniableProver).

Package proof imports 6 packages (graph) and is imported by 1 packages. Updated 2019-11-22. Refresh now. Tools for package owners.