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:2610.04359

A Cheat-Sensitive Primitive for Destination-Private Quantum Routing

S. F. E. Oliviero, S. Onofri, V. Giovannetti

quant-phcs.CRSubmitted Oct 3, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum networks will rely on intermediate nodes to distribute entanglement, but the same nodes may learn which users are being connected. We introduce a minimal two-call routing primitive in which a user, Alice, establishes an entangled link with one of several clients while testing whether the provider, Bob, has disturbed a coherently encoded request. The construction adapts the hidden-order mechanism of quantum private queries: one call contains a direct request, the other a coherent superposition of the desired and null addresses, and Alice keeps their order secret. A private matching qubit held by the selected client restores the coherent test state after a favorable Bell-measurement outcome, so that Alice can test the returned query without any further operation by Bob. The claim is deliberately limited. The protocol shows that a routing request can carry a physical cheating test, and it detects an explicit destination-reading attack with nonzero probability. It does not yet provide a quantitative information-disturbance tradeoff, composable security, or certification of an unmeasured output against arbitrary attacks. We also characterize the exact perfect-pass limit, in which Bob's residual state, averaged over the private matching states, is independent of the destination.

AI Summary

Can an untrusted entanglement router learn a requested destination only at the risk of detectable disturbance? This paper adapts the hidden-order mechanism of quantum private queries to a two-call routing primitive. Alice sequentially sends one direct destination request and one coherent superposition of the destination and a null address, hiding their order. Bob’s honest operation is an address-controlled swap using two pre-shared singlets per client. A private matching qubit at the selected client, followed by a favorable Bell-measurement outcome, restores the coherent request so Alice can projectively test it. Honest runs are conclusive with probability $1/4$; conditioned on that herald, the checks pass deterministically and the direct call supplies a singlet. Measuring both query addresses reveals the destination but dephases the trap: detection occurs with probability $1/2$ conditioned on the herald, or $1/8$ per attempt. An exact perfect-pass argument, using sequentiality and linearity, establishes destination independence of Bob’s residual state after averaging over independently sampled private matching states with mean $I/2$. This result assumes that both hidden orders preserve the trap, direct address, and direct singlet exactly. The primitive does not establish a quantitative information–disturbance tradeoff, composable security, or certification of the unmeasured output against arbitrary attacks. It assumes ideal initial singlets, trusted user/client devices, private authenticated classical channels, and fixed-pattern cover traffic. Loss, noise, malicious clients, and repeated destination use are outside its scope; no approximate-pass continuity bound is provided.

Little sign of AI-generated textAI use disclosedIncrementalStrong assumptions
Language models were only used to edit the manuscript. All results were derived by hand by the authors.

Error found: The abstract's perfect-pass destination-privacy statement omits the essential assumption that the retained direct output is an exact singlet, which the protocol's stated acceptance tests do not certify.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum Private Query With Perfect Performance Universally Applicable Against Collective-Noise

Na Li, Jian Li, Xiu‐Bo Chen +1 more

Almost all of the previous quantum private query (QPQ) protocols are always based on an ideal environment without any noise. Nevertheless, due to the defects of the channel, channel noise inevitably exists in the actual transmission process, which will give rise to transmission error and reduce the probability of successful quantum transmission. An eavesdropper may disguise her actions as channel noise to avoid being detected by legitimate parties during security checks. To solve this problem, we present a QPQ protocol with perfect performance universally applicable against collective noise. Concretely, the protocol encodes bits in noiseless subspace and thus can function over a quantum channel subjected to an arbitrary degree of collective noise, as occurs, for instance, due to polarization rotation in an optical fiber. Furthermore, Bob cannot get the information about Alice's choice at all by taking fake entangled attack and by taking fake photon attack, the probability Bob can get the information about Alice's choice is only approximately 6.7%, which is far less than the probability of 25% in Yang et al.'s protocol. Moreover, the conclusiveness of the user Alice's measurement results is subject to quantum randomness rather than allowing Alice to choose by herself to obtain a conclusive result in Wei et al.'s protocol, which prevents Alice's intuitive attack and meanwhile makes it arduous for Bob to perform the joint-measurement attack. Our protocol uses only one state, which reduces the communication complexity, and is, therefore, an effective QPQ solution with the high-security level.

IEEE Access•Jan 1, 2019•11 citations

Impossibility of quantum private queries

Esther Hänggi, Severin Winkler

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.

arXiv:2501.12842•Physical Review Research•Apr 3, 2026•1 citation

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

Practical quantum private query based on Bell state

Tao Zheng, Shibin Zhang, Xiang Gao +1 more

Quantum private query (QPQ) is a cryptographic application that protects the privacy of both users and databases while querying the database secretly. In most existing QPQ protocols, the protection of user privacy can only be cheat-sensitive. Cheat-sensitive means that Bob will be found later with a certain probability if he tries to get the address queried by Alice. On the premise of cheat-sensitivity, although Alice can discover Bob’s malicious behavior after a query (transaction), the secret information of Alice was leaked in the completed query, which is likely to be a fatal blow to Alice. Or, to prevent Bob’s malicious behavior, Alice executes one or more additional queries to test Bob’s honesty. However, to bypass Alice’s honesty test, Bob can also provide several honest queries before performing dishonest queries. Therefore, cheat-sensitive should not be the ultimate goal of user privacy protection in QPQ. In this paper, we propose a practical QKD-based QPQ protocol with better user privacy protection than cheat-sensitivity based on order rearrangement of qubits. The proposed QPQ protocol can resist the Trojan horse attack even without wavelength filter and photon number splitter (PNS) equipped with auxiliary monitoring detectors.

