sigmaprotocol - Sigma Protocols (Zero-Knowledge Proofs)¶

This module provides the base class for implementing Sigma protocols (three-move zero-knowledge proofs) in the Charm cryptographic library.

Overview¶

Sigma protocols are a class of three-move interactive proof systems where a prover convinces a verifier of knowledge of a secret witness (such as a discrete logarithm) without revealing the witness itself. The “sigma” name comes from the Greek letter Σ, representing the three-move structure.

The Three Moves:

Commitment (a): Prover sends a commitment based on random values
Challenge (c): Verifier sends a random challenge
Response (z): Prover sends a response computed from witness and challenge

The verifier accepts if a verification equation holds.

Example - Schnorr Protocol:

To prove knowledge of x such that h = g^x:

Prover: Pick random r, send a = g^r
Verifier: Send random challenge c
Prover: Send z = r + cx
Verifier: Check g^z = a · h^c

Security Properties¶

Sigma protocols provide the following security guarantees:

Security Property	Description
Completeness	An honest prover with a valid witness always convinces the verifier.
Special Soundness	Given two accepting transcripts (a, c₁, z₁) and (a, c₂, z₂) with the same commitment but different challenges, the witness can be extracted. This implies soundness: a cheating prover succeeds with negligible probability.
HVZK (Honest-Verifier Zero-Knowledge)	There exists a simulator that produces transcripts indistinguishable from real ones, without knowing the witness. Security holds when the verifier follows the protocol honestly.
NIZK (via Fiat-Shamir)	By replacing the verifier’s random challenge with a hash of the commitment and statement, the protocol becomes non-interactive. Security holds in the Random Oracle Model.

Typical Use Cases¶

Authentication Protocols

Prove knowledge of a secret key without revealing it. Used in smart card authentication, password-authenticated key exchange, and identity protocols.

# Prover demonstrates knowledge of secret key x
# where public key y = g^x
prover_state1()  # Send commitment a = g^r
# Receive challenge c from verifier
prover_state3()  # Send response z = r + cx
# Verifier checks: g^z == a * y^c

Digital Signatures

Schnorr signatures are Sigma protocols made non-interactive via Fiat-Shamir. The challenge is derived by hashing the commitment and message.
Verifiable Encryption

Prove that a ciphertext encrypts a value satisfying certain properties (e.g., within a range) without revealing the value.

Example Schemes¶

The following Sigma protocol implementations are available in Charm:

Schnorr Zero-Knowledge Protocol:

charm.schemes.protocol_schnorr91 - SchnorrZK: Classic Schnorr identification protocol proving knowledge of discrete log.

from charm.toolbox.ecgroup import ECGroup, G
from charm.toolbox.eccurve import prime192v1
from charm.schemes.protocol_schnorr91 import SchnorrZK

# Setup
group = ECGroup(prime192v1)
sp = SchnorrZK(group)

# Interactive protocol (simplified)
# Prover state 1: generate commitment
# t = g^r, send (t, g, y=g^x) to verifier

# Verifier state 2: generate challenge c

# Prover state 3: compute response s = r + c*x

# Verifier state 4: verify g^s == t * y^c

Pairing-Based Sigma Protocols:

charm.schemes.sigma1 - SigmaProtocol1: Sigma protocol for pairing-based settings
charm.schemes.sigma2 - SigmaProtocol2: Verifiable encryption protocol
charm.schemes.sigma3 - SigmaProtocol3: Proof of membership protocol

Modern ZKP Compiler:

For more advanced zero-knowledge proofs, see the ZKP compiler:

charm.zkp_compiler.schnorr_proof - Non-interactive Schnorr proofs
charm.zkp_compiler.dleq_proof - Discrete log equality proofs
charm.zkp_compiler.representation_proof - Knowledge of representation

from charm.toolbox.pairinggroup import PairingGroup, ZR, G1
from charm.zkp_compiler.schnorr_proof import SchnorrProof

group = PairingGroup('BN254')
g = group.random(G1)
x = group.random(ZR)
h = g ** x

# Non-interactive proof (Fiat-Shamir)
proof = SchnorrProof.prove_non_interactive(group, g, h, x)
is_valid = SchnorrProof.verify_non_interactive(group, g, h, proof)
assert is_valid == True

API Reference¶

class sigmaprotocol.Sigma(groupObj, common_input=None)[source]¶

Bases: Protocol

prover_state1()[source]¶

prover_state3(input)[source]¶

prover_state5(input)[source]¶

verifier_state2(input)[source]¶

verifier_state4(input)[source]¶

verifier_state6(input)[source]¶