Paper 2016/580

Fine-grained Cryptography

Akshay Degwekar, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan

Abstract

Fine-grained cryptographic primitives are ones that are secure against adversaries with a-priori bounded polynomial resources (time, space or parallel-time), where the honest algorithms use less resources than the adversaries they are designed to fool. Such primitives were previously studied in the context of time-bounded adversaries (Merkle, CACM 1978), space-bounded adversaries (Cachin and Maurer, CRYPTO 1997) and parallel-time-bounded adversaries (Håstad, IPL 1987). Our goal is to show unconditional security of these constructions when possible, or base security on widely believed separation of worst-case complexity classes. We show: NC$^1$-cryptography: Under the assumption that NC$^1 \neq \oplus$L/poly, we construct one-way functions, pseudo-random generators (with sub-linear stretch), collision-resistant hash functions and most importantly, public-key encryption schemes, all computable in NC$^1$ and secure against all NC$^1$ circuits. Our results rely heavily on the notion of randomized encodings pioneered by Applebaum, Ishai and Kushilevitz, and crucially, make {\em non-black-box} use of randomized encodings for logspace classes. AC$^0$-cryptography: We construct (unconditionally secure) pseudo-random generators with arbitrary polynomial stretch, weak pseudo-random functions, secret-key encryption and perhaps most interestingly, {\em collision-resistant hash functions}, computable in AC$^0$ and secure against all AC^$0$ circuits. Previously, one-way permutations and pseudo-random generators (with linear stretch) computable in AC$^0$ and secure against AC$^0$ circuits were known from the works of Håstad and Braverman.

Note: Full version.