• Calendar

January 19, Tuesday
12:00 – 13:30

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 digital 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. This includes simple forms of natural computation that can be performed by real-world dynamical systems in a constant number of steps. 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 approach for constructing public-key encryption schemes based on the intractability of random NC0 functions. Most, if not all, existing constructions of public-key encryption use hardness assumptions with significant algebraic structure. The main advantage of the new schemes is the relatively general and combinatorial 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.