Indistinguishability obfuscation, introduced by [Barak et. al. Crypto 2001], aims to compile
programs into unintelligible ones while preserving functionality. It is a fascinating and …

We consider the question of finding the lowest degree L for which L-linear maps suffice to
obtain IO. The current state of the art (Lin, EUROCRYPT'16, CRYPTO'17; Lin and …

Over the past few decades, we have seen a proliferation of advanced cryptographic
primitives with lossy or homomorphic properties built from various assumptions such as …

Let P:{0, 1} k→{0, 1} be a nontrivial k-ary predicate. Consider a random instance of the
constraint satisfaction problem (P) on n variables with Δ n constraints, each being P applied …

We construct an indistinguishability obfuscation (IO) scheme from the sub-exponential
hardness of the decisional linear problem on bilinear groups together with two variants of …

The problem of identifying a planted assignment given a random k-SAT formula consistent
with the assignment exhibits a large algorithmic gap: while the planted solution can always …

We study the complexity of securely evaluating an arithmetic circuit over a finite field F in the
setting of secure two-party computation with semi-honest adversaries. In all existing …

In this work, we study the question of what set of simple-to-state assumptions suffice for
constructing functional encryption and indistinguishability obfuscation (i O), supporting all …

Suppose that you have n truly random bits x=(x 1,…, xn) and you wish to use them to
generate m≫ n pseudorandom bits y=(y 1,…, ym) using a local mapping, ie, each yi should …

We continue the study of locally-computable pseudorandom generators (PRG) G:{0, 1} n-
>{0, 1} m that each of their outputs depend on a small number of d input bits. While it is …