Welcome to the resource topic for 2016/580
Title:
Fine-grained Cryptography
Authors: Akshay Degwekar, Vinod Vaikuntanathan, 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.
ePrint: https://eprint.iacr.org/2016/580
Talk: https://www.youtube.com/watch?v=3JWqm-wuzrE
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .