On basing private information retrieval on NP-hardness
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/106093 |
| _version_ | 1811081067643273216 |
|---|---|
| author | Liu, Tianren, Ph. D. Massachusetts Institute of Technology |
| author2 | Vinod Vaikuntanathan. |
| author_facet | Vinod Vaikuntanathan. Liu, Tianren, Ph. D. Massachusetts Institute of Technology |
| author_sort | Liu, Tianren, Ph. D. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016. |
| first_indexed | 2024-09-23T11:41:08Z |
| format | Thesis |
| id | mit-1721.1/106093 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:41:08Z |
| publishDate | 2016 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1060932020-03-31T14:45:02Z On basing private information retrieval on NP-hardness Liu, Tianren, Ph. D. Massachusetts Institute of Technology 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. Cataloged from PDF version of thesis. Includes bibliographical references (pages 17-19). The possibility of basing the security of cryptographic objects on the (minimal) assumption that NP ... BPP is at the very heart of complexity-theoretic cryptography. Most known results along these lines are negative, showing that assuming widely believed complexity-theoretic conjectures, there are no reductions from an NP-hard problem to the task of breaking certain cryptographic schemes. We make progress along this line of inquiry by showing that the security of single-server single-round private information retrieval schemes cannot be based on NP-hardness, unless the polynomial hierarchy collapses. Our main technical contribution is in showing how to break the security of a PIR protocol given an SZK oracle. Our result is tight in terms of both the correctness and the privacy parameter of the PIR scheme. by Tianren Liu. S.M. 2016-12-22T16:28:43Z 2016-12-22T16:28:43Z 2016 2016 Thesis http://hdl.handle.net/1721.1/106093 965383032 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 19 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Liu, Tianren, Ph. D. Massachusetts Institute of Technology On basing private information retrieval on NP-hardness |
| title | On basing private information retrieval on NP-hardness |
| title_full | On basing private information retrieval on NP-hardness |
| title_fullStr | On basing private information retrieval on NP-hardness |
| title_full_unstemmed | On basing private information retrieval on NP-hardness |
| title_short | On basing private information retrieval on NP-hardness |
| title_sort | on basing private information retrieval on np hardness |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/106093 |
| work_keys_str_mv | AT liutianrenphdmassachusettsinstituteoftechnology onbasingprivateinformationretrievalonnphardness |