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

YuFang, QiuDaowen

Published Jan 1, 2014• 0 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 que...
DOI
10.5555/2600498.2600503

Related papers

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

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

Private Database Queries Using Quantum States with Limited Coherence Times

Tad Hogg, Li Zhang

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

•Jan 1, 2009•8 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

Practical private database queries based on a quantum-key-distribution protocol

Markus Jakobi, Christoph Simon, Nicolas Gisin +4 more

Private queries allow a user, Alice, to learn an element of a database held by a provider, Bob, without revealing which element she is interested in, while limiting her information about the other elements. We propose to implement private queries based on a quantum-key-distribution protocol, with changes only in the classical postprocessing of the key. This approach makes our scheme both easy to implement and loss tolerant. While unconditionally secure private queries are known to be impossible, we argue that an interesting degree of security can be achieved by relying on fundamental physical principles instead of unverifiable security assumptions in order to protect both the user and the database. We think that the scope exists for such practical private queries to become another remarkable application of quantum information in the footsteps of quantum key distribution.

arXiv:1002.4360•Physical Review A•Feb 2, 2011•224 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.
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. 1
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.
Private queries allow a user, Alice, to learn an element of a database held by a provider, Bob, without revealing which element she is interested in, while limiting her information about the other elements. We propose to implement private queries based on a quantum-key-distribution protocol, with changes only in the classical postprocessing of the key. This approach makes our scheme both easy to implement and loss tolerant. While unconditionally secure private queries are known to be impossible, we argue that an interesting degree of security can be achieved by relying on fundamental physical principles instead of unverifiable security assumptions in order to protect both the user and the database. We think that the scope exists for such practical private queries to become another remarkable application of quantum information in the footsteps of quantum key distribution.
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.