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 st...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer
2017
|
| Online Access: | http://hdl.handle.net/1721.1/111069 https://orcid.org/0000-0002-8354-0621 https://orcid.org/0000-0002-2666-0045 https://orcid.org/0000-0002-0522-7023 |
| _version_ | 1826202632181514240 |
|---|---|
| author | Degwekar, Akshay Dhananjai Vaikuntanathan, Vinod Vasudevan, Prashant |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Degwekar, Akshay Dhananjai Vaikuntanathan, Vinod Vasudevan, Prashant |
| author_sort | Degwekar, Akshay Dhananjai |
| collection | MIT |
| description | 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 (Håstad, 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¹-cryptography: Under the assumption that Open image in new window, 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 non-black-box use of randomized encodings for logspace classes.
2. AC⁰-cryptography: We construct (unconditionally secure) pseudo-random generators with arbitrary polynomial stretch, weak pseudo-random functions, secret-key encryption and perhaps most interestingly, 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. |
| first_indexed | 2024-09-23T12:12:05Z |
| format | Article |
| id | mit-1721.1/111069 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:12:05Z |
| publishDate | 2017 |
| publisher | Springer |
| record_format | dspace |
| spelling | mit-1721.1/1110692022-10-01T08:41:08Z Fine-Grained Cryptography Degwekar, Akshay Dhananjai Vaikuntanathan, Vinod Vasudevan, Prashant Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Degwekar, Akshay Dhananjai Vaikuntanathan, Vinod Vasudevan, Prashant 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 (Håstad, 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¹-cryptography: Under the assumption that Open image in new window, 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 non-black-box use of randomized encodings for logspace classes. 2. AC⁰-cryptography: We construct (unconditionally secure) pseudo-random generators with arbitrary polynomial stretch, weak pseudo-random functions, secret-key encryption and perhaps most interestingly, 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. United States. Defense Advanced Research Projects Agency (Contract W911NF-15-C-0226) United States. Army Research Office (Contract W911NF-15-C-0226) 2017-08-30T17:35:22Z 2017-08-30T17:35:22Z 2017-08-30 Article http://purl.org/eprint/type/ConferencePaper 978-3-662-53014-6 978-3-662-53015-3 0302-9743 1611-3349 http://hdl.handle.net/1721.1/111069 Degwekar, Akshay et al. “Fine-Grained Cryptography.” Advances in Cryptology – CRYPTO 2016. Lecture Notes in Computer Science 9816 (2016): 533–562. © 2016 International Association for Cryptologic Research https://orcid.org/0000-0002-8354-0621 https://orcid.org/0000-0002-2666-0045 https://orcid.org/0000-0002-0522-7023 en_US http://dx.doi.org/10.1007/978-3-662-53015-3_19 Advances in Cryptology – CRYPTO 2016 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer MIT Web Domain |
| spellingShingle | Degwekar, Akshay Dhananjai Vaikuntanathan, Vinod Vasudevan, Prashant Fine-Grained Cryptography |
| title | Fine-Grained Cryptography |
| title_full | Fine-Grained Cryptography |
| title_fullStr | Fine-Grained Cryptography |
| title_full_unstemmed | Fine-Grained Cryptography |
| title_short | Fine-Grained Cryptography |
| title_sort | fine grained cryptography |
| url | http://hdl.handle.net/1721.1/111069 https://orcid.org/0000-0002-8354-0621 https://orcid.org/0000-0002-2666-0045 https://orcid.org/0000-0002-0522-7023 |
| work_keys_str_mv | AT degwekarakshaydhananjai finegrainedcryptography AT vaikuntanathanvinod finegrainedcryptography AT vasudevanprashant finegrainedcryptography |