Colloquium Details
Foundations of Cryptographic Proof Systems
Speaker: Alex Lombardi, MIT
Location: 60 Fifth Avenue 150
Date: March 7, 2022, 2 p.m.
Host: Jinyang Li
Synopsis:
One of computer science's greatest insights has been in understanding
the power and versatility of *proofs*, which were revolutionized in the
1980s to utilize *interaction* as well as other resources such as
randomization and computational hardness. Today, they form the backbone
of both theoretical and practical cryptography and are simultaneously
the source of deep connections to areas such as complexity theory, game
theory, and quantum computation.
In this talk, I will introduce general-purpose tools, techniques, and
abstractions for two key aspects of cryptographic proof systems that
have been poorly understood for decades:
1) Can we remove interaction from interactive proofs? Already in the
1980s, Fiat and Shamir proposed a heuristic *but unproven* methodology
for removing interaction from interactive proofs, which is now
ubiquitous and essential for practical applications. However, it
remained open for over 30 years to prove the security of this
transformation in essentially any setting of interest.
My work on the Fiat-Shamir transform has led to resolutions to many
long-standing open problems, including (i) building non-interactive zero
knowledge proof systems based on lattice cryptography, (ii) establishing
the existence of highly efficient and succinct non-interactive proof
systems, and (iii) demonstrating that foundational protocols from the
80s fail to compose in parallel.
2) Are classical interactive protocols secure against quantum computers?
At its heart, the problem of analyzing and ruling out quantum attacks on
cryptographic protocols is the issue of “rewinding.” The inability to
rewind a quantum attack stems from the no-cloning theorem, a fundamental
property of quantum information. As a result, very few classical
protocols were known to be secure against quantum attacks.
In a recent work, I showed how to overcome these difficulties and settle
many foundational questions on post-quantum cryptographic proof systems.
Our main technique is showing how to efficiently extract certain pieces
of (classical) information from a quantum attacker without disturbing
its internal state.
Speaker Bio:
Alex Lombardi is a graduate student at MIT advised by Vinod
Vaikuntanathan. He is broadly interested in the theoretical foundations
of cryptography with a particular focus on cryptographic proof systems
and post-quantum security.
Notes:
In-person attendance only available to those with active NYU ID cards.