Sigma protocol

As explained in Real-World Cryptography

A sigma protocol is an interactive proof pattern consisting of a prover commitment, a verifier challenge, and a prover response.

A sigma protocol is an interactive proof pattern for showing knowledge of a hidden witness without revealing it. The prover first commits, the verifier sends a challenge, and the prover responds. section 7.2.1

The interaction proceeds in three moves:

• Commitment: Peggy chooses random k and sends a value that hides her witness x. section 7.2.1
• Challenge: Victor sends a challenge c only after seeing the commitment. section 7.2.1
• Response: Peggy uses k, x, and c to compute s; without knowing x, she cannot complete the final step. section 7.2.1

The Schnorr identification protocol illustrates the pattern: it is complete, sound, and honest-verifier zero-knowledge when Victor chooses the challenge randomly. A malicious verifier may learn something about the witness. section 7.2.1

Figure 7.6 The Schnorr identification protocol is an interactive ZKP that is complete (Peggy can prove she knows some witness), sound (Peggy cannot prove anything if she doesn’t know the witness), and zero-knowledge (Victor learns nothing about the witness).

Use the protocol diagram to connect completeness, soundness, and zero-knowledge with the three-message interaction. section 7.2.1

How Real-World Cryptography covers it

How deep it goes

Explains commitment, challenge, response, and HVZK, but stops short of formal proof or implementation detail.

Examples

Uses Peggy and Victor, witness x, random value k, generator exponentiation, challenge c, and response s.

What it assumes

Assumes familiarity with witnesses, generators, exponentiation, and commitment schemes while motivating why hash commitments are insufficient.

What you can do after

Evaluate/understand how Schnorr identification uses commitment, challenge, and response to provide a knowledge proof.

How it connects

Connects interactive zero-knowledge proofs with Schnorr identification, commitment schemes, and digital signatures.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Related concepts

• Schnorr identification protocolincludes · The Schnorr identification protocol is an interactive proof-of-knowledge protocol in which a prover demonstrates knowledge of a discrete logarithm without revealing it.
• authentication challengehas part · An authentication challenge is a fresh, unpredictable verifier-provided value that binds a response to a specific authentication exchange.
• Fiat-Shamir transformationused by · The Fiat-Shamir transformation converts an interactive proof into a non-interactive proof by deriving the verifier's challenge from a hash of the protocol transcript.
• zero-knowledge proofkind of · A zero-knowledge proof is a cryptographic protocol in which a prover demonstrates a statement’s truth without revealing information beyond its validity.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.