Impossibility of Quantum Private Queries

Esther H\"anggi; Severin Winkler

REVIEW 2 major objections 5 minor 60 references

Impossibility of Quantum Private Queries

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves an explicit, post-protocol attack that lets a dishonest user recover the entire database in any quantum private queries protocol secure for the user.

desk verdict Worth sending out: the specific attack on the GLM protocol is solid, but the generic impossibility proof has an unverified Lemma 3 application that a referee must check. read the letter →

arxiv 2501.12842 v5 pith:WDUBR5MM submitted 2025-01-22 quant-ph cs.CR

Esther Hänggi , Severin Winkler This is my paper · ORCID

classification quant-phcs.CR MSC 81P9494A60 PACS 03.67.Dd

keywords quantumprivatequeriessymmetricinformationretrievalcheat-sensitivecryptographytwo-partycomputationoblivioustransferimpossibilityresultGentleMeasurementLemma

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish a negative result: quantum private queries, the cheat-sensitive quantum version of symmetric private information retrieval, cannot be implemented securely. It shows that any protocol that is $\varepsilon$-correct and $(\varepsilon,\delta)$-secure for the user lets a dishonest user retrieve $m$ database entries with probability at least $1 - 2m^2\sqrt{\varepsilon}$, for any $2 \le m \le n$. A sympathetic reader should care because this closes the question left open by earlier analyses of the original protocol, and it rules out cheat-sensitivity as a workaround for the known impossibility of two-party secure computation without assumptions. If the paper is right, database-owner privacy in such protocols is either trivial or restricted to computationally bounded users.

What carries the argument

The engine of the argument is a post-protocol "measure-then-rotate" step. From $\varepsilon$-correctness, Bob has a measurement that finds the queried entry with probability at least $1-\varepsilon$; the Gentle Measurement Lemma says this leaves his state $\sqrt{\varepsilon}$-close to the original. From weak user privacy, Alice's post-protocol marginals for any two queries are $2\varepsilon$-close, and the paper's Lemma 3 (imported from reference [52]) converts this, via Uhlmann's theorem, into a local unitary on Bob's side that maps the joint state for one query to a state $2\sqrt{\varepsilon}$-close to the joint state for another. Composing these operations for successive queries accumulates at most $(l-1)(3\sqrt{\varepsilon}+\varepsilon)$ of trace distance, and a union bound over $m$ entries yields the success probability in Theorem 1. The specialized attack on the protocol of reference [29] uses the same purification idea on Alice's side: she holds a superposition over all valid answers and applies an optimal distinguishing measurement after the protocol, so Bob cannot detect the attack.

What would settle it

Construct a pair of joint states of the form used in Lemma 3 whose Alice-side marginals have trace distance at most $\varepsilon$ and check numerically whether a local unitary on Bob's side brings the joint states within the distance promised by the lemma; a violation would break the stepping argument behind Theorem 1. Alternatively, find a protocol that satisfies Definitions 1 and 2 for $\varepsilon \le 1/64$ and measure whether a dishonest user actually retrieves two entries with probability at least $1 - 8\sqrt{\varepsilon}$.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 1: for any $\varepsilon \le \delta \le 1$, any quantum private queries protocol that is $\varepsilon$-correct and $(\varepsilon,\delta)$-secure for the user allows a dishonest user to compute $2 \le m \le n$ database entries with probability at least $1 - 2m^2\sqrt{\varepsilon}$. Since every protocol that is cheat-sensitive secure in a simulation sense must satisfy the paper's weak correctness, user privacy, and data privacy conditions, the theorem implies there is no such protocol for $\varepsilon \le 1/64$ when at least two queries have multiple valid answers. The attack itself is undetectable: Bob executes the protocol honestly, keeps the purification of his own state, and only after acceptance performs a sequence of measurements and local unitary rotations that walk his state from one query's post-protocol state to the next. A specialized version against the original protocol of reference [29] uses Alice's purification over valid answers and an optimal distinguishing measurement, giving her a distinguishing advantage of at least $1 - 1/\max\{|X_i|,|X_j|\}$ while Bob always accepts.

Load-bearing premise

