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

Quantum Information and Computation

Coding-based quantum private database query using entanglement

Fang Yu, Daowen Qiu

Published Jan 1, 2014• 17 citations
Publisher

Abstract

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.

DOI
10.26421/qic14.1-2-5

Related papers

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

Coding-based quantum private database query using entanglement

YuFang, QiuDaowen

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 que...

Quantum Information and Computation•Jan 1, 2014•0 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

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

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

Cryptanalysis and improvement to the quantum private query protocol for enhancing database privacy

Zhengda Shen, Wenzhu Shao, Zhigang Li +4 more

Abstract In order to protect the privacy of the query user and database, some QKD-based quantum private query (QPQ) protocols were proposed. One example is the protocol proposed by Zhou et al, in which the user makes initial quantum states and derives the key bit by comparing the initial quantum state and the outcome state returned from the database by ctrl or shift mode, instead of announcing two non-orthogonal qubits as others which may leak part secret information. To some extent, the security of the database and the privacy of the user are strengthened. Unfortunately, we find that in this protocol, the dishonest user could be obtained, utilizing unambiguous state discrimination, much more database information than that is analyzed in Zhou et al’s original research. To strengthen the database security, we improved the mentioned protocol by modifying the information returned by the database in various ways. The analysis indicates that the security of the improved protocols is greatly enhanced.

Communications in Theoretical Physics•Nov 26, 2024•0 citations
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.
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 the query user and database, some QKD-based quantum private query (QPQ) protocols were proposed. One example is the protocol proposed by Zhou et al, in which the user makes initial quantum states and derives the key bit by comparing the initial quantum state and the outcome state returned from the database by ctrl or shift mode, instead of announcing two non-orthogonal qubits as others which may leak part secret information. To some extent, the security of the database and the privacy of the user are strengthened. Unfortunately, we find that in this protocol, the dishonest user could be obtained, utilizing unambiguous state discrimination, much more database information than that is analyzed in Zhou et al’s original research. To strengthen the database security, we improved the mentioned protocol by modifying the information returned by the database in various ways. The analysis indicates that the security of the improved protocols is greatly enhanced.