{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/147579"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/147579","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic","abstract":"Interactive proof systems, introduced in a seminal work of Goldwasser, Micali, and Rackoff, have become one of the most powerful and flexible tools in cryptography and computer science at large. They 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 problem studied in this thesis is the following question: Can we remove interaction from interactive proofs? Even though this question sounds almost paradoxical, Fiat and Shamir (1986) proposed (and Blum extended) 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 its security, even for a single non-trivial case. The main goal of this thesis is to give a solid theoretical foundation for the FiatShamir 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 on the notion of correlation intractability, which is a hash function security property requiring that it is computationally infeasible to find pre-specified input-output correlations in the hash function. Using this methodology, we obtain 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.","abstract_html":"Interactive proof systems, introduced in a seminal work of Goldwasser, Micali, and Rackoff, have become one of the most powerful and flexible tools in cryptography and computer science at large. They 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 problem studied in this thesis is the following question: Can we remove interaction from interactive proofs? Even though this question sounds almost paradoxical, Fiat and Shamir (1986) proposed (and Blum extended) 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 its security, even for a single non-trivial case. The main goal of this thesis is to give a solid theoretical foundation for the FiatShamir 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 on the notion of correlation intractability, which is a hash function security property requiring that it is computationally infeasible to find pre-specified input-output correlations in the hash function. Using this methodology, we obtain 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.","abstract_has_math":false,"creators":["Lombardi, Alex"],"institution":"Massachusetts Institute of Technology","degree_name":"Doctoral","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Vaikuntanathan, Vinod"],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-09","date_published":"2022-09","updated_at":"2026-07-22T22:22:06Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/147579","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Vaikuntanathan, Vinod"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Lombardi, Alex"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2023-01-19T19:59:59Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2023-01-19T19:59:59Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-09"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctoral","Doctor of Philosophy"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/147579"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Interactive proof systems, introduced in a seminal work of Goldwasser, Micali, and Rackoff, have become one of the most powerful and flexible tools in cryptography and computer science at large. They 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 problem studied in this thesis is the following question: Can we remove interaction from interactive proofs? Even though this question sounds almost paradoxical, Fiat and Shamir (1986) proposed (and Blum extended) 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 its security, even for a single non-trivial case. The main goal of this thesis is to give a solid theoretical foundation for the FiatShamir 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 on the notion of correlation intractability, which is a hash function security property requiring that it is computationally infeasible to find pre-specified input-output correlations in the hash function. Using this methodology, we obtain 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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic"]}]}],"canonical_facts":{"dc:contributor.advisor":["Vaikuntanathan, Vinod"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Lombardi, Alex"],"dc:date.accessioned":["2023-01-19T19:59:59Z"],"dc:date.available":["2023-01-19T19:59:59Z"],"dc:date.issued":["2022-09"],"dc:description.abstract":["Interactive proof systems, introduced in a seminal work of Goldwasser, Micali, and Rackoff, have become one of the most powerful and flexible tools in cryptography and computer science at large. They 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 problem studied in this thesis is the following question: Can we remove interaction from interactive proofs? Even though this question sounds almost paradoxical, Fiat and Shamir (1986) proposed (and Blum extended) 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 its security, even for a single non-trivial case. The main goal of this thesis is to give a solid theoretical foundation for the FiatShamir 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 on the notion of correlation intractability, which is a hash function security property requiring that it is computationally infeasible to find pre-specified input-output correlations in the hash function. Using this methodology, we obtain 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."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/147579"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic"],"dc:type":["Thesis"],"thesis:degree_name":["Doctoral","Doctor of Philosophy"]},"updated_at":"2026-07-22T22:22:06Z"}