{"id":"c2c55e3e-a506-45f5-b5df-3f957c194313","arxiv_id":"2501.12842","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"No cheat-sensitive quantum private query protocol can be both secure for the user and protect the database owner, even when small errors are tolerated, because a dishonest user can retrieve all entries.","lead":"Quantum private query protocols promised to let a user secretly read one database entry while risking detection if they cheat. This paper proves that any protocol keeping the user's query secret lets the user extract the entire database, so cheat-sensitive quantum private queries are impossible.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 hinges on an unproved imported Lemma 3 whose hypotheses are not shown to match the protocol states; this needs verification before the impossibility claim is fully established.","rationale":"The central claim is well structured: Theorem 1's attack composes gentle measurements and Lemma 3 to step through queries, and the probability bounds in the appendix are internally consistent (the union bound works for m=2,3 and m>=4 with 125/64 <= 2). The specific attack on the GLM protocol is also convincing. The single load-bearing point is the external Lemma 3. The appendix explicitly says 'The proof of the lemma can be found in [52]' but does not state the proof's assumptions carefully enough for the reader to check the application. In particular, the lemma's unitary acts on A X, while the proof of Theorem 1 needs a unitary on B. A relabeling of A and B is possible, but the paper does not perform it, nor does it show that the classical-communication register structure in the protocol satisfies the lemma's cq-state template. Also, Definition 2's quantifier over 'a dishonest Alice' does not make it explicit that the honest Alice strategy is covered; the proof uses the honest execution's states. This is a real imprecision, but it is secondary to Lemma 3 because the intended reading of Definition 2 (security for the user against any Alice) would cover the honest case. The Lemma 3 dependency is more central: if the lemma does not apply, Eq. (9) has no basis. Since the lemma is from a published paper, this is likely fixable by adding a proof or a detailed derivation in the appendix, but it should be resolved before the impossibility claim is taken as established. Hence the reader's CONDITIONAL verdict remains appropriate.","tokens_in":1280,"tokens_out":1036,"duration_ms":264841,"concrete_test":"Independently write out the proof of Lemma 3 from [52] and instantiate it for the states rho^i_AB = sum_c p_i(c)|c><c|_C tensor |psi^{c,i}_{AB}><psi^{c,i}_{AB}|. Set X=C, X'=a copy of C, swap the lemma's A and B so that the conclusion is a unitary on B X, and verify that Definition 2's bound D(rho^i_A, rho^j_A) <= 2*eps implies the lemma's premise D(rho^i_{X'A}, rho^j_{X'A}) <= 2*eps (with the classical transcript included in A). Then check whether the unitary can be restricted to Bob's side B only, or whether it must act on the transcript register X; if the latter, confirm that Bob's local system includes that register. If Lemma 3's proof requires a condition not implied by the stated definitions - e.g., equality of the prior distributions P_0 and P_1 - the theorem needs qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive step in the proof of Theorem 1 is the use of Lemma 3 (Appendix, Preliminaries) to go from weak user privacy, D(rho^i_A, rho^j_A) <= 2*eps, to existence of a local unitary U_{B,i,j} on Bob's side such that D(U rho^i_AB U^dag, rho^j_AB) <= 2*sqrt(eps) (Eq. 9). Lemma 3 is stated for 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}| and concludes that there is a unitary on systems A and X, not on B. The proof is not given; the appendix only cites [52]. The paper does not spell out (i) how the protocol's end state, pure conditioned on classical communication, is mapped to the lemma's X, X', A, B registers; (ii) why the condition on D(rho^i_A, rho^j_A) implies the lemma's premise on the X'B marginal after the required party swap; and (iii) why the resulting unitary acts only on Bob's subsystem, as the attack requires. If any of these translations fails - for example, if the unitary necessarily acts on Alice's side, or if the classical-communication register is not included in both marginals in the way Definition 2 assumes - the chain of rotations that retrieves all entries is broken. This is not a dispute with the known result in [52], but a missing verification that Lemma 3 applies to the states in Theorem 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16418,"tokens_out":14929,"duration_ms":152329,"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":[{"comment":"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.","section":"Generic attack, Eq. (9); Appendix, Lemma 3"},{"comment":"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.","section":"Appendix, Lemma 3"}],"minor_comments":[{"comment":"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').","section":"Security Conditions"},{"comment":"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.","section":"Appendix, Lemma 2 proof"},{"comment":"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.","section":"Appendix, Eq. (6)"},{"comment":"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.","section":"Appendix, Theorem 1 proof"},{"comment":"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.","section":"Appendix, Theorem 1 proof"}],"recommendation":"major_revision","confidential_remarks":"The central result is potentially important and the specific attack is clean, but the generic proof's reliance on the unverified Lemma 3 is the main risk. I would ask the authors to supply a self-contained proof of the lemma or a precise reference with a detailed register translation before publication. The self-citation is not by itself a concern, but it increases the need for transparency about the lemma's exact statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nOn 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.\n\nAlso, 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.\n\nWhat 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.\n\nMy 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.\n\nFor your reading group, it is a maybe—the proof gap makes it a good discussion piece, and the specific attack is worth knowing.","headline":"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.","tokens_in":17039,"tokens_out":3619,"would_cite":true,"duration_ms":35519,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P94","94A60"],"pacs":["03.67.Dd"],"model":"deepseek-v4-flash","headline":"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.","keywords":["quantum private queries","symmetric private information retrieval","cheat-sensitive cryptography","quantum two-party computation","oblivious transfer","impossibility result","Gentle Measurement Lemma"],"falsifier":"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}$.","tokens_in":15901,"feed_emoji":"🔓","tokens_out":14845,"duration_ms":139082,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quantum private queries are impossible, even with cheat detection","feed_subtitle":"Weak user privacy forces a full-database leak whenever two queries have multiple valid answers.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the quantum private queries protocol and the cheat-sensitive setting that the paper's specific attack targets.","marker":"[29]"},{"why":"Provides the security analysis, the unique-valid-answer assumption, the repeated-query countermeasure, and the open question the paper answers negatively.","marker":"[30]"},{"why":"Supplies the earlier impossibility intuition that a local operation lets the user recover other entries, which the paper quantifies into its generic attack.","marker":"[13]"},{"why":"Supplies Lemma 3, the local-rotation lemma that lets Bob move his post-protocol state from one query to the next.","marker":"[52]"},{"why":"The Gentle Measurement Lemma, used to bound the disturbance when Bob measures a database entry from his state.","marker":"[46, 47]"},{"why":"The theorem connecting closeness of Alice's marginals to the existence of Bob's local rotation.","marker":"[48]"}],"fun_headline_variants":["Quantum private queries impossible with multiple valid answers","Cheat-sensitive quantum retrieval proven untrustworthy","Two answers break all quantum private query protocols","Quantum private queries fail when ambiguity exists","Impossibility proof: quantum private queries can't hide a second answer"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum private queries impossible with multiple valid answers","Cheat-sensitive quantum retrieval proven untrustworthy","Two answers break all quantum private query protocols","Quantum private queries fail when ambiguity exists","Impossibility proof: quantum private queries can't hide a second answer"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000267,"raw_usage":{"total_tokens":1601,"prompt_tokens":916,"completion_tokens":685,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":532,"completion_tokens_details":{"reasoning_tokens":627}},"tokens_in":532,"tokens_out":685,"duration_ms":6835,"temperature":1.0,"reasoning_tokens":627,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:46:43.346733+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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}$.","supporting_citations":[{"cited_title":"Giovannetti, S","cited_arxiv_id":null,"evidence_quote":"Introduces the quantum private queries protocol and the cheat-sensitive setting that the paper's specific attack targets."},{"cited_title":"Giovannetti, S","cited_arxiv_id":null,"evidence_quote":"Provides the security analysis, the unique-valid-answer assumption, the repeated-query countermeasure, and the open question the paper answers negatively."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the earlier impossibility intuition that a local operation lets the user recover other entries, which the paper quantifies into its generic attack."},{"cited_title":"Winkler, M","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 3, the local-rotation lemma that lets Bob move his post-protocol state from one query to the next."}],"review_version":1}