The Fiat-Shamir Transform

Imagine proving to a friend that you know a secret — without revealing the secret itself. That is the goal of a zero-knowledge proof: convince a verifier that a statement is true while leaking nothing beyond the truth of the statement.

The classic way to do it is a three-step dance called a Σ-protocol (sigma protocol):

1. The prover sends a commitment — a random blinding value.
2. The verifier picks a random challenge and sends it back.
3. The prover computes a response that ties the challenge to the secret, and the verifier checks it.

This works beautifully — but it requires the prover and verifier to be online at the same time. In 1986, Amos Fiat and Adi Shamir asked a disarmingly simple question: what if the prover just computed the challenge themselves, using a hash function?

Replace the verifier's random challenge with $H(\text{commitment} \| \text{message})$, where $H$ is a cryptographic hash, and the interaction collapses to a single object the prover publishes. Anyone can check it later, without a live verifier. That one substitution — the Fiat-Shamir transform — turned interactive proofs into digital signatures and shaped modern cryptography.

The demo below runs the full Fiat-Shamir pipeline over a small toy group $\mathbb{Z}_{p}^{*}$. Pick a secret, watch the prover commit, hash the challenge, and respond — then verify the result without any back-and-forth.

<!-- {{c_html_intro}} -->
<div class="fs-app">
  <section class="setup-row">
    <div class="field">
      <label for="secret">{{lbl_secret}}</label>
      <input id="secret" type="number" min="1" max="22" value="7" />
      <span class="hint-inline">{{hint_secret_range}}</span>
    </div>
    <div class="field">
      <label for="message">{{lbl_message}}</label>
      <input id="message" type="text" maxlength="40" value="hello" placeholder="{{ph_message}}" />
    </div>
  </section>

  <div class="steps">
    <div class="step" id="step-commit">
      <div class="step-num">1</div>
      <div class="step-body">
        <strong>{{lbl_commit}}</strong>
        <div class="step-math" id="out-commit">—</div>
        <div class="step-note" id="note-commit"></div>
      </div>
    </div>
    <div class="step" id="step-challenge">
      <div class="step-num">2</div>
      <div class="step-body">
        <strong>{{lbl_challenge}}</strong>
        <div class="step-math" id="out-challenge">—</div>
        <div class="step-note" id="note-challenge"></div>
      </div>
    </div>
    <div class="step" id="step-response">
      <div class="step-num">3</div>
      <div class="step-body">
        <strong>{{lbl_response}}</strong>
        <div class="step-math" id="out-response">—</div>
        <div class="step-note" id="note-response"></div>
      </div>
    </div>
  </div>

  <div class="sig-box" id="sig-box" hidden>
    <span class="sig-label">{{lbl_signature}}</span>
    <span id="sig-value" class="sig-value"></span>
  </div>

  <div class="btns">
    <button id="btn-sign" type="button">{{btn_sign}}</button>
    <button id="btn-verify" type="button" disabled>{{btn_verify}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>

  <div class="result" id="result"></div>

  <details class="params-box">
    <summary>{{lbl_params}}</summary>
    <div id="params-display" class="params-content"></div>
  </details>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.fs-app { display: flex; flex-direction: column; gap: .75rem; }
.setup-row { display: flex; flex-wrap: wrap; gap: .6rem; }
.field { display: flex; flex-direction: column; gap: .2rem; flex: 1 1 140px; }
label { font-weight: 600; font-size: .82rem; color: #444; }
input { padding: .35rem .55rem; border: 1px solid #c0cad4; border-radius: 6px;
        font-size: .95rem; width: 100%; }
.hint-inline { font-size: .75rem; color: #666; }
.steps { display: flex; flex-direction: column; gap: .5rem; }
.step { display: flex; align-items: flex-start; gap: .65rem; padding: .55rem .7rem;
        border: 1px solid #dde4eb; border-radius: 8px; background: #f7f9fb;
        transition: background .2s, border-color .2s; }
.step.active { background: #eaf2ff; border-color: #91b8e8; }
.step.done { background: #eafaf0; border-color: #74c49a; }
.step-num { width: 26px; height: 26px; border-radius: 50%; background: #1d3557; color: #fff;
            font-weight: 700; font-size: .82rem; display: flex; align-items: center;
            justify-content: center; flex-shrink: 0; margin-top: 2px; }
.step-body { flex: 1; }
.step-body strong { font-size: .88rem; color: #1d3557; }
.step-math { font-family: ui-monospace, monospace; font-size: .92rem; color: #333;
             margin-top: .2rem; word-break: break-all; }
.step-note { font-size: .78rem; color: #666; margin-top: .2rem; }
.sig-box { background: #1d3557; color: #fff; border-radius: 8px; padding: .5rem .8rem;
           display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
.sig-label { font-weight: 700; font-size: .85rem; flex-shrink: 0; }
.sig-value { font-family: ui-monospace, monospace; font-size: .82rem; word-break: break-all; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px 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; }
button:disabled { opacity: .45; cursor: default; }
.result { font-weight: 600; font-size: .95rem; min-height: 1.3em; }
.result.ok { color: #0a7d33; }
.result.bad { color: #c92f3c; }
.params-box { border: 1px solid #dde4eb; border-radius: 8px; padding: .4rem .7rem; }
summary { cursor: pointer; font-size: .82rem; color: #555; user-select: none; }
.params-content { font-family: ui-monospace, monospace; font-size: .78rem;
                  color: #444; margin-top: .4rem; line-height: 1.7; }

// Code not found

Notice that signing is done entirely by the prover alone: the challenge is computed from the commitment using a hash, so no verifier is needed. Verifying just recomputes the expected commitment from the response and checks the hash. The secret never appears in the signature.

The beauty of Fiat-Shamir hides real subtlety. Here is the landscape:

• Security relies on the hash acting like a random oracle. If $H$ truly outputs independent random values, the transform preserves the soundness of the underlying Σ-protocol. This is the random oracle model (Bellare & Rogaway, 1993).
• It can fail in the standard model. Goldwasser and Kalai (2003) showed that for some Σ-protocols, no concrete hash function can securely replace a truly random oracle — the standard-model security proof breaks.
• The underlying hardness assumption. In the Schnorr signature scheme — the most famous application — the prover's secret is a discrete logarithm. Breaking the scheme requires computing $\log_{g} y \pmod{p}$, which is believed to be hard (the discrete log problem). No polynomial-time algorithm is known.
• Special soundness. A Σ-protocol has special soundness if two accepting transcripts with the same commitment but different challenges let you extract the witness. Fiat-Shamir inherits this: a forger who could produce two valid signatures for the same randomness would expose the secret.
• Fiat-Shamir is not NP-complete. Unlike the puzzles in P vs NP, the transform is a reduction — it maps one problem (interactive proof) to another (signature). Its security lives in the world of cryptographic assumptions, not worst-case complexity.

The bottom line: in the random oracle model, Fiat-Shamir produces tight, provably secure signatures. In the real world, careful choice of hash function and protocol is essential.

The Fiat-Shamir transform is one of the most-deployed ideas in modern cryptography:

• Schnorr signatures: the direct application — compact, fast, and the basis of EdDSA (used in SSH, TLS 1.3, and Signal). Bitcoin's Taproot upgrade adopted Schnorr in 2021.
• zk-SNARKs and zk-STARKs: modern zero-knowledge proof systems compile their interactive verification step through a Fiat-Shamir transform to produce a single non-interactive proof. These power privacy-preserving blockchains (Zcash, StarkNet) and verifiable computation.
• Post-quantum signatures: NIST's post-quantum standardization process selected Dilithium and Falcon — both Fiat-Shamir signatures over lattice-based Σ-protocols, replacing RSA and ECDSA with quantum-resistant alternatives.
• Identification schemes: the original 1986 paper used Fiat-Shamir to build an identification protocol based on factoring — if you can factor, you can break the scheme; otherwise the prover's identity is safe.

Understand Fiat-Shamir and you have the skeleton key to nearly every modern proof system.

The Fiat-Shamir transform is a masterclass in elegant reduction: a three-round conversation collapses to a single message the moment you replace the verifier's coin-flip with a hash. The prover becomes self-sufficient, the interaction disappears, and the resulting object — a non-interactive zero-knowledge proof — can be checked by anyone, anywhere, at any time.

That single substitution is why your SSH key works, why Schnorr signatures fit in 64 bytes, and why blockchains can prove computation without redoing it. The next time you send a signed message, remember: somewhere under the hood, a hash function is standing in for a verifier — and that is, mathematically, one of the cleanest ideas in all of cryptography.