Impossibility of Quantum Private Queries
arXiv:2501.12842 · doi:10.1103/2pd6-j1xf
Abstract
Symmetric private information retrieval is a cryptographic task allowing a user to query a database and obtain exactly one entry without revealing to the owner of the database which element was accessed. The task is a variant of general two-party protocols called one-sided secure function evaluation and is closely related to oblivious transfer. Under the name quantum private queries, quantum protocols have been proposed to solve this problem in a cheat-sensitive way: In such protocols, it is not impossible for dishonest participants to cheat, but they risk detection [V. Giovannetti, S. Lloyd, and L. Maccone, Phys. Rev. Lett. 100, 230502 (2008)]. We give an explicit attack against any cheat-sensitive symmetric private information retrieval protocol, showing that any protocol that is secure for the user cannot have non-trivial security guarantees for the owner of the database.
v2,v3,v4: Minor changes. v5: Updated to the journal-published version; scientific content unchanged, with only minor editorial and stylistic changes. Building on the present proof techniques, arXiv:2405.12121 shows lower bounds for quantum secure function evaluation reductions
References in corpus (13)
- Coding Theorem and Strong Converse for Quantum Channels
- Practical private database queries based on a quantum key distribution protocol
- Quantum private queries
- Degrees of concealment and bindingness in quantum bit commitment protocols
- A quantum protocol for cheat-sensitive weak coin flipping
- Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
- Quantum Private Queries: security analysis
- The Impossibility Of Secure Two-Party Classical Computation
- Possibility, Impossibility and Cheat-Sensitivity of Quantum Bit String Commitment
- Performing private database queries in a real-world environment using a quantum protocol
- Quantum Private Information Retrieval has linear communication complexity
- Impossibility of Growing Quantum Bit Commitments
- Quantum Private Information Retrieval with Sublinear Communication Complexity