Cryptography with Low Complexity

The efficiency of cryptographic constructions is a fundamental question. Theoretically, it is important to understand how much computational resources are needed to guarantee strong notions of security. Practically, highly efficient schemes are always desirable for real-world applications. More generally, the possibility of cryptography with low complexity has wide applications for problems in computational complexity, combinatorial optimization, and computational learning theory.

In this project we aim to understand what are the minimal computational resources needed to perform different cryptographic tasks. In a nutshell, we suggest to focus on three main objectives. First, we would like to get better understanding of the cryptographic hardness of random local functions. Second, to harness our insights into the hardness of local functions to derive applications in cryptography and computational complexity, with an eye towards improving the efficiency of basic cryptographic building blocks such as pseudorandom functions. Third, to expand our theoretical understanding of garbled circuits, study their limitations, and improve their efficiency.