## CryptoDB

### Russell Impagliazzo

#### Publications

Year
Venue
Title
2016
TCC
2014
TCC
2009
TCC
2009
JOFC
2007
CRYPTO
2001
CRYPTO
2001
EPRINT
Informally, an {\em obfuscator} $O$ is an (efficient, probabilistic) compiler'' that takes as input a program (or circuit) $P$ and produces a new program $O(P)$ that has the same functionality as $P$ yet is unintelligible'' in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are based on an interpretation of the unintelligibility'' condition in obfuscation as meaning that $O(P)$ is a virtual black box,'' in the sense that anything one can efficiently compute given $O(P)$, one could also efficiently compute given oracle access to $P$. In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible. We prove this by constructing a family of functions $F$ that are {\em \inherently unobfuscatable} in the following sense: there is a property $\pi : F \rightarrow \{0,1\}$ such that (a) given {\em any program} that computes a function $f\in F$, the value $\pi(f)$ can be efficiently computed, yet (b) given {\em oracle access} to a (randomly selected) function $f\in F$, no efficient algorithm can compute $\pi(f)$ much better than random guessing. We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only {\em approximately} preserve the functionality, and (c) only need to work for very restricted models of computation ($TC_0$). We also rule out several potential applications of obfuscators, by constructing unobfuscatable'' signature schemes, encryption schemes, and pseudorandom function families.
1999
EPRINT
We present a general probabilistic lemma that can be applied to upper bound the advantage of an adversary in distinguishing between two families of functions. Our lemma reduces the task of upper bounding the advantage to that of upper bounding the ratio of two probabilities associated to the adversary, when this ratio is is viewed as a random variable. It enables us to obtain significantly tighter analyses than more conventional methods. In this paper we apply the technique to the problem of PRP to PRF conversion. We present a simple, new construction of a PRF from a PRP that makes only two invocations of the PRP and has insecurity linear in the number of queries made by the adversary. We also improve the analysis of the truncation construction.
1996
EUROCRYPT
1996
JOFC
1988
CRYPTO
1987
CRYPTO

TCC 2008
Crypto 1994
Crypto 1993