Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2501.12842 · Physical Review Research

Impossibility of quantum private queries

Esther Hänggi, Severin Winkler

Published Apr 3, 2026• 0 citations
arXivHTMLPDF

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 and is closely related to oblivious transfer. Under the name , 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 [Giovannetti , ]. 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 nontrivial security guarantees for the owner of the database: The user is even able to retrieve the database.

DOI
10.1103/2pd6-j1xf

Related papers

Quantum Private Queries: Security Analysis

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

A security analysis of the recently introduced Quantum Private Query (QPQ) protocol is presented. The latter is a cheat sensitive quantum protocol to perform a private search on a classical database. It allows a user to retrieve an item from the database without revealing which item was retrieved, and at the same time it ensures data privacy of the database (the information that the user retrieves in a query is bounded). The security analysis is based on information-disturbance tradeoffs which show that whenever the provider tries to obtain information on the query, the query (encoded into a quantum system) is disturbed so that the person querying the database can detect the privacy violation. The security bounds are derived under the assumption that a unique answer corresponds to each query. To remove this assumption, some simple variants of the protocol are illustrated, and it is conjectured that analogous security bounds apply to them.

arXiv:0809.1934•IEEE Transactions on Information Theory•Jun 23, 2010•83 citations

Quantum Private Queries: Security Analysis

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

A security analysis of the recently introduced Quantum Private Query (QPQ) protocol is presented. The latter is a cheat sensitive quantum protocol to perform a private search on a classical database. It allows a user to retrieve an item from the database without revealing which item was retrieved, and at the same time it ensures data privacy of the database (the information that the user retrieves in a query is bounded). The security analysis is based on information-disturbance tradeoffs which show that whenever the provider tries to obtain information on the query, the query (encoded into a quantum system) is disturbed so that the person querying the database can detect the privacy violation. The security bounds are derived under the assumption that a unique answer corresponds to each query. To remove this assumption, some simple variants of the protocol are illustrated, and it is conjectured that analogous security bounds apply to them.

•Aug 1, 2009•51 citations

How Bob in Quantum Private Query Protocol Gets the Element?

Bingren Chen, Lide Xue, Wei Yang +1 more

Quantum private query (QPQ) requires that the database holder Bob knows nothing about his client Alice, including the index she provides and the element she obtains. However, on some occasion, Bob wants to know which element he has revealed to Alice. Therefore, we raise a symmetric quantum private query (SQPQ) problem in this paper. SQPQ can guarantee that Alice shares the real element with Bob and also partially protect the privacy of Alice's index. Some necessary conditions are need to satisfy to implement SQPQ. We prove that Alice must provide some extra information to enable Bob to know the element. Then, we define the term “absolutely secure”, which is a security notion stronger than cheat sensitive, and prove that “absolutely secure”SQPQ is impossible. In addition, we raise a cheat sensitive scheme three-databases-detection to implement SQPQ protocol. Finally, we construct a reduction from SQPQ to quantum bit commitment (QBC) to clarify that SQPQ is a problem more difficult than QBC.

IEEE Access•Jan 1, 2019•0 citations

Performing private database queries in a real-world environment using a quantum protocol

Philip Chan, I. Lucio-Martinez, Xiaofan Mo +2 more

Private query protocols [1-3] use uncertainty in quantum mechanics to offer functionality similar to 1-out-of-N oblivious transfer (where a user, Ursula, retrieves a single element from a database provider, Dave, who learns nothing about which of the N elements was retrieved). The difference in functionality varies for each private query protocol, but in all cases is motivated by the fact that perfect 1-out-of-N oblivious transfer has been shown to be impossible if the attacker possess an arbitrarily powerful quantum computer [4]. Nonetheless, quantum protocols can offer security against stronger adversaries than protocols relying only on classical information, and it remains an interesting question as to what level of security can be achieved using quantum information. We present a proof-of-principle demonstration of a novel private query protocol that is loss- and fault-tolerant, making it suitable for implementation in a real-world environment, and show that it offers excellent privacy against several quantum attacks [5]. This demonstration is performed over a deployed fibre link between the University of Calgary and SAIT Polytechnic using a slightly modified quantum key distribution (QKD) system [6]. Oblivious transfer (OT) is a well studied primitive in classical information theory, and protocols

•Jan 8, 2014•43 citations

Quantum Private Queries

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

We propose a cheat sensitive quantum protocol to perform a private search on a classical database which is efficient in terms of communication complexity. It allows a user to retrieve an item from the database provider without revealing which item he or she retrieved: if the provider tries to obtain information on the query, the person querying the database can find it out. The protocol ensures also perfect data privacy of the database: the information that the user can retrieve in a single query is bounded and does not depend on the size of the database. With respect to the known (quantum and classical) strategies for private information retrieval, our protocol displays an exponential reduction in communication complexity and in running-time computational complexity.

arXiv:0708.2992•Physical Review Letters•Jun 10, 2008•217 citations

Reexamination of the realtime protection for user privacy in practical quantum private query

Chun‐Yan Wei, Xiao‐Qiu Cai, Tian‐Yin Wang

Abstract Quantum private query (QPQ) is the quantum version for symmetrically private information retrieval. However, the user privacy in QPQ is generally guarded in the delayed and cheat-sensitive way. That is, the dishonest database holder Bob’s cheating to elicit user privacy can only be discovered after the protocol is finished (when the user finds some errors in the retrieved database item). Such delayed detection may cause very unpleasant results for the user Alice in real-life applications. Without the realtime conscious of privacy leaking, Alice may make faulty decisions according to the received faulty item and suffer great loss. Worse yet, it is difficult for Alice to accuse a dishonest database to any one else though she can detect the cheating. Current efforts to protect user privacy in realtime in existing QPQ protocols mainly use two techniques, i.e. adding an honesty checking on the database or allowing the user to reorder the qubits. We reexamine these two kinds of QPQ protocols and find neither of them can work very well. We give concrete cheating strategies for both participants and show that honesty checking of inner participant should be dealt more carefully in for example the choosing of checking qubits. Finally, we give an idea to realize realtime detection of dishonest database in QPQ of blocks (i.e. multi-bit database items).

