We describe a method for private database queries using exchange of quantum states with bits encoded in mutually incompatible bases. For technology with limited coherence time, the database vendor can announce the encoding after a suitable delay to allow the user to privately learn one of two items in the database without the ability to also definitely infer the second item. This quantum approach also allows the user to choose to learn other functions of the items, such as the exclusive-or of their bits, but not to gain more information than equivalent to learning one item, on average. This method is especially useful for items consisting of a few bits by avoiding the substantial overhead of conventional cryptographic approaches. 1We describe a method for private database queries using exchange of quantum states with bits encoded in mutually incompatible bases. For technology with limited coherence time, the database vendor can announce the encoding after a suitable delay to allow the user to privately learn one of two items in the database without the ability to also definitely infer the second item. This quantum approach also allows the user to choose to learn other functions of the items, such as the exclusive-or of their bits, but not to gain more information than equivalent to learning one item, on average. This method is especially useful for items consisting of a few bits by avoiding the substantial overhead of conventional cryptographic approaches. 1

Jan 1, 20098 citations

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.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 ComputationJan 1, 201417 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.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.2992Physical Review LettersJun 10, 2008217 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.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 PhysicsJan 1, 20188 citations

Practical quantum private query with better performance in resisting joint-measurement attack

Chun‐Yan Wei, Tian‐Yin Wang, Fei Gao

As a kind of practical protocol, quantum-key-distribution (QKD)-based quantum private queries (QPQs) have drawn lots of attention. However, joint-measurement (JM) attack poses a noticeable threat to the database security in such protocols. That is, by JM attack a malicious user can illegally elicit many more items from the database than the average amount an honest one can obtain. Taking Jacobi et al.'s protocol as an example, by JM attack a malicious user can obtain as many as 500 bits, instead of the expected 2.44 bits, from a ${10}^{4}$ -bit database in one query. It is a noticeable security flaw in theory, and would also arise in application with the development of quantum memories. To solve this problem, we propose a QPQ protocol based on a two-way QKD scheme, which behaves much better in resisting JM attack. Concretely, the user Alice cannot get more database items by conducting JM attack on the qubits because she has to send them back to Bob (the database holder) before knowing which of them should be jointly measured. Furthermore, JM attack by both Alice and Bob would be detected with certain probability, which is quite different from previous protocols. Moreover, our protocol retains the good characters of QKD-based QPQs, e.g., it is loss tolerant and robust against quantum memory attack.As a kind of practical protocol, quantum-key-distribution (QKD)-based quantum private queries (QPQs) have drawn lots of attention. However, joint-measurement (JM) attack poses a noticeable threat to the database security in such protocols. That is, by JM attack a malicious user can illegally elicit many more items from the database than the average amount an honest one can obtain. Taking Jacobi et al.'s protocol as an example, by JM attack a malicious user can obtain as many as 500 bits, instead of the expected 2.44 bits, from a ${10}^{4}$-bit database in one query. It is a noticeable security flaw in theory, and would also arise in application with the development of quantum memories. To solve this problem, we propose a QPQ protocol based on a two-way QKD scheme, which behaves much better in resisting JM attack. Concretely, the user Alice cannot get more database items by conducting JM attack on the qubits because she has to send them back to Bob (the database holder) before knowing which of them should be jointly measured. Furthermore, JM attack by both Alice and Bob would be detected with certain probability, which is quite different from previous protocols. Moreover, our protocol retains the good characters of QKD-based QPQs, e.g., it is loss tolerant and robust against quantum memory attack.

Physical Review AApr 12, 2016140 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.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 AAug 8, 2011125 citations

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.

{10}^{4}

-bit database in one query. It is a noticeable security flaw in theory, and would also arise in application with the development of quantum memories. To solve this problem, we propose a QPQ protocol based on a two-way QKD scheme, which behaves much better in resisting JM attack. Concretely, the user Alice cannot get more database items by conducting JM attack on the qubits because she has to send them back to Bob (the database holder) before knowing which of them should be jointly measured. Furthermore, JM attack by both Alice and Bob would be detected with certain probability, which is quite different from previous protocols. Moreover, our protocol retains the good characters of QKD-based QPQs, e.g., it is loss tolerant and robust against quantum memory attack.