Paper 2016/580

Fine-grained Cryptography

Akshay Degwekar, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan


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.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2016
Fine-grained CryptographyPublic Key CryptographyRandomized EncodingsAC0
Contact author(s)
akshayd @ mit edu
2016-06-16: last of 2 revisions
2016-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akshay Degwekar and Vinod Vaikuntanathan and Prashant Nalini Vasudevan},
      title = {Fine-grained Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2016/580},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.