This speaker series is made possible by an anonymous charitable donation in memory of cypherpunks and privacy advocates Len Sassaman, Hugh Daniel, Hal Finney, and Caspar Bowden.
View the list of past and upcoming speakers
Average-Case Fine-Grained Hardness, and What To Do With It
Prashant Nalini Vasudevan, MIT
[Download (MP4)] [View on Youtube]
June 16, 2017 10:30am, in DC 2568
Abstract
We present functions that are hard to compute on average for algorithms running in some fixed polynomial time, assuming widely-conjectured worst-case hardness of certain problems from the study of fine-grained complexity.
We discuss the relevance of such average-case hardness to cryptography and present, as an illustration, an outline of a proof-of-work protocol constructed based on the hardness and certain structural properties of our functions.
Joint work with Marshall Ball, Alon Rosen and Manuel Sabin.
Bio
Prashant is a PhD student at MIT; where his advisor is Vinod Vaikuntanathan. He is interested broadly in complexity theory and cryptography, and narrowly in the understanding the fundamentals of complexity-based cryptography, which involves questions like what sorts of functions are useful when they are hard and what generic assumptions are necessary or sufficient to construct various cryptographic objects.
