Ph.D Thesis | |

Ph.D Student | Applebaum Benny |
---|---|

Subject | Cryptography in Constant Parallel Time |

Department | Department of Computer Science |

Supervisors | PROF. Yuval Ishai |

PROF. Eyal Kushilevitz | |

Full Thesis text |

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).