Colloquium Details
How to Do Cryptography Even When Cryptography Doesn't Exist
Speaker: Marshall Ball, University of Washington
Location: Online
Date: March 25, 2021, 10 a.m.
Host: Yevgeniy Dodis
Synopsis:
Cryptographic protocols and primitives are an integral part of the backbone of modern infrastructure. However, despite cryptography's ubiquitous use, we have not yet succeeded in unconditionally proving the existence of classical cryptographic primitives, such as symmetric key or public key encryption! One explanation for this failure is that classical cryptography implies that P does not equal NP, a Millenium Prize Problem beyond current techniques. However, even if P does not equal NP, it is still plausible that classical cryptography does not exist. If classical cryptography is impossible, do we have any hope of recovering some notion of security in a formal sense?
In this talk, I will show how to recover meaningful cryptographic guarantees that rest on robust, worst-case conjectures in computational complexity theory (incomparable to classical cryptography). This gives new sources of cryptographic hardness In particular, I will show how to construct Proofs of Work, enabling a user to prove they have expended computational resources, simply assuming the worst-case hardness of certain problems in Fine-Grained Complexity (All-Pairs Shortest Paths, 3SUM, Orthogonal Vectors, etc). Proof of Work schemes are an essential ingredient in Bitcoin and related protocols in permissionless distributed computing. I will also discuss tamper resilience and secure communication, even in a world where classical cryptography is impossible.
Speaker Bio:
Marshall Ball is a Computing Innovation Postdoctoral Fellow at University of Washington, hosted by Huijia Lin and Stefano Tessaro. His research interests lie in the intersection of Cryptography and Computational Complexity, particularly in understanding the nature of computational hardness. He received his PhD from Columbia University under Tal Malkin, supported in part by an IBM PhD Fellowship. Prior to that he worked in the art world for a number of years after receiving his BA from Wesleyan University.