Thesis Defense: Alex Lombardi : Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic
Speaker
Alex Lombardi
MIT CSAIL Graduate Student
Host
Vinod Vaikuntanathan
CSAIL MIT
One of computer science’s greatest insights has been in understanding the power and versatility of proofs. Nowhere is this more clearly demonstrated than in the Turing Award winning work of Goldwasser, Micali, and Rackoff, which established a radically new conception of proofs that are interactive and randomized.
Since their introduction, interactive proofs have directly led to some of the biggest breakthroughs in theoretical cryptography, complexity, and quantum computation. They are also at the center of a revolution in practical cryptography, particularly in the context of blockchains and cryptocurrencies.
However, despite their importance, our understanding of cryptographic proofs is surprisingly limited. The central question studied in this thesis is as follows:
Can we remove interaction from interactive proofs?
Even though this question sounds paradoxical, Fiat and Shamir (1986) proposed a heuristic methodology for removing interaction from a huge class of interactive proofs. This methodology is ubiquitous and essential for practical applications, but for over thirty years, we had no proof of security for this transformation -- not even for a single non-trivial proof system.
The main goal of this thesis is to give a solid theoretical foundation for the Fiat-Shamir transformation by developing general-purpose tools, techniques, and abstractions for characterizing its security. We propose a two-step methodology for obtaining provable instantiations that relies essentially on the notion of correlation intractability (CI). CI is a hash function security property roughly requiring that it is difficult to find pre-specified input-output correlations in the hash function.
Using this methodology, we obtain (in this thesis) various new results in cryptography, touching on areas such as non-interactive zero knowledge, delegation of computation, the insecurity of parallel repetition, and the cryptographic hardness of computing Nash Equilibria in game theory.
Since their introduction, interactive proofs have directly led to some of the biggest breakthroughs in theoretical cryptography, complexity, and quantum computation. They are also at the center of a revolution in practical cryptography, particularly in the context of blockchains and cryptocurrencies.
However, despite their importance, our understanding of cryptographic proofs is surprisingly limited. The central question studied in this thesis is as follows:
Can we remove interaction from interactive proofs?
Even though this question sounds paradoxical, Fiat and Shamir (1986) proposed a heuristic methodology for removing interaction from a huge class of interactive proofs. This methodology is ubiquitous and essential for practical applications, but for over thirty years, we had no proof of security for this transformation -- not even for a single non-trivial proof system.
The main goal of this thesis is to give a solid theoretical foundation for the Fiat-Shamir transformation by developing general-purpose tools, techniques, and abstractions for characterizing its security. We propose a two-step methodology for obtaining provable instantiations that relies essentially on the notion of correlation intractability (CI). CI is a hash function security property roughly requiring that it is difficult to find pre-specified input-output correlations in the hash function.
Using this methodology, we obtain (in this thesis) various new results in cryptography, touching on areas such as non-interactive zero knowledge, delegation of computation, the insecurity of parallel repetition, and the cryptographic hardness of computing Nash Equilibria in game theory.