Sigma Protocols

Sigma Protocols are a basic building block for Zero-knowledge proofs, Zero-Knowledge Proofs Of Knowledge and more. A sigma protocol is a 3-round proof, comprised of:

  1. A first message from the prover to the verifier
  2. A random challenge from the verifier
  3. A second message from the prover.

Sigma Protocol can be executed as a standalone protocol or as a building block for another protocol, like Zero Knowledge proofs. As a standalone protocol, Sigma protocol should execute the protocol as is, including the communication between the prover and the verifier. As a building block for other protocols, Sigma protocol should only compute the prover’s first and second messages and the verifier’s challenge and verification. This is, in other words, the protocol functions without communication between the parties.

To enable both options, there is a separation between the communication part and the actual protocol computations. The general structure of Sigma Protocol contains the following components:

  • Prover, Verifier and Simulator generic interfaces.
  • Prover and Verifier abstract classes.
  • ProverComputation and VerifierComputation classes (Specific to each protocol).

The Prover Interface

The SigmaProtocolProver interface has two modes of operation:

  1. Explicit mode - call processFirstMessage() to process the first message and afterwards call processSecondMessage() to process the second message.
  2. Implicit mode - Call prove() function that calls the above two functions. This way is more easy to use since the user should not be aware of the order in which the functions must be called.
public interface SigmaProtocolProver

General interface for Sigma Protocol prover. Every class that implements it is signed as Sigma Protocol prover. Sigma protocols are a basic building block for zero-knowledge, zero-knowledge proofs of knowledge and more.

A sigma protocol is a 3-round proof, comprised of a first message from the prover to the verifier, a random challenge from the verifier and a second message from the prover. See Hazay-Lindell (chapter 6) for more information.

public void processFirstMsg(SigmaProverInput input)

Processes the first step of the sigma protocol. It computes the first message and sends it to the verifier.

Parameters:
  • input
Throws:
  • IOException – if failed to send the message.
public void processSecondMsg()

Processes the second step of the sigma protocol. It receives the challenge from the verifier, computes the second message and then sends it to the verifier.

This is a blocking function!

Throws:
  • CheatAttemptException – if the received challenge’s length is not equal to the soundness parameter.
  • IOException – if there was a problem during the communication phase.
  • ClassNotFoundException – if there was a problem during the serialization mechanism.
public void prove(SigmaProverInput input)

Runs the proof of this protocol.

This function executes the proof at once by calling the above functions one by one. This function can be called when a user does not want to save time by doing operations in parallel.

Parameters:
  • input
Throws:
  • CheatAttemptException – if the received challenge’s length is not equal to the soundness parameter.
  • IOException – if there was a problem during the communication phase.
  • ClassNotFoundException – if there was a problem during the serialization mechanism.

The Verifier Interface

The SigmaProtocolVerifier also has two modes of operation:

  1. Explicit mode – call sampleChallenge() to sample the challenge, then sendChallenge() to receive the prover’s first message and then call processVerify() to receive the prover’s second message and verify the proof.
  2. Implicit mode - Call verify() function that calls the above three functions. Same as the prove function of the prover, this way is much simpler, since the user should not know the order of the functions.
public interface SigmaProtocolVerifier

General interface for Sigma Protocol verifier. Every class that implements it is signed as Sigma Protocol verifier.

public byte[] getChallenge()

Returns the sampled challenge.

Returns:the challenge.
public boolean processVerify(SigmaCommonInput input)

Waits to the prover’s second message and then verifies the proof. This is a blocking function!

Parameters:
  • input
Throws:
  • ClassNotFoundException – if there was a problem during the serialization mechanism.
  • IOException – if there was a problem during the communication phase.
Returns:

true if the proof has been verified; false, otherwise.

public void sampleChallenge()

Samples the challenge for this protocol.

public void sendChallenge()

Waits for the prover’s first message and then sends the chosen challenge to the prover. This is a blocking function!

Throws:
  • ClassNotFoundException – if there was a problem during the serialization mechanism.
  • IOException – if there was a problem during the communication phase.
public void setChallenge(byte[] challenge)

Sets the given challenge.

Parameters:
  • challenge
public boolean verify(SigmaCommonInput input)

Runs the verification of this protocol.

This function executes the verification protocol at once by calling the following functions one by one. This function can be called when a user does not want to save time by doing operations in parallel.

Parameters:
  • input
Throws:
  • ClassNotFoundException – if there was a problem during the serialization mechanism.
  • IOException – if there was a problem during the communication phase.
Returns:

true if the proof has been verified; false, otherwise.

The Simulator Interface

The SigmaSimulator has two simulate() functions. Both functions simulate the sigma protocol. The difference between them is the source of the challenge; one function receives the challenge as an input argument, while the other samples a random challenge. Both simulate functions return SigmaSimulatorOutput object that holds the simulated a, e, z.

public interface SigmaSimulator

General interface for Sigma Protocol Simulator. The simulator is a probabilistic polynomial-time function, that on input x and challenge e outputs a transcript of the form (a, e, z) with the same probability distribution as transcripts between the honest prover and verifier on common input x.

