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-cryptography: Under the assumption that NCL/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 and secure against all NC 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-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 and secure against all AC^ circuits. Previously, one-way permutations and pseudo-random generators (with linear stretch) computable in AC and secure against AC circuits were known from the works of Håstad and Braverman.

Note: Full version.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2016
Keywords
Fine-grained CryptographyPublic Key CryptographyRandomized EncodingsAC0
Contact author(s)
akshayd @ mit edu
History
2016-06-16: last of 2 revisions
2016-06-06: received
See all versions
Short URL
https://ia.cr/2016/580
License
Creative Commons Attribution
CC BY

BibTeX

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