Computer Science Colloquium, 2008-2009

Abstract:

How much computational power is required to perform basic cryptographic tasks?

We will survey a number of recent results on the complexity of basic cryptographic primitives such as one-way functions, pseudorandom generators, encryption schemes and signatures. Specifically, we will consider the possibility of computing instances of these primitives by NC0 functions, in which each output bit depends on only a constant number of input bits. Somewhat surprisingly and unintuitively, it turns out that most cryptographic tasks can be carried out by such simple functions. We will also explore the cryptographic strength of several interesting subclasses of NC0.

On the application side, we will mention new connections between NC0 cryptography and other seemingly unrelated areas such as secure distributed computation, program checking, and hardness of approximation. We will focus on a new public-key encryption scheme whose security is based on two new assumptions: one related to the pseudorandomness of certain simple NC0 generator, and the second based on the hardness of detecting small non-expanding sets in sparse random graphs. Most, if not all, existing constructions of public-key encryption use hardness assumptions with significant algebraic structure. The main advantage of the new scheme is the relatively general and unstructured nature of the new assumptions, which seem qualitatively different than previous ones.

Based on joint works with Yuval Ishai and Eyal Kushilevitz and with Boaz Barak and Avi Wigderson. The talk is self-contained, and does not assume previous background in cryptography.