Fine-Grained Cryptography

摘要

Fine-grained cryptographic primitives are ones that are secure against adversaries with an a-priori bounded polynomial amount of 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 (Hastad, IPL 1987). Our goal is come up with fine-grained primitives (in the setting of parallel-time-bounded adversaries) and to show unconditional security of these constructions when possible, or base security on widely believed separation of worst-case complexity classes. We show: 1. NC~1-cryptography: Under the assumption that NC~1 ≠ {direct+}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 non-black-box use of randomized encodings for logspace classes. 2. AC~0-cryptography: We construct (unconditionally secure) pseudorandom generators with arbitrary polynomial stretch, weak pseudorandom functions, secret-key encryption and perhaps most interestingly, 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 Hastad and Braverman.