## Cryptography in Constant Parallel Time

### Benny Applebaum, Technion

We study the parallel time-complexity of basic cryptographic primitives
such as one-way functions (OWFs) and pseudorandom generators (PRGs).
Specifically, we consider the possibility of computing instances of
these primitives by NC0 circuits, in which each output bit depends on a
constant number of input bits. Despite previous efforts in this
direction, there has been no convincing theoretical evidence supporting
this possibility, which was posed as an open question in several
previous works.

We essentially settle this question by providing strong evidence for the
possibility of cryptography in NC0. Our main result is that every
"moderately easy" OWF (resp., PRG), say computable in NC1, can be
compiled into a corresponding OWF (resp., low-stretch PRG) in which each
output bit depends on only four input bits. The existence of OWF and PRG
in NC1 is a relatively mild assumption, implied by most number-theoretic
or algebraic intractability assumptions commonly used in cryptography. A
similar compiler can also be obtained for other cryptographic primitives
such as one-way permutations, encryption, signature, commitment, and
collision-resistant hashing.

Our results make use of the machinery of randomizing polynomials, which
was originally motivated by questions in the domain of
information-theoretic secure multiparty computation. By extending this
tool to the computational setting we obtain additional results regarding
NC0 cryptography. In particular, we show that even some relatively
complex cryptographic primitives, including (stateless) symmetric
encryption and digital signatures, are NC0-reducible to a PRG. No
parallel reductions of this type were previously known, even in NC. Our
reductions make a non-black-box use of the underlying PRG.

Joint work with Yuval Ishai and Eyal Kushilevitz (FOCS 2004, CCC 2005)

Gates 4B (opposite 490) Thursday 06/16/05 1630 hrs