arXiv:2407.19147•Physica Scripta•Nov 18, 2024•1 citation
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 and is closely related to oblivious transfer. Under the name , 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 [Giovannetti , ]. 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 nontrivial security guarantees for the owner of the database: The user is even able to retrieve the database.
A security analysis of the recently introduced Quantum Private Query (QPQ) protocol is presented. The latter is a cheat sensitive quantum protocol to perform a private search on a classical database. It allows a user to retrieve an item from the database without revealing which item was retrieved, and at the same time it ensures data privacy of the database (the information that the user retrieves in a query is bounded). The security analysis is based on information-disturbance tradeoffs which show that whenever the provider tries to obtain information on the query, the query (encoded into a quantum system) is disturbed so that the person querying the database can detect the privacy violation. The security bounds are derived under the assumption that a unique answer corresponds to each query. To remove this assumption, some simple variants of the protocol are illustrated, and it is conjectured that analogous security bounds apply to them.
A security analysis of the recently introduced Quantum Private Query (QPQ) protocol is presented. The latter is a cheat sensitive quantum protocol to perform a private search on a classical database. It allows a user to retrieve an item from the database without revealing which item was retrieved, and at the same time it ensures data privacy of the database (the information that the user retrieves in a query is bounded). The security analysis is based on information-disturbance tradeoffs which show that whenever the provider tries to obtain information on the query, the query (encoded into a quantum system) is disturbed so that the person querying the database can detect the privacy violation. The security bounds are derived under the assumption that a unique answer corresponds to each query. To remove this assumption, some simple variants of the protocol are illustrated, and it is conjectured that analogous security bounds apply to them.
Quantum private query (QPQ) requires that the database holder Bob knows nothing about his client Alice, including the index she provides and the element she obtains. However, on some occasion, Bob wants to know which element he has revealed to Alice. Therefore, we raise a symmetric quantum private query (SQPQ) problem in this paper. SQPQ can guarantee that Alice shares the real element with Bob and also partially protect the privacy of Alice's index. Some necessary conditions are need to satisfy to implement SQPQ. We prove that Alice must provide some extra information to enable Bob to know the element. Then, we define the term “absolutely secure”, which is a security notion stronger than cheat sensitive, and prove that “absolutely secure”SQPQ is impossible. In addition, we raise a cheat sensitive scheme three-databases-detection to implement SQPQ protocol. Finally, we construct a reduction from SQPQ to quantum bit commitment (QBC) to clarify that SQPQ is a problem more difficult than QBC.
Private query protocols [1-3] use uncertainty in quantum mechanics to offer functionality similar to 1-out-of-N oblivious transfer (where a user, Ursula, retrieves a single element from a database provider, Dave, who learns nothing about which of the N elements was retrieved). The difference in functionality varies for each private query protocol, but in all cases is motivated by the fact that perfect 1-out-of-N oblivious transfer has been shown to be impossible if the attacker possess an arbitrarily powerful quantum computer [4]. Nonetheless, quantum protocols can offer security against stronger adversaries than protocols relying only on classical information, and it remains an interesting question as to what level of security can be achieved using quantum information. We present a proof-of-principle demonstration of a novel private query protocol that is loss- and fault-tolerant, making it suitable for implementation in a real-world environment, and show that it offers excellent privacy against several quantum attacks [5]. This demonstration is performed over a deployed fibre link between the University of Calgary and SAIT Polytechnic using a slightly modified quantum key distribution (QKD) system [6]. Oblivious transfer (OT) is a well studied primitive in classical information theory, and protocols
We propose a cheat sensitive quantum protocol to perform a private search on a classical database which is efficient in terms of communication complexity. It allows a user to retrieve an item from the database provider without revealing which item he or she retrieved: if the provider tries to obtain information on the query, the person querying the database can find it out. The protocol ensures also perfect data privacy of the database: the information that the user can retrieve in a single query is bounded and does not depend on the size of the database. With respect to the known (quantum and classical) strategies for private information retrieval, our protocol displays an exponential reduction in communication complexity and in running-time computational complexity.
Abstract Quantum private query (QPQ) is the quantum version for symmetrically private information retrieval. However, the user privacy in QPQ is generally guarded in the delayed and cheat-sensitive way. That is, the dishonest database holder Bob’s cheating to elicit user privacy can only be discovered after the protocol is finished (when the user finds some errors in the retrieved database item). Such delayed detection may cause very unpleasant results for the user Alice in real-life applications. Without the realtime conscious of privacy leaking, Alice may make faulty decisions according to the received faulty item and suffer great loss. Worse yet, it is difficult for Alice to accuse a dishonest database to any one else though she can detect the cheating. Current efforts to protect user privacy in realtime in existing QPQ protocols mainly use two techniques, i.e. adding an honesty checking on the database or allowing the user to reorder the qubits. We reexamine these two kinds of QPQ protocols and find neither of them can work very well. We give concrete cheating strategies for both participants and show that honesty checking of inner participant should be dealt more carefully in for example the choosing of checking qubits. Finally, we give an idea to realize realtime detection of dishonest database in QPQ of blocks (i.e. multi-bit database items).