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:0708.2992 · Physical Review Letters

Quantum Private Queries

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

Published Jun 10, 2008• 217 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.100.230502

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

Secure quantum private information retrieval using phase-encoded queries

Łukasz Olejnik

We propose a quantum solution to the classical private information retrieval (PIR) problem, which allows one to query a database in a private manner. The protocol offers privacy thresholds and allows the user to obtain information from a database in a way that offers the potential adversary, in this model the database owner, no possibility of deterministically establishing the query contents. This protocol may also be viewed as a solution to the symmetrically private information retrieval problem in that it can offer database security (inability for a querying user to steal its contents). Compared to classical solutions, the protocol offers substantial improvement in terms of communication complexity. In comparison with the recent quantum private queries [Phys. Rev. Lett. 100, 230502 (2008)] protocol, it is more efficient in terms of communication complexity and the number of rounds, while offering a clear privacy parameter. We discuss the security of the protocol and analyze its strengths and conclude that using this technique makes it challenging to obtain the unconditional (in the information-theoretic sense) privacy degree; nevertheless, in addition to being simple, the protocol still offers a privacy level. The oracle used in the protocol is inspired both by the classical computational PIR solutions as well as the Deutsch-Jozsa oracle.

Physical Review A•Aug 8, 2011•125 citations

A Quantum Private Query Protocol for Enhancing both User and Database Privacy*

Yi‐Hua Zhou, Xuewei Bai, Lei-Lei Li +2 more

Abstract In order to protect the privacy of query user and database, some QKD-based quantum private query (QPQ) protocols were proposed. Unfortunately some of them cannot resist internal attack from database perfectly; some others can ensure better user privacy but require a reduction of database privacy. In this paper, a novel two-way QPQ protocol is proposed to ensure the privacy of both sides of communication. In our protocol, user makes initial quantum states and derives the key bit by comparing initial quantum state and outcome state returned from database by ctrl or shift mode instead of announcing two non-orthogonal qubits as others which may leak part secret information. In this way, not only the privacy of database be ensured but also user privacy is strengthened. Furthermore, our protocol can also realize the security of loss-tolerance, cheat-sensitive, and resisting JM attack etc.

Communications in Theoretical Physics•Jan 1, 2018•8 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

Coding-based quantum private database query using entanglement

Fang Yu, Daowen Qiu

We propose an efficient coding-based quantum protocol which uses entanglement to help a user retrieve one out of $N$ items from a database without revealing which one he/she is interested in. The query is accomplished through an encoding-decoding process with the support of a database-specific unitary operation. For each query, $O(logN)$ time is needed for communication and no more than one bit of information about the database can be learnt by even a dishonest user. We prove rigorously that the protocol is secure against a dishonest database which causes little deviation on the original system. A theorem quantitatively describes the tradeoff between information and disturbance in such a setting. Examples are given to illustrate that both coding-based quantum private database query protocols proposed so far, including ours and Olejnik's, are insecure against dishonest databases which are free to cause deviations. Compared to Olejnik's protocol, which utilizes superposed states rather than entanglement, our protocol can prevent a dishonest-but-conscientious database, which tries to provide the user right answers to his/her queries while eavesdropping, from learning significant information when it evaded his/her detection. Finally, for the purpose of enhancing user privacy, two extensions of the protocol are proposed and discussed.

Quantum Information and Computation•Jan 1, 2014•17 citations
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.
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.
We propose a quantum solution to the classical private information retrieval (PIR) problem, which allows one to query a database in a private manner. The protocol offers privacy thresholds and allows the user to obtain information from a database in a way that offers the potential adversary, in this model the database owner, no possibility of deterministically establishing the query contents. This protocol may also be viewed as a solution to the symmetrically private information retrieval problem in that it can offer database security (inability for a querying user to steal its contents). Compared to classical solutions, the protocol offers substantial improvement in terms of communication complexity. In comparison with the recent quantum private queries [Phys. Rev. Lett. 100, 230502 (2008)] protocol, it is more efficient in terms of communication complexity and the number of rounds, while offering a clear privacy parameter. We discuss the security of the protocol and analyze its strengths and conclude that using this technique makes it challenging to obtain the unconditional (in the information-theoretic sense) privacy degree; nevertheless, in addition to being simple, the protocol still offers a privacy level. The oracle used in the protocol is inspired both by the classical computational PIR solutions as well as the Deutsch-Jozsa oracle.
Abstract In order to protect the privacy of query user and database, some QKD-based quantum private query (QPQ) protocols were proposed. Unfortunately some of them cannot resist internal attack from database perfectly; some others can ensure better user privacy but require a reduction of database privacy. In this paper, a novel two-way QPQ protocol is proposed to ensure the privacy of both sides of communication. In our protocol, user makes initial quantum states and derives the key bit by comparing initial quantum state and outcome state returned from database by ctrl or shift mode instead of announcing two non-orthogonal qubits as others which may leak part secret information. In this way, not only the privacy of database be ensured but also user privacy is strengthened. Furthermore, our protocol can also realize the security of loss-tolerance, cheat-sensitive, and resisting JM attack etc.
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).
We propose an efficient coding-based quantum protocol which uses entanglement to help a user retrieve one out of NNN items from a database without revealing which one he/she is interested in. The query is accomplished through an encoding-decoding process with the support of a database-specific unitary operation. For each query, O(logN)O(logN)O(logN) time is needed for communication and no more than one bit of information about the database can be learnt by even a dishonest user. We prove rigorously that the protocol is secure against a dishonest database which causes little deviation on the original system. A theorem quantitatively describes the tradeoff between information and disturbance in such a setting. Examples are given to illustrate that both coding-based quantum private database query protocols proposed so far, including ours and Olejnik's, are insecure against dishonest databases which are free to cause deviations. Compared to Olejnik's protocol, which utilizes superposed states rather than entanglement, our protocol can prevent a dishonest-but-conscientious database, which tries to provide the user right answers to his/her queries while eavesdropping, from learning significant information when it evaded his/her detection. Finally, for the purpose of enhancing user privacy, two extensions of the protocol are proposed and discussed.