Cryptography, Security, and Privacy (CrySP) Group

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