Structure Versus Hardness Through the Obfuscation Lens
Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log, or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardne...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143920 |
| _version_ | 1826214430148395008 |
|---|---|
| author | Bitansky, Nir Degwekar, Akshay Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bitansky, Nir Degwekar, Akshay Vaikuntanathan, Vinod |
| author_sort | Bitansky, Nir |
| collection | MIT |
| description | Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log, or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low (and so-called structured) complexity classes such as NP ∩ coNP or statistical zero-knowledge (SZK). Is this structure really necessary? For some cryptographic primitives, such as one-way permutations and homomorphic encryption, we know that the answer is yes-they imply hard problems in NP∩coNP and SZK, respectively. In contrast, one-way functions do not imply such hard problems, at least not by black-box reductions. Yet, for many basic primitives such as public-key encryption, oblivious transfer, and functional encryption, we do not have any answer. We show that the above primitives, and many others, do not imply hard problems in NP∩coNP or SZK via black-box reductions. In fact, we first show that even the very powerful notion of indistinguishability obfuscation (IO) does not imply such hard problems, and then deduce the same for a large class of primitives that can be constructed from IO. |
| first_indexed | 2024-09-23T16:05:13Z |
| format | Article |
| id | mit-1721.1/143920 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:05:13Z |
| publishDate | 2022 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1439202023-01-10T15:27:34Z Structure Versus Hardness Through the Obfuscation Lens Bitansky, Nir Degwekar, Akshay Vaikuntanathan, Vinod Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log, or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low (and so-called structured) complexity classes such as NP ∩ coNP or statistical zero-knowledge (SZK). Is this structure really necessary? For some cryptographic primitives, such as one-way permutations and homomorphic encryption, we know that the answer is yes-they imply hard problems in NP∩coNP and SZK, respectively. In contrast, one-way functions do not imply such hard problems, at least not by black-box reductions. Yet, for many basic primitives such as public-key encryption, oblivious transfer, and functional encryption, we do not have any answer. We show that the above primitives, and many others, do not imply hard problems in NP∩coNP or SZK via black-box reductions. In fact, we first show that even the very powerful notion of indistinguishability obfuscation (IO) does not imply such hard problems, and then deduce the same for a large class of primitives that can be constructed from IO. 2022-07-21T14:47:06Z 2022-07-21T14:47:06Z 2021 2022-07-21T14:36:51Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/143920 Bitansky, Nir, Degwekar, Akshay and Vaikuntanathan, Vinod. 2021. "Structure Versus Hardness Through the Obfuscation Lens." SIAM Journal on Computing, 50 (1). en 10.1137/17M1136559 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Bitansky, Nir Degwekar, Akshay Vaikuntanathan, Vinod Structure Versus Hardness Through the Obfuscation Lens |
| title | Structure Versus Hardness Through the Obfuscation Lens |
| title_full | Structure Versus Hardness Through the Obfuscation Lens |
| title_fullStr | Structure Versus Hardness Through the Obfuscation Lens |
| title_full_unstemmed | Structure Versus Hardness Through the Obfuscation Lens |
| title_short | Structure Versus Hardness Through the Obfuscation Lens |
| title_sort | structure versus hardness through the obfuscation lens |
| url | https://hdl.handle.net/1721.1/143920 |
| work_keys_str_mv | AT bitanskynir structureversushardnessthroughtheobfuscationlens AT degwekarakshay structureversushardnessthroughtheobfuscationlens AT vaikuntanathanvinod structureversushardnessthroughtheobfuscationlens |