proof

Documentation

Overview

This package provides functionality to create and verify non-interactive zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL). This means, for two values xG and xH one can check that

log_{G}(xG) == log_{H}(xH)

without revealing the secret value x.

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.

Index

• func DeniableProver(suite abstract.Suite, self int, prover Prover, verifiers []Verifier) clique.Protocol
• func HashProve(suite abstract.Suite, protocolName string, random abstract.Cipher, ...) ([]byte, error)
• func HashVerify(suite abstract.Suite, protocolName string, verifier Verifier, proof []byte) error
• type DLEQProof
  • func NewDLEQProof(suite abstract.Suite, G abstract.Point, H abstract.Point, x abstract.Scalar) (proof *DLEQProof, xG abstract.Point, xH abstract.Point, err error)
  • func NewDLEQProofBatch(suite abstract.Suite, G []abstract.Point, H []abstract.Point, ...) (proof []*DLEQProof, xG []abstract.Point, xH []abstract.Point, err error)
  • func (p *DLEQProof) Verify(suite abstract.Suite, G abstract.Point, H abstract.Point, xG abstract.Point, ...) error
• type Predicate
  • func And(sub ...Predicate) Predicate
  • func Or(sub ...Predicate) Predicate
  • func Rep(P string, SB ...string) Predicate
• type Prover
• type ProverContext
• type Verifier
• type VerifierContext

Functions

func DeniableProver

func DeniableProver(suite abstract.Suite, self int, prover Prover,
	verifiers []Verifier) clique.Protocol

Create a clique.Protocol implementing an interactive Sigma-protocol to prove a particular statement to the other participants. Optionally the clique.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.

func HashProve

func HashProve(suite abstract.Suite, protocolName string,
	random abstract.Cipher, prover Prover) ([]byte, error)

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.Stream to use fresh random bits, or a pseudorandom stream based on a secret seed to create deterministically reproducible proofs.

func HashVerify

func HashVerify(suite abstract.Suite, protocolName string,
	verifier Verifier, proof []byte) error

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

Types

type DLEQProof

type DLEQProof struct {
	C  abstract.Scalar // challenge
	R  abstract.Scalar // response
	VG abstract.Point  // public commitment with respect to base point G
	VH abstract.Point  // public commitment with respect to base point H
}

DLEQProof represents a NIZK dlog-equality proof.

func NewDLEQProof

func NewDLEQProof(suite abstract.Suite, G abstract.Point, H abstract.Point, x abstract.Scalar) (proof *DLEQProof, xG abstract.Point, xH abstract.Point, err error)

NewDLEQProof computes a new NIZK dlog-equality proof for the scalar x with respect to base points G and H. It therefore randomly selects a commitment v and then computes the challenge c = H(xG,xH,vG,vH) and response r = v - cx. Besides the proof, this function also returns the encrypted base points xG and xH.

func NewDLEQProofBatch

func NewDLEQProofBatch(suite abstract.Suite, G []abstract.Point, H []abstract.Point, secrets []abstract.Scalar) (proof []*DLEQProof, xG []abstract.Point, xH []abstract.Point, err error)

NewDLEQProofBatch computes lists of NIZK dlog-equality proofs and of encrypted base points xG and xH. Note that the challenge is computed over all input values.

func (*DLEQProof) Verify

func (p *DLEQProof) Verify(suite abstract.Suite, G abstract.Point, H abstract.Point, xG abstract.Point, xH abstract.Point) error

Verify examines the validity of the NIZK dlog-equality proof. The proof is valid if the following two conditions hold:

vG == rG + c(xG)
vH == rH + c(xH)

type Predicate

type Predicate interface {

	// Create a Prover proving the statement this Predicate represents.
	Prover(suite abstract.Suite, secrets map[string]abstract.Scalar,
		points map[string]abstract.Point, choice map[Predicate]int) Prover

	// Create a Verifier for the statement this Predicate represents.
	Verifier(suite abstract.Suite, points map[string]abstract.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.

func And

func And(sub ...Predicate) Predicate

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

func Or

func Or(sub ...Predicate) Predicate

func Rep

func Rep(P string, SB ...string) Predicate

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.

type Prover

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

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

ProverContext represents the abstract 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 Verifier

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

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

ProverContext represents the abstract 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).