The load-bearing premise is that near-indistinguishability of the database owner's view for two queries guarantees the user can, by acting only on his own part of the shared state, switch to a state almost as good for the other query; if that premise fails for some protocol, the chain that extracts every database entry breaks.

Editorial extensions

If this is right

There is no quantum private queries protocol for any database with $n \ge 2$ entries, at least two of which have multiple valid answers, when $\varepsilon \le 1/64$ and both user and data privacy are required (Corollary 1.1).
Any protocol that is secure for the user necessarily leaks the entire database to a malicious user, so the database owner's privacy guarantee cannot be non-trivial in the cheat-sensitive model.
The repeated-query countermeasure proposed for the original protocol does not restore security: the database owner can answer consistently from a fixed purification, and the distinguishing measurement happens after the protocol ends.
The impossibility extends beyond private queries to secure evaluation of arbitrary functions and to variants of oblivious transfer, and the proof method yields lower bounds on the number of 1-out-of-2 oblivious transfer instances needed to implement 1-out-of-$n$ oblivious transfer.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Our inference: the same measure-then-rotate template may apply to other one-sided secure function evaluations, since it only needs user privacy to force closeness of the sender's marginal states.
Our inference: the $m^2$ factor in the success bound comes from a union bound and linear accumulation of trace distance, so a tighter error analysis could plausibly lower the exponent and make the impossibility hold for larger $\varepsilon$.
Our inference: because the attack runs after acceptance, changing the order of verification checks or adding consistency rounds cannot prevent the leak while the user-privacy condition holds, so experimental demonstrations should be benchmarked against post-protocol local processing.
Our inference: if the local-rotation lemma used from reference [52] holds for more general state families, the same impossibility would transfer to other two-party primitives that only guarantee closeness of one party's marginals.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is worth reading, but the headline result needs a careful look. The specific attack on the Giovannetti–Lloyd–Maccone protocol is the strongest part: it works even against the repeated-query countermeasure from [30], and the trace-distance calculation is clean. That alone is a useful contribution. The generic attack, with the bound 1−2m²√ε, would close the approximate cheat-sensitive regime that [32] left open, and the statement is genuinely new.

On the proof: the chain from weak user privacy to a local rotation that hops between query states is load-bearing, and it relies entirely on Lemma 3, imported from [52]. The lemma as stated gives a unitary on AX (Alice plus a classical register), with the closeness assumption on the X'B marginal. The proof of Theorem 1 instead needs a unitary on B alone, with closeness of the Alice marginals. The paper does not explain how the protocol's end state—pure conditioned on classical communication—is cast in the lemma's cq form, nor why the party roles line up. This is not a minor typo; without that translation, Eq. (9) does not follow from the cited lemma. The appendix does not reproduce the proof of Lemma 3, so a referee cannot check the adaptation. The stress-test concern is right: the hypotheses may match after a suitable purification and register relabeling, but the paper has to show it.

Also, Definition 2's quantifier is loose: it says "for any strategy of a dishonest Alice that Bob accepts with probability at least 1−δ" but does not make explicit whether the honest Alice strategy is included. That matters for the claim that ε-correctness implies δ=ε. Fixable in a sentence, but it should be fixed.

What is not wrong: the specific attack is rigorous, the paper engages honestly with prior work, there is no parameter fitting or circularity, and the discussion of computational alternatives is sensible. If the Lemma 3 gap closes, the impossibility result is significant—it kills cheat-sensitive quantum private queries as a theoretical primitive for multi-answer databases.

My take: the paper deserves a serious referee. I would send it out, but with a request to make the proof of Theorem 1 self-contained regarding Lemma 3 and to fix the unitary side mismatch. I would not accept it as is.

For your reading group, it is a maybe—the proof gap makes it a good discussion piece, and the specific attack is worth knowing.

Referee Report

2 major / 5 minor

Summary. The paper claims an impossibility result for cheat-sensitive quantum private queries under weak statistical security definitions. It first presents a specific attack against the Giovannetti-Lloyd-Maccone protocol, in which a dishonest database owner who prepares a superposition of valid database entries and keeps a purification can distinguish any two queries with probability at least 1 - 1/max{|X_i|, |X_j|}, without being detected. It then gives a generic attack against any quantum private queries protocol that is epsilon-correct and weakly (epsilon, delta)-secure for the user, showing that a dishonest user can retrieve m database entries with probability at least 1 - 2 m^2 sqrt(epsilon). The paper concludes that no protocol can satisfy its weak user-privacy and weak data-privacy conditions simultaneously for epsilon <= 1/64, and that any protocol secure for the user leaks the full database to a malicious user under the stated definitions.

