Three Cryptographic Primitives and Their Limits

▶ Watch (1:49)

Public key encryption, symmetric key schemes like AES, and digital signatures form the foundation of secure communication. Encryption protects confidentiality. Signatures provide integrity and authentication. TLS, Signal, and most applications use these primitives today. But these tools cannot simultaneously hide data and prove its correctness. A user sharing a passport for age verification reveals their full identity, birth date and address, when the server only needs a binary answer: over 18 or not.

Zero-Knowledge Proofs: Correctness, Soundness, and Privacy

▶ Watch (9:19)

Zero-knowledge proofs are interactive protocols between a prover and a verifier. The prover holds a secret witness, for example a passport proving age. Three properties are required. Correctness: an honest prover with the witness succeeds. Soundness: a cheater without the witness cannot convince the verifier. Zero-knowledge: the verifier learns nothing beyond the statement’s truth. The verifier knows the user is over 18 but learns nothing else about the passport. Goldwasser, Micali, and Rackoff introduced this concept in a 1985 paper and later won the Gödel Prize.

Quantum-Safe Signatures from Zero-Knowledge Proofs

▶ Watch (16:02)

FIPS 204, the ML-DSA signature scheme standardized by NIST, is a zero-knowledge proof. The prover knows secret vectors S1 and S2 with small coefficients. A public matrix multiplied with these vectors produces the public signing key. The protocol samples randomness, sends a commitment, receives a challenge, and returns a response. Verification checks an equation. Converting this interactive proof into a signature uses the Fiat-Shamir transform: hash the commitment and message to produce the challenge. The result is a single message signature tied to a code update or ciphertext.

Anonymous Credentials with Unlinkable Tokens

▶ Watch (27:32)

The Norwegian contact tracing app used zero-knowledge proofs to unlink positive test tokens from user identities. A user with a positive test received a signed certificate from a national verification service. The app randomized this certificate exactly once, producing a new valid token unlinkable to the original. A zero-knowledge proof confirmed the token was properly signed without revealing the user’s identity. This prevented spam while preserving privacy. For general anonymous credentials, a user can log into the same service 10 times and each proof looks like a different person.

Succinct Zero-Knowledge Arguments

▶ Watch (33:42)

ZK-SNARKs are zero-knowledge succinct non-interactive arguments of knowledge. The proof is small and fast to verify. Some systems produce constant-size proofs of 1 kilobyte regardless of statement complexity. Verification takes milliseconds even if proof generation took hours. This shifts computation to the prover. A powerful server can prove a statement about a machine learning model that would not fit on a mobile device, and the phone verifies the proof. NIST is running a standardization process for these proof systems. Open-source libraries such as Baby Snark in Python are designed for educational experimentation.

Notable Quotes

the verifier is convinced that the statement is true, but it doesn’t learn anything whatsoever about the witness that proves that it’s true Tjerand Silde · ▶ Watch (11:37)

it’s as hard to cheat in this protocol as breaking AES or breaking the RSA scheme Tjerand Silde · ▶ Watch (14:43)

you even if you log in to the same service 10 times, for the service side, it looks like 10 different people Tjerand Silde · ▶ Watch (30:43)

no matter what you want to prove in the world, the proof is 1 kilobyte Tjerand Silde · ▶ Watch (35:56)

Key Takeaways

  • Zero-knowledge proofs let verifiers confirm a statement’s truth without seeing the underlying secret data.
  • The ML-DSA post-quantum signature standard (FIPS 204) is built from a zero-knowledge proof of a secret signing key.
  • ZK-SNARKs produce constant 1-kilobyte proofs verified in milliseconds, enabling mobile verification of heavy computations.

About the Speaker

Tjerand Silde is a cryptography researcher focusing on quantum-safe cryptography, privacy-preserving technologies, and secure implementation.