Modern Physics Letters A•Jun 14, 2019•15 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•225 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•88 citations
Quantum networks will rely on intermediate nodes to distribute entanglement, but the same nodes may learn which users are being connected. We introduce a minimal two-call routing primitive in which a user, Alice, establishes an entangled link with one of several clients while testing whether the provider, Bob, has disturbed a coherently encoded request. The construction adapts the hidden-order mechanism of quantum private queries: one call contains a direct request, the other a coherent superposition of the desired and null addresses, and Alice keeps their order secret. A private matching qubit held by the selected client restores the coherent test state after a favorable Bell-measurement outcome, so that Alice can test the returned query without any further operation by Bob. The claim is deliberately limited. The protocol shows that a routing request can carry a physical cheating test, and it detects an explicit destination-reading attack with nonzero probability. It does not yet provide a quantitative information-disturbance tradeoff, composable security, or certification of an unmeasured output against arbitrary attacks. We also characterize the exact perfect-pass limit, in which Bob's residual state, averaged over the private matching states, is independent of the destination.
Can an untrusted entanglement router learn a requested destination only at the risk of detectable disturbance? This paper adapts the hidden-order mechanism of quantum private queries to a two-call routing primitive. Alice sequentially sends one direct destination request and one coherent superposition of the destination and a null address, hiding their order. Bob’s honest operation is an address-controlled swap using two pre-shared singlets per client. A private matching qubit at the selected client, followed by a favorable Bell-measurement outcome, restores the coherent request so Alice can projectively test it.
Honest runs are conclusive with probability 1/41/41/4; conditioned on that herald, the checks pass deterministically and the direct call supplies a singlet. Measuring both query addresses reveals the destination but dephases the trap: detection occurs with probability 1/21/21/2 conditioned on the herald, or 1/81/81/8 per attempt. An exact perfect-pass argument, using sequentiality and linearity, establishes destination independence of Bob’s residual state after averaging over independently sampled private matching states with mean I/2I/2I/2. This result assumes that both hidden orders preserve the trap, direct address, and direct singlet exactly.
The primitive does not establish a quantitative information–disturbance tradeoff, composable security, or certification of the unmeasured output against arbitrary attacks. It assumes ideal initial singlets, trusted user/client devices, private authenticated classical channels, and fixed-pattern cover traffic. Loss, noise, malicious clients, and repeated destination use are outside its scope; no approximate-pass continuity bound is provided.
Almost all of the previous quantum private query (QPQ) protocols are always based on an ideal environment without any noise. Nevertheless, due to the defects of the channel, channel noise inevitably exists in the actual transmission process, which will give rise to transmission error and reduce the probability of successful quantum transmission. An eavesdropper may disguise her actions as channel noise to avoid being detected by legitimate parties during security checks. To solve this problem, we present a QPQ protocol with perfect performance universally applicable against collective noise. Concretely, the protocol encodes bits in noiseless subspace and thus can function over a quantum channel subjected to an arbitrary degree of collective noise, as occurs, for instance, due to polarization rotation in an optical fiber. Furthermore, Bob cannot get the information about Alice's choice at all by taking fake entangled attack and by taking fake photon attack, the probability Bob can get the information about Alice's choice is only approximately 6.7%, which is far less than the probability of 25% in Yang et al.'s protocol. Moreover, the conclusiveness of the user Alice's measurement results is subject to quantum randomness rather than allowing Alice to choose by herself to obtain a conclusive result in Wei et al.'s protocol, which prevents Alice's intuitive attack and meanwhile makes it arduous for Bob to perform the joint-measurement attack. Our protocol uses only one state, which reduces the communication complexity, and is, therefore, an effective QPQ solution with the high-security level.
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.
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.
Quantum private query (QPQ) is a cryptographic application that protects the privacy of both users and databases while querying the database secretly. In most existing QPQ protocols, the protection of user privacy can only be cheat-sensitive. Cheat-sensitive means that Bob will be found later with a certain probability if he tries to get the address queried by Alice. On the premise of cheat-sensitivity, although Alice can discover Bob’s malicious behavior after a query (transaction), the secret information of Alice was leaked in the completed query, which is likely to be a fatal blow to Alice. Or, to prevent Bob’s malicious behavior, Alice executes one or more additional queries to test Bob’s honesty. However, to bypass Alice’s honesty test, Bob can also provide several honest queries before performing dishonest queries. Therefore, cheat-sensitive should not be the ultimate goal of user privacy protection in QPQ. In this paper, we propose a practical QKD-based QPQ protocol with better user privacy protection than cheat-sensitivity based on order rearrangement of qubits. The proposed QPQ protocol can resist the Trojan horse attack even without wavelength filter and photon number splitter (PNS) equipped with auxiliary monitoring detectors.
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.
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.