Technical Report PHD-2007-20

Title: Cryptography in Constant Parallel Time
Authors: Benny Applebaum
Supervisors: Yuval Ishai and Eyal Kushilevitz
Abstract: We study the parallel time-complexity of basic cryptographic primitives. 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. In particular, we derive the following results:

1. Existence of cryptographic primitives in NC0. We show that many cryptographic primitives can be realized in NC0 under standard intractability assumptions used in cryptography, such as ones related to factoring, discrete logarithm, or lattice problems. This includes one-way functions, pseudorandom generators, symmetric and public key encryption schemes, digital signatures, message authentication schemes (MACs), commitment schemes, collision resistant hash functions and zero-knowledge proofs. Moreover, we provide a compiler that transforms an implementation of a cryptographic primitive in a relatively "high'" complexity class into an NC0 implementation. This compiler is also used to derive new (unconditional) NC0 reductions between different cryptographic primitives. In some cases, no parallel reductions of this type were previously known, even in NC. Interestingly, we get non-black-box reductions.

2. Cryptography with constant input locality. We study the possibility of carrying out cryptographic tasks by functions in which each input bit affects a constant number of output bits, i.e., functions with constant input locality. (Our previous results have only addressed the case of a constant output locality, which does not imply a constant input locality.) We (almost) characterize what cryptographic tasks can be performed with constant input locality. On the negative side, we show that primitives which require some form of non-malleability (such as digital signatures, message authentication, or non-malleable encryption) cannot be realized with constant input locality. On the positive side, assuming the intractability of certain problems from the domain of error correcting codes (namely, hardness of decoding a random linear code or the security of the McEliece cryptosystem), we obtain new constructions of one-way functions, pseudorandom generators, commitments, and semantically-secure public-key encryption schemes whose input locality is constant. Moreover, these constructions also enjoy constant output locality. Therefore, they give rise to cryptographic hardware that has constant-depth, constant fan-in and constant fan-out. As a byproduct, we obtain a pseudorandom generator whose output and input locality are both optimal (namely, 3).

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2007
To the main CS technical reports page

Computer science department, Technion