Computer Science
Cryptography, Security, and Privacy (CrySP) Group

Friday, 16 June 2017 at 2:00PM

** MOVED TO ** Friday, 16 June 2017 at 10:30AM

Average-Case Fine-Grained Hardness, And What To Do With It

Prashant Nalini Vasudevan


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.

This work is joint with Marshall Ball, Alon Rosen and Manuel Sabin.

Bio: Prashant Nalini Vasudevan is a student at MIT, advised by 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