Gödel in Cryptography: Zero-Knowledge Proofs With No Interaction, No Setup, and Perfect Soundness
Rahul Ilango
VideoAbstract:
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” (I won’t assume you know what this means!). 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.
Bio:
Rahul is a postdoc in theoretical computer science at the Insitute for Advanced Study. Before this, he did his PhD at MIT advised by Ryan Williams. Most of his research is in the field of computational complexity theory, which quantifies the amount of resources — like time and hardware — needed to solve computational tasks, like finding the fastest route from point A to point B on a map.