Average-Case Fine-Grained Hardness, and What To Do With It
Prashant Nalini Vasudevan, MIT
June 16, 2017 10:30am, in DC 2568
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.
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.