Zero-Knowledge Proof (ZKP)

If the statement is true, an honest prover can always convince an honest verifier.

• Mechanism: The protocol guarantees that a valid witness (secret input) will pass the verification algorithm with probability 1.
• Practical meaning: A user who actually knows the password, private key, or correct solution will never be falsely rejected.
• Example: In a Sudoku ZKP, if the prover genuinely knows the solution, the verifier's random row/column/box checks will always pass.
• Failure mode: A protocol lacking completeness would reject legitimate users, making it unusable for authentication or identity systems.

If the statement is false, no cheating prover can convince an honest verifier, except with negligible probability.

• Mechanism: The verification challenges are randomized, forcing a dishonest prover to commit to a false claim before seeing the challenge.
• Practical meaning: A malicious actor cannot forge a proof for a statement they don't actually know.
• Computational vs. Statistical Soundness: Computational soundness assumes the prover is polynomially bounded (standard in practice). Statistical soundness holds against unbounded provers (stronger guarantee).
• Soundness error: The probability a cheater succeeds. Typically set to 2^-128 or lower through parallel repetition.

The verifier learns nothing beyond the validity of the statement. No information about the secret witness is leaked.

• Mechanism: A simulator can generate transcripts indistinguishable from real protocol executions without access to the witness, proving no knowledge is transferred.
• Practical meaning: A verifier cannot extract your password, biometric data, or private transaction details from the proof.
• Perfect vs. Computational ZK: Perfect ZK means the simulated and real distributions are identical. Computational ZK means they are computationally indistinguishable.
• Example: In a ZK identity proof, the verifier learns only "this person is over 18" — not their actual birthdate or ID number.

While not one of the three classical properties, succinctness defines modern zk-SNARKs: the proof is small and verification is exponentially faster than re-executing the computation.

• Proof size: Typically a few hundred bytes, regardless of the computation's complexity.
• Verification time: Constant or logarithmic relative to computation size. Ethereum verifies zk-SNARKs in ~500k gas.
• Contrast with classical ZKPs: Early ZKPs required interactive rounds and linear verification time, making them impractical for blockchain scaling.
• Trade-off: Succinctness requires a trusted setup or complex polynomial commitment schemes (e.g., KZG, FRI).

A ZKP where the prover sends a single message to the verifier with no back-and-forth interaction required.

• Mechanism: The Fiat-Shamir heuristic replaces the verifier's random challenges with a cryptographic hash of the prover's commitments, making the protocol non-interactive.
• Practical impact: Enables ZKPs in asynchronous environments like blockchains, email, or file storage where multiple rounds are impractical.
• Common constructions: zk-SNARKs, zk-STARKs, and Bulletproofs are all non-interactive.
• Security model: Requires the Random Oracle Model (ROM) for formal security proofs when using hash-based challenge derivation.

A stronger notion than soundness: the prover demonstrates not just that a statement is true, but that they possess the secret witness.

• Mechanism: An extractor algorithm can recover the witness by rewinding the prover and feeding different challenges (knowledge extractor).
• Distinction: Soundness says "X is true." Proof of Knowledge says "I know the secret that makes X true."
• Practical use: Essential for authentication. Proving "a private key exists" is useless; proving "I know the private key" enables secure login.
• Formal definition: For every prover that convinces the verifier with probability ε, there exists an extractor that outputs the witness in expected time poly(1/ε).

A cryptographic method enabling computation on ciphertext. Unlike ZKPs which prove validity of a computation on private data, HE allows a third party to actually perform the computation on encrypted data without ever decrypting it. The result remains encrypted and can only be decrypted by the data owner. This is critical for privacy-preserving inference where a model processes encrypted user queries.

A protocol distributing computation across multiple parties where no single party sees the others' private inputs. While a ZKP proves a statement about a secret to a verifier, SMPC allows multiple parties to jointly compute a function over their private inputs without revealing them to each other. Often used in privacy-preserving machine learning for collaborative model training across competing organizations.

A mathematical framework injecting calibrated statistical noise into query results to prevent re-identification of individual records. ZKPs prove computational integrity; differential privacy guarantees that the output of an analysis does not leak information about any single individual in the dataset. It is the gold standard for privacy-preserving data analytics and is often combined with ZKPs in verifiable private computation systems.

A hardware-enforced secure area within a main processor that isolates sensitive code and data from the host operating system. Unlike the purely mathematical guarantees of ZKPs, TEEs rely on hardware trust assumptions (e.g., Intel SGX, AMD SEV). They are used for confidential computing to run unmodified applications in an encrypted memory region, providing a complementary approach to software-based cryptographic privacy.

Cryptographic algorithms designed to resist attacks from large-scale quantum computers. Many current ZKP constructions rely on hardness assumptions vulnerable to Shor's algorithm. PQC, particularly lattice-based cryptography and hash-based signatures, is essential for building ZKP systems that remain secure in a post-quantum era. Standardization is being led by NIST.

A protocol allowing a client to retrieve an item from a database server without the server learning which item was accessed. While a ZKP can prove a client is authorized to access a record without revealing which one, PIR hides the access pattern itself. This is vital for encrypted vector databases where a user queries for the nearest neighbor without revealing the query vector or the result index.