A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis.

1) Obfuscation can serve as a general-purpose *worst-case to average-case reduction*, reducing the existence of various forms of cryptography to corresponding worst-case assumptions.
2) We can therefore hope to overcome ... more >>>