On Basing Private Information Retrieval on NP-Hardness
© International Association for Cryptologic Research 2016. 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 widel...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137799.2 |
| _version_ | 1811089759591727104 |
|---|---|
| author | Liu, Tianren Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Liu, Tianren Vaikuntanathan, Vinod |
| author_sort | Liu, Tianren |
| collection | MIT |
| description | © International Association for Cryptologic Research 2016. 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 NPhard 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. |
| first_indexed | 2024-09-23T14:24:16Z |
| format | Article |
| id | mit-1721.1/137799.2 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:24:16Z |
| publishDate | 2021 |
| publisher | Springer Nature |
| record_format | dspace |
| spelling | mit-1721.1/137799.22021-12-20T15:15:23Z On Basing Private Information Retrieval on NP-Hardness Liu, Tianren Vaikuntanathan, Vinod Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © International Association for Cryptologic Research 2016. 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 NPhard 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. 2021-12-20T15:15:22Z 2021-11-08T19:35:21Z 2021-12-20T15:15:22Z 2015-12 2019-07-09T16:28:04Z Article http://purl.org/eprint/type/ConferencePaper 0302-9743 1611-3349 https://hdl.handle.net/1721.1/137799.2 Liu, Tianren and Vaikuntanathan, Vinod. 2015. "On Basing Private Information Retrieval on NP-Hardness." en 10.1007/978-3-662-49096-9_16 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/octet-stream Springer Nature Other repository |
| spellingShingle | Liu, Tianren Vaikuntanathan, Vinod 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 |
| url | https://hdl.handle.net/1721.1/137799.2 |
| work_keys_str_mv | AT liutianren onbasingprivateinformationretrievalonnphardness AT vaikuntanathanvinod onbasingprivateinformationretrievalonnphardness |