Sigma Protocols

Imagine you know a secret password. You want to convince a guard that you know it — but without actually saying it out loud. Is that even possible?

Sigma protocols (named for the Greek letter Σ, whose shape echoes the three-move flow) answer with a resounding yes. They are a family of interactive proofs of knowledge: cryptographic conversations in which a prover convinces a verifier that they know some secret, while the protocol itself leaks nothing about what the secret actually is.

The canonical example is the Schnorr protocol (Claus-Peter Schnorr, 1991), which proves knowledge of a discrete logarithm without revealing it. The idea is disarmingly simple: instead of showing the secret directly, the prover commits to a random blinding value, receives a random challenge, and sends back a response that entangles both. The verifier checks one equation — and learns nothing else.

That combination — completeness (honest provers always pass), soundness (cheaters fail with overwhelming probability), and zero-knowledge (the transcript could have been faked without the secret) — is the magic at the heart of modern privacy-preserving cryptography.

The demo below runs a Schnorr discrete-log proof over a small group so every number stays readable. The prover knows a secret $x$ such that $g^x \equiv y \pmod{p}$. The goal: convince you of that fact without saying what $x$ is.

<!-- {{c_html_intro}} -->
<div class="sigma-app">
  <div class="params-row">
    <span class="param-label">p = <strong id="val-p"></strong></span>
    <span class="param-label">g = <strong id="val-g"></strong></span>
    <span class="param-label">q = <strong id="val-q"></strong></span>
    <span class="param-label">y = g<sup>x</sup> = <strong id="val-y"></strong></span>
    <span class="param-label secret-label">x = <strong id="val-x" class="secret-val"></strong> <em class="secret-tag">{{secret_tag}}</em></span>
  </div>

  <div class="steps-grid">
    <!-- {{c_step1_comment}} -->
    <div class="step-card" id="card-commit">
      <div class="step-num">1</div>
      <div class="step-body">
        <div class="step-title">{{step_commit_title}}</div>
        <div class="step-desc">{{step_commit_desc}}</div>
        <div class="step-math" id="commit-math"></div>
      </div>
    </div>

    <!-- {{c_step2_comment}} -->
    <div class="step-card dimmed" id="card-challenge">
      <div class="step-num">2</div>
      <div class="step-body">
        <div class="step-title">{{step_challenge_title}}</div>
        <div class="step-desc">{{step_challenge_desc}}</div>
        <div class="step-math" id="challenge-math"></div>
      </div>
    </div>

    <!-- {{c_step3_comment}} -->
    <div class="step-card dimmed" id="card-respond">
      <div class="step-num">3</div>
      <div class="step-body">
        <div class="step-title">{{step_respond_title}}</div>
        <div class="step-desc">{{step_respond_desc}}</div>
        <div class="step-math" id="respond-math"></div>
      </div>
    </div>

    <!-- {{c_verify_comment}} -->
    <div class="step-card dimmed" id="card-verify">
      <div class="step-num">✓</div>
      <div class="step-body">
        <div class="step-title">{{step_verify_title}}</div>
        <div class="step-desc">{{step_verify_desc}}</div>
        <div class="step-math" id="verify-math"></div>
      </div>
    </div>
  </div>

  <div class="status-bar" id="status-bar"></div>

  <div class="btns">
    <button id="btn-next" type="button">{{btn_next}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>

  <div class="cheat-panel" id="cheat-panel" style="display:none;">
    <div class="cheat-title">{{cheat_title}}</div>
    <div class="cheat-body" id="cheat-body"></div>
  </div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.sigma-app { padding: .5rem .2rem; }
.params-row { display: flex; flex-wrap: wrap; gap: .5rem .9rem; font-size: .82rem;
              background: #eef2f6; border-radius: 8px; padding: .5rem .8rem; margin-bottom: .8rem; }
.param-label { color: #444; }
.secret-label { color: #c0392b; }
.secret-val { color: #c0392b; }
.secret-tag { font-style: italic; font-size: .75rem; color: #888; }

.steps-grid { display: grid; grid-template-columns: 1fr 1fr; gap: .5rem; margin-bottom: .6rem; }
.step-card { border: 1.5px solid #cdd9e3; border-radius: 10px; padding: .55rem .75rem;
             display: flex; gap: .5rem; background: #f5f8fb; transition: opacity .25s, border-color .25s; }
.step-card.dimmed { opacity: .38; }
.step-card.active { border-color: #1d3557; background: #eaf0f8; opacity: 1; }
.step-card.done { border-color: #0a7d33; background: #edfaf2; opacity: 1; }
.step-card.fail { border-color: #c0392b; background: #fdecea; opacity: 1; }
.step-num { font-weight: 700; font-size: 1.05rem; color: #1d3557; min-width: 1.4rem; }
.step-title { font-weight: 700; font-size: .88rem; color: #1d3557; margin-bottom: .15rem; }
.step-desc { font-size: .78rem; color: #555; line-height: 1.35; }
.step-math { font-family: ui-monospace, monospace; font-size: .82rem; color: #222;
             margin-top: .3rem; line-height: 1.5; min-height: 1.2em; }

.status-bar { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .4rem 0 .5rem; }
.status-bar.ok { color: #0a7d33; }
.status-bar.bad { color: #c0392b; }
.status-bar.info { color: #1d3557; }

.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

.cheat-panel { margin-top: .8rem; border: 1.5px solid #e2a800; border-radius: 10px;
               padding: .55rem .75rem; background: #fffbea; }
.cheat-title { font-weight: 700; color: #b87800; font-size: .85rem; margin-bottom: .3rem; }
.cheat-body { font-size: .82rem; color: #555; line-height: 1.5; }

@media (max-width: 420px) {
  .steps-grid { grid-template-columns: 1fr; }
  .params-row { font-size: .78rem; }
}

// Code not found

Notice the structure. The commit step blinds the secret with fresh randomness $r$: the prover sends $A = g^r \bmod p$. The challenge $e$ arrives from the verifier (or, in practice, from a hash). The response $z = r + e \cdot x$ folds the challenge in. Finally the verifier checks $g^z \equiv A \cdot y^e \pmod{p}$ — one modular equation, no secret needed. A cheater without $x$ would have to predict $e$ in advance, which happens with probability $1/q$: negligible for a large prime $q$.

What makes a sigma protocol work — and what are its limits?

• Completeness: if the prover truly knows $x$, the verification equation $g^z \equiv A \cdot y^e \pmod{p}$ always holds. This follows from the algebra: $g^{r+ex} = g^r \cdot (g^x)^e = A \cdot y^e$.
• Special soundness: given two accepting transcripts $(A, e_1, z_1)$ and $(A, e_2, z_2)$ with the same commitment but different challenges, one can extract the secret as $x = (z_1 - z_2)/(e_1 - e_2) \bmod q$. A cheater who cannot predict the challenge cannot fake two such transcripts — so cheating succeeds only with probability $1/q$.
• Honest-verifier zero-knowledge (HVZK): a simulator can produce transcripts $(A, e, z)$ that are statistically indistinguishable from real ones — without knowing $x$. It picks $z$ and $e$ at random, then sets $A = g^z \cdot y^{-e} \bmod p$. Because the challenge is chosen after the commitment in a real run, the distributions match perfectly.
• The Fiat–Shamir transform (Amos Fiat and Adi Shamir, 1986) replaces the verifier's random challenge with a cryptographic hash $e = H(A \| \text{message})$. This converts the interactive protocol into a non-interactive zero-knowledge (NIZK) proof — and, when a message is hashed in, into a digital signature. The Schnorr signature scheme is exactly this transform applied to the Schnorr protocol.
• Security assumption: the protocol's soundness rests on the hardness of the discrete logarithm problem. Break discrete log and you break the proof.

The commit-challenge-respond pattern is one of cryptography's most reused building blocks:

• Digital signatures: the Schnorr signature (now standardized in EdDSA and used in Signal, SSH, and TLS 1.3) is literally the Fiat–Shamir transform of the Schnorr sigma protocol.
• Anonymous credentials: systems like Microsoft U-Prove and IRMA let you prove properties about yourself (age, membership) without revealing your identity — via sigma protocols for committed values.
• Ring signatures and group signatures: proving "I am one of these $n$ people" without saying which one uses sigma protocols composed with OR-proofs.
• Zero-knowledge range proofs: proving a committed number lies in $[0, 2^k - 1]$ without revealing it — essential for confidential transactions in Monero, Zcash, and similar systems.
• zk-SNARKs and zk-STARKs: modern succinct zero-knowledge proof systems build on the same completeness/soundness/zero-knowledge triad that sigma protocols made concrete, scaling it to arbitrary computations.

Understand sigma protocols and you hold the key to every privacy layer in modern cryptography — from your chat app to the blockchain.

Sigma protocols distill a profound idea into three lines of algebra: commit to hide yourself in randomness, challenge to prevent cheating, respond to prove you know without showing. The result is a protocol that is simultaneously convincing and revealing nothing.

The Fiat–Shamir transform then collapses the interaction entirely, turning a conversation into a signature. That single insight — that a hash can replace a verifier — connects sigma protocols to nearly every privacy-preserving construction in modern cryptography.

So the next time your phone signs into a server, or a blockchain transaction hides its amount, or an anonymous credential proves your age — somewhere in the machinery, three numbers are dancing the sigma protocol's elegant waltz. See also: discrete logarithm and the factoring problem that underlies so many cryptographic hardness assumptions.