Zero-Knowledge Proofs, MPC, and Secret Sharing¶
Job: develop the ZK (Σ-protocol / Fiat–Shamir), the MPC (BGW / GMW), the Shamir secret sharing, and the Yao garbled circuits — with the Schnorr Σ / Shamir as the worked example.
Core¶
The ZK and the Σ-protocol¶
| ZK / Σ-protocol / Fiat–Shamir / simulation | Description |
|---|---|
| ZK | completeness, soundness, zero-knowledge (the information theory) |
| Σ-protocol | commit-challenge-response (the number theory) |
| Fiat–Shamir | non-interactive via \(e=H(t,m)\) (the foundations) |
| Simulation | the simulator the ZK (the information theory) |
The MPC and the BGW / GMW¶
| MPC / BGW / GMW | Description |
|---|---|
| MPC | secure multiparty computation (the information theory) |
| BGW | honest majority, the Shamir-based (the information theory) |
| GMW | dishonest majority, the garbled / OT (the information theory) |
The secret sharing and the Shamir¶
| Shamir / \(t\)-of-\(n\) / threshold / polynomial | Description |
|---|---|
| Shamir | \(t\)-of-\(n\) threshold (the polynomial \(p(0)=s\), shares \(p(i)\), the number theory) |
The Garbled circuits and the Yao¶
| Yao / garbled / OT / two-party | Description |
|---|---|
| Yao | garbled circuits, secure two-party (the information theory) |
| OT | oblivious transfer (the information theory) |
See it¶
Schnorr Σ-protocol and the Shamir secret sharing. The Schnorr: the \(\Sigma\)-protocol (the commit \(t=rG\), the challenge \(e\), the response \(s=r+ex\), the verify \(sG=t+eX\), the number theory). The Shamir: the \(t\)-of-\(n\) (the polynomial \(p(0)=s\), the shares \(p(i)\), the reconstruct \(p\) from \(t\) shares, the number theory). The key point: the Schnorr the \(\Sigma\), the Shamir the polynomial.
Check¶
Explain the Schnorr Σ-protocol and the Fiat–Shamir.
The Schnorr \(\Sigma\): the commit \(t=rG\) (the \(r\) random, the \(G\) the generator), the challenge \(e\) (the verifier), the response \(s=r+ex\) (the \(x\) the secret), the verify \(sG=t+eX\) (the \(X=xG\) the public, the number theory). The Fiat–Shamir: the \(e=H(t,m)\) the non-interactive (the hash the challenge, the foundations). The ZK: the simulator (the \(\Sigma\) the HVZK, the information theory). So the Schnorr the \(\Sigma\), the Fiat–Shamir the non-interactive.
Explain the Shamir secret sharing and the MPC (BGW / GMW).
The Shamir: the \(t\)-of-\(n\) (the \(p(0)=s\) the polynomial degree \(t-1\), the shares \(p(i)\), the reconstruct \(p\) from \(t\) shares via Lagrange, the number theory). The BGW: the honest majority (the \(n\ge2t+1\) the Shamir, the information theory). The GMW: the dishonest majority (the \(n\) any, the garbled / OT, the information theory). The Yao: the garbled circuits (the two-party, the information theory). So the Shamir the polynomial, the BGW the honest, the GMW the dishonest.
Pitfalls¶
- The ZK the simulation (the information theory) — the ZK the simulator, the HVZK the honest-verifier.
- The Fiat–Shamir the ROM (the foundations) — the Fiat–Shamir the non-interactive, the ROM the heuristic.
- The Shamir the [number theory] (the polynomial, the number theory) — the Shamir the threshold, the Lagrange.
- The Yao the garbled (the information theory) — the Yao the two-party, the OT.
Refs¶
- Goldreich, Foundations of Cryptography II; the ZK / the MPC
- Shamir, "How to share a secret" (CACM 1979); the secret sharing
- Yao, "Protocols for secure computations" (FOCS 1982); the garbled circuits
- Ben-Or–Goldwasser–Wigderson (BGW, STOC 1988); the MPC
Next¶
Crypto index · Foundations · Lattice & Post-Quantum · Hash & Signatures · Protocols & TLS · Information theory · Number theory