public int getSoundnessParam()

Returns the soundness parameter for this Sigma simulator.

Returns:t soundness parameter
public SigmaSimulatorOutput simulate(SigmaCommonInput input, byte[] challenge)

Computes the simulator computation.

Parameters:
  • input
  • challenge
Throws:
  • CheatAttemptException – if the received challenge’s length is not equal to the soundness parameter.
Returns:

the output of the computation - (a, e, z).

public SigmaSimulatorOutput simulate(SigmaCommonInput input)

Chooses random challenge and computes the simulator computation.

Parameters:
  • input
Returns:

the output of the computation - (a, e, z).

Computation classes

The classes that operate the actual protocol phases implement the SigmaProverComputation and SigmaVerifierComputation interfaces. SigmaProverComputation computes the prover’s messages and SigmaVerifierComputation computes the verifier’s challenge and verification. Each operation is done in a dedicated function.

In case that Sigma Protocol is used as a building block, the protocol which uses it will hold an instance of SigmaProverComputation or SigmaVerifierComputation and will call the required function. Each concrete sigma protocol should implement the computation interfaces.

SigmaProverComputation

public interface SigmaProverComputation

This interface manages the mathematical calculations of the prover side in the sigma protocol. It samples random values and computes the messages.

public SigmaProtocolMsg computeFirstMsg(SigmaProverInput input)

Computes the first message of the sigma protocol.

Parameters:
  • input
public SigmaProtocolMsg computeSecondMsg(byte[] challenge)

Computes the second message of the sigma protocol.

Throws:
  • CheatAttemptException – if the received challenge’s length is not equal to the soundness parameter.

SigmaVerifierComputation

public interface SigmaVerifierComputation

This interface manages the mathematical calculations of the verifier side in the sigma protocol. It samples random challenge and verifies the proof.

public void sampleChallenge()

Samples the challenge for this protocol.

public void setChallenge(byte[] challenge)

Sets the given challenge.

Parameters:
  • challenge
public byte[] getChallenge()

Returns the sampled challenge.

Returns:the challenge.
public boolean verify(SigmaCommonInput input, SigmaProtocolMsg a, SigmaProtocolMsg z)

Verifies the proof.

Parameters:
  • input
Returns:

true if the proof has been verified; false, otherwise.

Supported Protocols

Concrete Sigma protocols implemented so far are:

  • Dlog
  • DH
  • Extended DH
  • Pedersen commitment knowledge
  • Pedersen committed value
  • El Gamal commitment knowledge
  • El Gamal committed value
  • El Gamal private key
  • El Gamal encrypted value
  • Cramer-Shoup encrypted value
  • Damgard-Jurik encrypted zero
  • Damgard-Jurik encrypted value
  • Damgard-Jurik product
  • AND (of multiple statements)
  • OR of two statements
  • OR of multiple statements

Example of Usage

Steps in prover creation:

  • Given a Channel object channel and input for the concrete Sigma protocol prover (In the example below, x and h) do:
    • Create a SigmaProverComputation (for example, SigmaDlogProverComputation).
    • Create a SigmaProtocolProver with channel and the proverComputation.
    • Create input object for the prover.
    • Call the prove() function of the prover with the input.

Prover code example:

//Creates the dlog group.
DlogGroup dlog = null;
try {
    //use the koblitz curve.
    dlog = new MiraclDlogECF2m("K-233");
} catch (FactoriesException e1) {
    // TODO Auto-generated catch block
    e1.printStackTrace();
}

//Creates sigma prover computation.
SigmaProverComputation proverComputation = new SigmaDlogProverComputation(dlog, t, new SecureRandom());

//Create Sigma Prover with the given SigmaProverComputation.
SigmaProver prover = new SigmaProver(channel, proverComputation);

//Creates input for the prover.
SigmaProverInput input = new SigmaDlogProverInput(h, w);

//Calls the prove function of the prover.
prover.prove(input);

Steps in verifier creation:

  • Given a Channel object channel and input for the concrete Sigma protocol verifier (In the example below, h) do:
    • Create a SigmaVerifierComputation (for example, SigmaDlogVerifierComputation).
    • Create a SigmaProtocolVerifier with channel and verifierComputation.
    • Create input object for the verifier.
    • Call the verify() function of the verifier with the input.

Verifier code example:

//Creates the dlog group
DlogGroup dlog = null;
try {
    //use the koblitz curve
    dlog = new MiraclDlogECF2m("K-233");
} catch (FactoriesException e1) {
    // TODO Auto-generated catch block
    e1.printStackTrace();
}

//Creates sigma verifier computation.
SigmaVerifierComputation verifierComputation = new SigmaDlogVerifierComputation(dlog, t, new SecureRandom());

//Creates Sigma verifier with the given SigmaVerifierComputation.
SigmaVerifier verifier = new SigmaVerifier(channel, verifierComputation);

// Creates input for the verifier.
SigmaCommonInput input = new SigmaDlogCommonInput(h);

//Calls the verify function of the verifier.
verifier.verify(input);