Gödel in Cryptography: Zero-Knowledge for NP With No Interaction, No Setup, and Perfect Soundness

Gödel showed that there are true but unprovable statements. This was bad news for Hilbert, who hoped that every true statement was provable. In this talk, I’ll describe why Gödel’s result is, in fact, good news for cryptography. 

Specifically, Gödel’s result allows for the following strange scenario: a cryptographic system S is insecure, but it is impossible to prove that S is insecure. As I will explain, in this scenario (defined carefully), S is secure for nearly all practical purposes.

Leveraging this idea, we effectively construct — under longstanding assumptions — a classically-impossible cryptographic dream object: “zero-knowledge proofs for NP with no interaction, no setup, and perfect soundness”. As an application, our result lets one give an ordinary mathematical proof that a Sudoku puzzle is solvable without revealing how to solve it. Previously, it was not known how to do this (i.e. how to construct "non-interactive witness hiding proofs").