Significance. If Theorem 1 is correct, the paper closes an open question about whether cheat-sensitive quantum private queries can provide any non-trivial security guarantee in the approximate, multi-valid-answer setting. The explicit attack on the GLM protocol is a clean and useful strengthening of the earlier attack of Giovannetti-Lloyd-Maccone, and the generic attack provides a quantitative bound rather than only an asymptotic statement. The proof uses standard tools - the gentle measurement lemma, Uhlmann's theorem, and trace-distance inequalities - and does not fit parameters to data. The main weakness is that the central step of the generic attack depends on an imported lemma whose application to the protocol states is not verified in the manuscript; until that gap is closed, the impossibility claim is conditional.

major comments (2)

[Generic attack, Eq. (9); Appendix, Lemma 3] The proof of Theorem 1 uses Lemma 3 to pass from D(rho^i_A, rho^j_A) <= 2 epsilon to the existence of a local unitary U_{B,i,j} with D(U_{B,i,j} rho^i_AB U_{B,i,j}^\dagger, rho^j_AB) <= 2 sqrt(epsilon). As stated, Lemma 3 applies to cq-states of the form sum_x P_b(x)|x><x|_X tensor |x><x|_{X'} tensor |psi^{x,b}_{AB}><psi^{x,b}_{AB}|, its premise is closeness of the X'B marginal, and its conclusion is a unitary on A X, not on B. The appendix does not explain how the protocol's final state (pure conditioned on classical communication) is mapped to the registers X, X', A, B; why D(rho^i_A, rho^j_A) <= 2 epsilon implies the lemma's premise after the required party swap; or why the resulting unitary can be taken to act only on Bob's system. Since this is exactly the step that lets Bob rotate from one query's post-protocol state to the next, Eq. (9) is unsupported as written and Theorem 1 is incomplete without a proof or a precise citation of a suitable variant.
[Appendix, Lemma 3] Lemma 3 is imported from Ref. [52] without proof or a pointer to the precise statement in that reference. This matters not only for self-containedness: the printed statement of Lemma 3 is not in the form used in the proof of Theorem 1, and one of the authors of the present paper is a coauthor of Ref. [52]. The appendix should either reproduce a proof of Lemma 3 or state the exact lemma number and version in Ref. [52] and verify the register translation, so that the reader can check that the lemma's hypotheses actually match the states in Theorem 1.

minor comments (5)

[Security Conditions] In the paragraph introducing Definition 2, the sentence 'the states rho^i_A and rho^j_A are at least 2 epsilon-close' should read 'at most 2 epsilon-close' (or 'within trace distance 2 epsilon').
[Appendix, Lemma 2 proof] In the proof of Lemma 2, the initial database state is written with |phi^i>_{X_k X'_k} under the product over k; the superscript should be k, not i, since each data register k has its own superposition over the valid answers for query k.
[Appendix, Eq. (6)] Appendix Eq. (6) writes D(rho^0_A, rho^1_A) for what are joint cq-states rho^b_{XA}; the displayed identity holds for the joint states, so the notation should be D(rho^0_{XA}, rho^1_{XA}) to avoid stating a false identity for the marginals.
[Appendix, Theorem 1 proof] In bounding epsilon_l by (l-1)(3 sqrt(epsilon)+epsilon)+epsilon, the proof relies on the standard fact that applying a fixed measurement to two states changes the success probability by at most their trace distance; this fact should be stated explicitly, as it is otherwise easy to miss.
[Appendix, Theorem 1 proof] There are typographical slips in the appendix, such as '(l-1))(3 sqrt(epsilon)+epsilon)' and missing closing parentheses in the displayed induction chain; these should be cleaned up.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the impossibility result is derived from the paper's stated security definitions and standard parameter-free lemmas, with only a minor self-citation to Lemma 3 that is not itself the target result.

full rationale

The central claim, Theorem 1, is derived from the paper's own security definitions (Definitions 1-3), the Gentle Measurement Lemma, Uhlmann's theorem, and Lemma 3 imported from Ref. [52]. The only self-citation in the loading-bearing proof is Lemma 3, which is coauthored by one of the present authors, S. Winkler. However, this lemma is a parameter-free mathematical statement with a published proof elsewhere; its conclusion is not equivalent to the impossibility of quantum private queries, and the theorem's result is not an input to the lemma. The proof does not fit any parameter to data, and the 'prediction' that a dishonest user can retrieve entries with probability 1 - 2m^2 sqrt(eps) is obtained by an explicit attack construction from the stated privacy and correctness conditions. The specific attack on the Giovannetti-Lloyd-Maccone protocol is also self-contained, computing a trace-distance lower bound from explicit state preparations rather than importing the impossibility conclusion. The concern that Lemma 3's hypotheses may not match the protocol states, or that the appendix does not reproduce its proof, is a verification or correctness gap, not a circularity: the paper does not define user privacy in terms of the lemma's conclusion, nor does the lemma presuppose the nonexistence of secure quantum private queries. Accordingly, the derivation is substantially self-contained, and the minor self-citation does not make the central claim circular; score 1 reflects that small self-citation dependency without any reduction of the result to its inputs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted: epsilon is a variable in the theorem, not a constant matched to data. The proof relies on standard quantum-information theorems and on one imported lemma (Lemma 3 from Ref. [52]) that is not reproduced in the appendix. No new physical entities are postulated; the 'purified strategies' and 'valid answer sets' are modeling tools, not independent entities.

assumptions (6)

standard math Uhlmann's theorem: for two pure states with ε-close reduced states on subsystem A, there exists a unitary on subsystem B rotating one state to within √(2ε) of the other.
Invoked in the proof of Theorem 1 and in Lemma 3 to convert user privacy (closeness of Alice's marginals) into a local rotation of Bob's state.
standard math Gentle Measurement Lemma: a measurement that detects a state with probability at least 1−ε leaves the post-measurement state √ε-close to the original.
Used in the proof of Theorem 1 (Lemma 4) to bound the disturbance Bob's measurement of one database entry causes to his state.
standard math Lemma 3 from Ref. [52]: for states of the form ρ^b_{XX'AB} with D(ρ^0_{X'B}, ρ^1_{X'B}) ≤ ε, there exists a unitary on A and X mapping the first state to within √(2ε) of the second.
The pivotal bridge in the generic attack; stated in the appendix with proof deferred to [52]. It generalizes Uhlmann's theorem to classical-quantum states with classical registers.
domain assumption The final joint state of the protocol can be purified so that, conditioned on all classical communication, the state is pure.
Assumed in the proof of Theorem 1 and in the appendix preliminaries; standard in quantum two-party computation because adversarial operations can be purified with ancillas.
domain assumption The weak security conditions (Definitions 2 and 3) are necessary for any meaningful cheat-sensitive QPQ protocol.
The paper states that these conditions necessarily hold for any simulation-based secure protocol; the impossibility is proven against these necessary conditions, so the result's scope is exactly this class.
domain assumption Database entries X_i are chosen uniformly at random from the sets of valid answers X_i.
Used to model a priori unknown database entries and to define data privacy; also used in the specific attack where Alice keeps a purification of the random choice.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Impossibility of Quantum Private Queries." pith.science (2026). https://pith.science/paper/WDUBR5MM

@misc{pith2026250112842,
  author       = {Pith},
  title        = {Pith review of: Impossibility of Quantum Private Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WDUBR5MM}},
  note         = {Machine review of arXiv:2501.12842}
}

read the original abstract

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 one-sided secure function evaluation and is closely related to oblivious transfer. Under the name quantum private queries, 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 [V. Giovannetti, S. Lloyd, and L. Maccone, Phys. Rev. Lett. 100, 230502 (2008)]. 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 non-trivial security guarantees for the owner of the database.

Figures

Figures reproduced from arXiv: 2501.12842 by the authors.

**Figure 2.** FIG. 2. The protocol [29] is depicted inside the box. Using the [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗

**Figure 3.** FIG. 3. Our generic attack on any protocol implementing [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: FIG. 4. The generic attack on any quantum private queries protocol. The sequence of rotations and measurements are all [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 54 canonical work pages

[30]

Giovannetti, S

V. Giovannetti, S. Lloyd, and L. Maccone, IEEE Trans- actions on Information Theory56, 3465 (2010)

work page 2010
[32]

Jakobi, C

M. Jakobi, C. Simon, N. Gisin, J.-D. Bancal, C. Bran- ciard, N. Walenta, and H. Zbinden, Physical Review A 83, 022301 (2011)

work page 2011
[52]

Winkler, M

S. Winkler, M. Tomamichel, S. Hengl, and R. Renner, Physical Review Letters107, 090502 (2011). 1 Impossibility of Quantum Private Queries — Appendix Preliminaries We refer to a standard textbook on quantum information such as [49] for a detailed introduction. We consider finite-dimensional Hilbert spacesH.P(H) denotes the set of positive semi-definite ope...

work page 2011
[1]

C. H. Bennett and G. Brassard, inProceedings of IEEE International Conference on Computers, Systems, and Signal Processing(India, 1984) p. 175

work page 1984
[2]

A. K. Ekert, Physical Review Letters67, 661 (1991)

1991
[3]

Stefanov, N

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, Journal of Modern Optics47, 595 (2000)

work page 2000
[4]

Jennewein, U

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, Review of Scientific Instruments71, 1675 (2000)

work page 2000
[5]

Wiesner, SIGACT News15, 78 (1983)

S. Wiesner, SIGACT News15, 78 (1983)

1983

Show all 60 references

[6]

Brassard and C

G. Brassard and C. Cr´ epeau, inAdvances in Cryptology- CRYPTO’ 90, edited by A. J. Menezes and S. A. Van- stone (Springer Berlin Heidelberg, Berlin, Heidelberg,
[7]

C. H. Bennett, G. Brassard, C. Cr´ epeau, and H. Sku- biszewska, inAdvances in Cryptology — CRYPTO ’91 (1992) pp. 351–366

1992
[8]

Brassard, C

G. Brassard, C. Crepeau, R. Jozsa, and D. Langlois, in Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science(1993) pp. 362–371

1993
[9]

Ardehali, A quantum bit commitment protocol based on epr states (1996), arXiv:quant-ph/9505019 [quant-ph]

M. Ardehali, A quantum bit commitment protocol based on epr states (1996), arXiv:quant-ph/9505019 [quant-ph]

1996 arXiv
[10]

B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, in Proceedings of IEEE 36th Annual Foundations of Com- puter Science(1995) pp. 41–50

1995
[11]

Mayers, Physical Review Letters78, 3414 (1997)

D. Mayers, Physical Review Letters78, 3414 (1997)

1997
[12]

H. K. Lo and H. F. Chau, Physical Review Letters78, 3410 (1997)

1997
[13]

H. K. Lo, Physical Review A56, 1154 (1997)

1997
[14]

Kitaev, Quantum coin-flipping (2003), slides avail- able athttp://www.msri.org/publications/ln/msri/ 2002/qip/kitaev/1/index.html

A. Kitaev, Quantum coin-flipping (2003), slides avail- able athttp://www.msri.org/publications/ln/msri/ 2002/qip/kitaev/1/index.html

2003
[15]

Ambainis, inSTOC ’01: Proceedings of the 33rd An- nual ACM Symposium on Theory of Computing(2001) pp

A. Ambainis, inSTOC ’01: Proceedings of the 33rd An- nual ACM Symposium on Theory of Computing(2001) pp. 134–142

2001
[16]

Buhrman, M

H. Buhrman, M. Christandl, and C. Schaffner, Physical Review Letters109, 160501 (2012)

2012
[17]

Colbeck, The impossibility of secure two-party classi- cal computation (2007)

R. Colbeck, The impossibility of secure two-party classi- cal computation (2007)

2007
[18]

R. W. Spekkens and T. Rudolph, Physical Review A65, 012310 (2001)

2001
[19]

Chailloux and I

A. Chailloux and I. Kerenidis, in2009 50th Annual IEEE Symposium on Foundations of Computer Science(IEEE,
[20]

Chailloux, G

A. Chailloux, G. Gutoski, and J. Sikora, Chicago Journal of Theoretical Computer Science2016, 10.4086/cjtcs.2016.013 (2016)

2016 doi
[21]

Aharonov, A

D. Aharonov, A. Ta-Shma, U. V. Vazirani, and A. C. Yao, inProceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC ’00 (2000) p. 705–714

2000
[22]

Mochon, inFOCS ’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004) pp

C. Mochon, inFOCS ’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004) pp. 2–11

2004
[23]

Franklin and M

M. Franklin and M. Yung, inProceedings of the Twenty- Fourth Annual ACM Symposium on Theory of Comput- ing, STOC ’92 (Association for Computing Machinery, New York, NY, USA, 1992) p. 699–710

1992
[24]

Aumann and Y

Y. Aumann and Y. Lindell, Journal of Cryptology23, 281 (2010)

2010
[25]

R. W. Spekkens and T. Rudolph, Physical Review Letters 89, 227901 (2002)

2002
[26]

Neves, V

S. Neves, V. Yacoub, U. Chabaud, M. Bozzio, I. Kereni- dis, and E. Diamanti, Nature Communications14, 1855 (2023)

2023
[27]

Hardy and A

L. Hardy and A. Kent, Physical Review Letters92, 157901 (2004)

2004
[28]

Buhrman, M

H. Buhrman, M. Christandl, P. Hayden, H.-K. Lo, and S. Wehner, Physical Review A78, 022316 (2008)

2008
[29]

Giovannetti, S

V. Giovannetti, S. Lloyd, and L. Maccone, Physical Re- view Letters100, 230502 (2008)

2008
[31]

De Martini, V

F. De Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, Physical Review A80, 010302 (2009)

2009
[33]

Olejnik, Physical Review A84, 022313 (2011)

L. Olejnik, Physical Review A84, 022313 (2011)

2011
[34]

P. Chan, I. Lucio-Martinez, X. Mo, C. Simon, and W. Tittel, Scientific Reports4, 5233 (2014)

2014
[35]

Winkler and J

S. Winkler and J. Wullschleger, inAdvances in Cryptol- ogy — CRYPTO ’10(2010) pp. 707–723

2010
[36]

Salvail, C

L. Salvail, C. Schaffner, and M. Sot´ akov´ a, inAdvances in Cryptology — ASIACRYPT ’09(2009) pp. 70–87

2009
[37]

Bartusek, A

J. Bartusek, A. Coladangelo, D. Khurana, and F. Ma, inAdvances in Cryptology – CRYPTO 2021(2021) pp. 467–496

2021
[38]

Thus, here thenactual database entries arex 1,

Note that the database for the protocol [29] uses an ad- 6 ditional dummy entry at index 0. Thus, here thenactual database entries arex 1, . . . , xn
[39]

This is an attack type often used in quantum two-party protocols and corresponds to the player keeping the pu- rification of the state
[40]

Helstrom,Quantum Detection and Estimation Theory (Academic Press, 1976)

C. Helstrom,Quantum Detection and Estimation Theory (Academic Press, 1976)

1976
[41]

Fehr and C

S. Fehr and C. Schaffner, inTheory of Cryptography Con- ference — TCC ’09(2009) pp. 350–367

2009
[42]

H¨ anggi and S

E. H¨ anggi and S. Winkler, (2024), arXiv:2405.12121

2024 arXiv
[43]

Since this stronger requirement satisfies our cor- rectness condition, our impossibility result also holds in this case, for any 0≤δ≤1

A stronger correctness condition would require that both players always accept the protocol if it is honestly exe- cuted. Since this stronger requirement satisfies our cor- rectness condition, our impossibility result also holds in this case, for any 0≤δ≤1
[44]

Alice rejects the protocol with prob- abilityεindependently of everything else

In this trivial protocol, Alice sends allndatabase entries xi to Bob, who retrieves the database entry of his choice and always accepts. Alice rejects the protocol with prob- abilityεindependently of everything else. This protocol is correct and obviously secure for Bob. Since...
[45]

Onofri and V

S. Onofri and V. Giovannetti, (2024), arXiv:2401.05754

2024 arXiv
[46]

Winter, IEEE Transactions on Information Theory 45, 2481 (1999)

A. Winter, IEEE Transactions on Information Theory 45, 2481 (1999)

1999
[47]

M. M. Wilde,Quantum Information Theory(Cambridge University Press, 2013)

2013
[48]

Uhlmann, Rep

A. Uhlmann, Rep. Math. Phys.9, 273 (1976)

1976
[49]

Nielsen and I

M. Nielsen and I. Chuang,Quantum Computation and Quantum Information(Cambridge University Press, 2000)

2000
[50]

W. F. Stinespring, Proceedings of the American Mathe- matical Society6, 211 (1955)

1955
[51]

Renner,Security of Quantum Key Distribution, Ph.D

R. Renner,Security of Quantum Key Distribution, Ph.D. thesis, ETH Zurich, Switzerland (2005), available at http://arxiv.org/abs/quant-ph/0512258

2005 arXiv
[53]

, n}are the actual database entries and|x 0⟩=|d⟩is an additional dummy entry

Alice creates a classical database{|x i⟩}i containingn+ 1 entries, wherex i ∈ Xfori∈ {1, . . . , n}are the actual database entries and|x 0⟩=|d⟩is an additional dummy entry
[54]

, n}which he would like to query

Bob selects the indexi∈ {1, . . . , n}which he would like to query
[55]

Ifa= 0, he prepares the states|ψ 1⟩=|i⟩and|ψ 2⟩= (|0⟩+|i⟩)/ √

Bob tosses a coina. Ifa= 0, he prepares the states|ψ 1⟩=|i⟩and|ψ 2⟩= (|0⟩+|i⟩)/ √
[56]

Ifa= 1, then he prepares the states|ψ 1⟩= (|0⟩+|i⟩)/ √ 2 and|ψ 2⟩=|i⟩
[57]

Bob sends|ψ 1⟩to Alice who performs a conditional database query, i.e., she applies the QRAM algorithm (see [29, 49] and the definition below) and returns the query and the register to Bob
[58]

Bob sends|ψ 2⟩to Alice who performs a conditional database query and returns the query and the register to Bob
[59]

If this first check fails, he caught Alice cheating

Ifa= 0, Bob measures the first state in the computational basis and checks whether the result is (i, x i). If this first check fails, he caught Alice cheating. He then checks whether the second state is (|0⟩ |d⟩+|i⟩ |xi⟩)/ √ 2, by projecting onto this state. If the second chec...
[60]

Alice computes the answers to both queries using the QRAM algorithm

Then he chooses a random bitaand sends first the state|ψ a⟩and then the state|ψ 1−a⟩. Alice computes the answers to both queries using the QRAM algorithm. The algorithm only accesses the data registerX 0 (dummy entry) andX i (the answer to Bob’s query). The state|Ψ AB⟩before A...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [30]

Giovannetti, S

V. Giovannetti, S. Lloyd, and L. Maccone, IEEE Trans- actions on Information Theory56, 3465 (2010)

work page 2010

[2] [32]

Jakobi, C

M. Jakobi, C. Simon, N. Gisin, J.-D. Bancal, C. Bran- ciard, N. Walenta, and H. Zbinden, Physical Review A 83, 022301 (2011)

work page 2011

[3] [52]

Winkler, M

S. Winkler, M. Tomamichel, S. Hengl, and R. Renner, Physical Review Letters107, 090502 (2011). 1 Impossibility of Quantum Private Queries — Appendix Preliminaries We refer to a standard textbook on quantum information such as [49] for a detailed introduction. We consider finite-dimensional Hilbert spacesH.P(H) denotes the set of positive semi-definite ope...

work page 2011

[4] [1]

C. H. Bennett and G. Brassard, inProceedings of IEEE International Conference on Computers, Systems, and Signal Processing(India, 1984) p. 175

work page 1984

[5] [2]

A. K. Ekert, Physical Review Letters67, 661 (1991)

1991

[6] [3]

Stefanov, N

A. Stefanov, N. Gisin, O. Guinnard, L. Guinnard, and H. Zbinden, Journal of Modern Optics47, 595 (2000)

work page 2000

[7] [4]

Jennewein, U

T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, Review of Scientific Instruments71, 1675 (2000)

work page 2000

[8] [5]

Wiesner, SIGACT News15, 78 (1983)

S. Wiesner, SIGACT News15, 78 (1983)

1983