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.