Introduction

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(commitment∥message)H(\text{commitment} \| \text{message}), where HH 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.

Build the Signature

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

<!-- Fiat-Shamir transform demo: sign with a Sigma-protocol, verify non-interactively -->
<div class="fs-app">
  <section class="setup-row">
    <div class="field">
      <label for="secret">Secret key x</label>
      <input id="secret" type="number" min="1" max="22" value="7" />
      <span class="hint-inline">integer 1–22</span>
    </div>
    <div class="field">
      <label for="message">Message</label>
      <input id="message" type="text" maxlength="40" value="hello" placeholder="any text" />
    </div>
  </section>

  <div class="steps">
    <div class="step" id="step-commit">
      <div class="step-num">1</div>
      <div class="step-body">
        <strong>Commit: prover picks random k, computes R = g^k mod p</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>Challenge: hash of (R, message) — no verifier needed</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>Response: s = (k − e·x) mod (p−1)</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">Signature:</span>
    <span id="sig-value" class="sig-value"></span>
  </div>

  <div class="btns">
    <button id="btn-sign" type="button">Sign</button>
    <button id="btn-verify" type="button" disabled>Verify</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>

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

  <details class="params-box">
    <summary>Group parameters</summary>
    <div id="params-display" class="params-content"></div>
  </details>
</div>

/* Styles for the Fiat-Shamir demo: step indicators and signature box */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fiat-Shamir demo: Schnorr-style signature over Z_p*
// Toy parameters — small enough to inspect, same math as real Schnorr
const P = 23;
const G = 5;
const Q = P - 1; // group order (prime minus 1 for this toy group)

// Modular exponentiation via square-and-multiply
function modpow(base, exp, mod) {
  let result = 1n;
  base = BigInt(base) % BigInt(mod);
  exp = BigInt(exp);
  const m = BigInt(mod);
  while (exp > 0n) {
    if (exp % 2n === 1n) result = result * base % m;
    exp = exp / 2n;
    base = base * base % m;
  }
  return Number(result);
}

// Toy hash: deterministic, NOT cryptographically secure — demo only
function toyHash(commitment, message, modulus) {
  let h = 0;
  const str = commitment + '|' + message;
  for (let i = 0; i < str.length; i++) {
    h = (h * 31 + str.charCodeAt(i)) >>> 0;
  }
  return (h % (modulus - 1)) + 1; // keep challenge in [1, p-1]
}

// Persistent signature state across sign/verify
let currentSig = null;
let currentPublicKey = null;

function getInputs() {
  const x = parseInt(document.getElementById('secret').value, 10);
  const msg = document.getElementById('message').value.trim() || 'hello';
  return { x, msg };
}

function setStepState(id, state) {
  document.getElementById(id).className = 'step ' + state;
}

function setResult(text, cls) {
  const r = document.getElementById('result');
  r.textContent = text;
  r.className = 'result ' + cls;
}

function showParams(x) {
  // Display group parameters and public key
  const y = modpow(G, x, P);
  const lines = [
    fmt('Prime p = %P%', { P: P }),
    fmt('Generator g = %G%', { G: G }),
    fmt('Secret x = %x% (range 1..22)', { x: x }),
    fmt('Public key y = g^x mod p = %G%^%x% mod %P% = %y%', { G: G, x: x, P: P, y: y }),
  ];
  document.getElementById('params-display').innerHTML = lines.join('<br>');
}

function sign() {
  const { x, msg } = getInputs();
  if (isNaN(x) || x < 1 || x > 22) {
    setResult('Secret key must be an integer between 1 and 22.', 'bad');
    return;
  }

  // Step 1: Commit — pick ephemeral k and compute R = g^k mod p
  const k = ((x * 3 + 7) % (Q - 1)) + 1; // deterministic k from secret for demo reproducibility
  const R = modpow(G, k, P); // commitment

  document.getElementById('out-commit').textContent = 'R = g^k mod p = ' + G + '^' + k + ' mod ' + P + ' = ' + R;
  document.getElementById('note-commit').textContent = fmt('Using deterministic k = %k%', { k: k });
  setStepState('step-commit', 'done');

  // Step 2: Challenge — Fiat-Shamir: replace verifier with hash
  const e = toyHash(R, msg, P);
  document.getElementById('out-challenge').textContent = 'e = H(R, "' + msg + '") mod p = ' + e;
  document.getElementById('note-challenge').textContent = 'Hash replaces the verifier’s random coin flip.';
  setStepState('step-challenge', 'done');

  // Step 3: Response — s = (k - e*x) mod (p-1)
  const s = ((k - e * x) % Q + Q) % Q;
  document.getElementById('out-response').textContent = 's = (k - e·x) mod (p-1) = (' + k + ' - ' + e + '·' + x + ') mod ' + Q + ' = ' + s;
  document.getElementById('note-response').textContent = 's hides x: given only (R, e, s) and g^x, you cannot recover x.';
  setStepState('step-response', 'done');

  // Assemble the non-interactive signature (R, e, s)
  currentSig = { R, e, s, msg };
  currentPublicKey = modpow(G, x, P);

  const sigBox = document.getElementById('sig-box');
  document.getElementById('sig-value').textContent = '(R=' + R + ', e=' + e + ', s=' + s + ')';
  sigBox.hidden = false;

  showParams(x);
  document.getElementById('btn-verify').disabled = false;
  setResult('Signed! Now verify — no interaction required.', 'ok');
  console.log('Fiat-Shamir signature produced:', { R, e, s, msg, publicKey: currentPublicKey });
}

function verify() {
  if (!currentSig) return;
  const { R, e, s, msg } = currentSig;
  const y = currentPublicKey;

  // Verification: recompute R’ and check hash without knowing x
  // Formula: R' = g^s · y^e mod p
  const gs = modpow(G, s, P);
  const ye = modpow(y, e, P);
  const Rprime = (gs * ye) % P;
  const ePrime = toyHash(Rprime, msg, P);

  const valid = (Rprime === R) && (ePrime === e);

  document.getElementById('out-commit').textContent +=
    "  " + fmt('|  Verify:  R’ = g^s·y^e mod p = %G%^%s%·%y%^%e% mod %P% = %Rprime%', { G: G, s: s, y: y, e: e, P: P, Rprime: Rprime });

  if (valid) {
    setResult('✓ Valid signature — commitment matches and hash checks out.', 'ok');
    console.log('Verification passed:', { Rprime, ePrime });
  } else {
    setResult('✗ Invalid signature — tampering detected.', 'bad');
    console.log('Verification FAILED:', { Rprime, ePrime, expected_R: R, expected_e: e });
  }
}

function reset() {
  currentSig = null;
  currentPublicKey = null;
  ['step-commit', 'step-challenge', 'step-response'].forEach(id => {
    setStepState(id, '');
    document.getElementById('out-' + id.replace('step-', '')).textContent = '—';
    document.getElementById('note-' + id.replace('step-', '')).textContent = '';
  });
  document.getElementById('sig-box').hidden = true;
  document.getElementById('btn-verify').disabled = true;
  document.getElementById('params-display').textContent = '';
  setResult('', '');
}

document.getElementById('btn-sign').addEventListener('click', sign);
document.getElementById('btn-verify').addEventListener('click', verify);
document.getElementById('btn-reset').addEventListener('click', reset);
Result
Console

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 Real Complexity

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

  • Security relies on the hash acting like a random oracle. If HH 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⁡gy(modp)\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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fiat-shamir/Content licensed under CC BY-NC 4.0.