Structure vs. hardness through the obfuscation lens
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/105578 |
| _version_ | 1811096989276831744 |
|---|---|
| author | Degwekar, Akshay (Akshay Dhananjai) |
| author2 | Vinod Vaikuntanathan. |
| author_facet | Vinod Vaikuntanathan. Degwekar, Akshay (Akshay Dhananjai) |
| author_sort | Degwekar, Akshay (Akshay Dhananjai) |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. |
| first_indexed | 2024-09-23T16:52:34Z |
| format | Thesis |
| id | mit-1721.1/105578 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:52:34Z |
| publishDate | 2016 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1055782019-04-12T17:37:52Z Structure vs. hardness through the obfuscation lens Degwekar, Akshay (Akshay Dhananjai) Vinod Vaikuntanathan. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 71-[77]). Cryptography relies on the computational hardness of structured problems. While one-way functions, the most basic cryptographic object, does not seem to require much structure, as we advance up the ranks into public-key cryptography and beyond, we seem to require that certain structured problems are hard. For example, factoring, quadratic residuosity, discrete logarithms, and approximate shortest and closest vectors in lattices all have considerable algebraic structure. This structure, on the one hand, enables useful applications such as public-key and homomorphic encryption, but on the other, also puts their hardness in question. Their structure is exactly what puts them in low complexity classes such as SZK or NP [set-theoretic intersection symbol] coNP, and is in fact the reason behind (sub-exponential or quantum) algorithms for these problems. The question is whether such structure is inherent in different cryptographic primitives, deeming them inherently easier. We study the relationship between two structured complexity classes, statistical zero-knowledge (SZK) and NP [set-theoretic intersection symbol] coNP, and cryptography. To frame the question in a meaningful way, we rely on the language of black-box constructions and separations. Our results are the following: -- Cryptography vs. Structured Hardness: Our two main results show that there are no black-box constructions of hard problems in SZK or NP [set-theoretic intersection symbol] coNP starting from one of a wide variety of cryptographic primitives such as one-way and trapdoor functions, one-way and trapdoor permutations (in the case of SZK), public-key encryption, oblivious transfer, deniable encryption, functional encryption, and even indistinguishability obfuscation; -- Complexity-theoretic Implications: As a corollary of our result, we show a separation between SZK and NP[set-theoretic intersection symbol]coNP and the class PPAD that captures the complexity of computing Nash Equilibria; and -- Positive Results: We construct collision-resistant hashing from a strong form of SZK-hardness and indistinguishability obfuscation. It was previously known that indistinguishability obfuscation by itself does not imply collision-resistant hashing in a black-box way; we show that it does if one adds SZK-hardness as a "catalyst". Our black-box separations are derived using indistinguishability obfuscation as a "gateway", by first showing a (separation) result for indistinguishability obfuscation and then leveraging on the fact that indistinguishability obfuscation can be used to construct the above variety of cryptographic primitives and hard PPAD instances in a black-box manner. by Akshay Degwekar. S.M. 2016-12-05T19:11:21Z 2016-12-05T19:11:21Z 2016 2016 Thesis http://hdl.handle.net/1721.1/105578 964523120 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 71, 6 unnumbered pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Degwekar, Akshay (Akshay Dhananjai) Structure vs. hardness through the obfuscation lens |
| title | Structure vs. hardness through the obfuscation lens |
| title_full | Structure vs. hardness through the obfuscation lens |
| title_fullStr | Structure vs. hardness through the obfuscation lens |
| title_full_unstemmed | Structure vs. hardness through the obfuscation lens |
| title_short | Structure vs. hardness through the obfuscation lens |
| title_sort | structure vs hardness through the obfuscation lens |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/105578 |
| work_keys_str_mv | AT degwekarakshayakshaydhananjai structurevshardnessthroughtheobfuscationlens |