Zero-knowledge proof

As explained in Real-World Cryptography

A zero-knowledge proof is a cryptographic proof in which a prover demonstrates that a statement is true without revealing the underlying secret information beyond its validity.

A zero-knowledge proof lets a prover demonstrate knowledge of secret information—a witness—without revealing the witness itself. Peggy might prove to Victor that she knows x in Y = g^x, while keeping x private. A useful proof must be complete, so a knowledgeable prover can succeed; sound, so someone without the witness cannot; and zero-knowledge, so the verifier learns nothing about the witness. section 7.2 section 7.2.1

The Schnorr identification protocol builds the idea from a tempting but unsafe first attempt:

• Hide the witness with fresh randomness: compute s = k + x. This appears to conceal x, but revealing k lets Victor recover x as s − k. section 7.2.1
• Hide the randomness in the exponent instead: compute R = g^k. Peggy sends a hidden value s and R; Victor checks whether g^s equals Y × R. section 7.2.1
• Keep the exchange interactive when Victor supplies a challenge. Interactivity adds messages, requires both participants to be online, and can introduce delays. section 7.2.2
• Apply the Fiat–Shamir transformation to replace Victor’s challenge with a hash of the transcript. Including a message turns the resulting non-interactive proof into a cryptographic commitment to that message: a Schnorr signature. section 7.2.2

From website ownership to private computation

Before receiving a certificate, a website must prove to a trusted authority that it controls its domain. The authority signs the website’s public key, and browsers verify that signature when connecting securely. Broader zero-knowledge proofs can hide selected inputs or outputs while proving that a program executed correctly—for example, proving that a Sudoku has a solution without revealing the solution. In cryptocurrencies, they can protect transaction details or compress blockchain history into a small proof. section 7.1.3 section 12.3.4 section 15.3 section 12.3.3

Figure 15.11 General-purpose ZKPs allow a prover to convince a verifier about the integrity of an execution trace (the inputs of a program and the outputs obtained after its execution) while hiding some of the inputs or outputs involved in the computation. An example of this is a prover trying to prove that a sudoku can be solved.

Use the execution-trace diagram to see how a general-purpose proof establishes program integrity while hiding selected inputs or outputs. section 15.3

How Real-World Cryptography covers it

How deep it goes

Builds an interactive Schnorr protocol from a broken masking attempt, then derives non-interactive proofs and general-purpose applications.

Examples

Uses domain ownership, Schnorr’s algebraic protocol, Sudoku, confidential transactions, and fixed-size blockchain-history proofs.

What it assumes

Assumes the discrete logarithm setting and basic signature concepts, while introducing witnesses and proof properties explicitly.

What you can do after

Evaluate how proofs preserve secrecy, distinguish interactive from non-interactive protocols, and recognize applications in signatures and cryptocurrencies.

How it connects

Connects witnesses, discrete logarithms, Schnorr identification, Fiat–Shamir, digital signatures, public-key infrastructure, and cryptocurrencies.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Elliptic Curve Cryptography for DevelopersA zero-knowledge proof is a cryptographic protocol that lets a prover demonstrate that a statement is true or that secret information is known without revealing the secret information itself.
• 

  liveBookmanning.com
  First-Party Data ActivationA cryptographic proof that demonstrates the truth of a statement without revealing the underlying information beyond that fact.

Compare how 3 books explain zero-knowledge proof →

Related concepts

• non-interactive zero-knowledge proofcontrasts with · A non-interactive zero-knowledge proof is a zero-knowledge proof generated and verified without online message exchange between the prover and verifier.
• general-purpose zero-knowledge proofincludes · A zero-knowledge proof system capable of proving the correct execution of general computations or programs, potentially while hiding selected inputs or outputs.
• proof of knowledgekind of · A proof of knowledge is a cryptographic proof in which a prover demonstrates knowledge of a witness satisfying a specified statement.
• cryptocurrencyused by · A cryptocurrency is a digital asset whose ownership and transfers are secured and recorded using cryptographic mechanisms, typically through a distributed ledger.
• bilinear pairinguses · A bilinear pairing is a map from two groups into a third group that preserves the group operation in each argument separately.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.