CSE Colloquium: Stronger Foundations for Public-Key Cryptography: New Constructions and Barriers

Abstract: Public-key cryptography enables secure communication between two parties who have no shared secret in common. Two fundamental primitives in public-key cryptography are public-key encryption and trapdoor functions. Despite the fundamental nature of both these primitives, the set of cryptographic assumptions currently known to imply trapdoor functions is much more limited than those sufficient for public-key encryption. 

I will describe my work on the first construction of trapdoor functions from the Computational Diffie-Hellman (CDH) assumption. Whether or not CDH implies trapdoor functions had been open for more than 30 years, since the introduction of the Computational Diffie-Hellman assumption in 1978. I will also describe some of the ramifications of the techniques developed in this work. 

In the second part of the talk, I will address the question of whether public-key cryptography may be based on the minimal assumption of one-way functions. I will describe my work that proves a non-blackbox barrier against this goal, extending the classical blackbox impossibility result of Impagliazzo and Rudich (1989). 

Biography: Mohammad Hajiabadi is a postdoctoral researcher in Computer Science at UC Berkeley, working with Sanjam Garg. He received his Ph D in Computer Science at the University of Victoria under Bruce Kapron. He is broadly interested in theoretical and practical aspects of cryptography. More information is available at his webpage https://people.eecs.berkeley.edu/~mdhajiabadi/.