{"id":"424ab552-4ae9-4cd9-8a9e-ce72a54a371c","arxiv_id":"2506.16904","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A proposed public-key quantum signature scheme based on local density matrices, claimed secure via QMA-hardness, is broken by a simple re-signing attack and an invalid security reduction.","lead":"This paper proposes a quantum authentication and digital signature scheme where the public key is a set of small reduced density matrices and the private key is a secret circuit that prepares a large entangled state. The security claim rests on the QMA-completeness of the quantum marginal problem, but the scheme is forgeable from a single valid signature.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The scheme is publicly malleable: from one signature σ_m = U_m ρ_M and the public unitaries, an adversary produces a valid signature for any new m′ by applying U_{m′}U_m^{−1}. This directly breaks EUF-qCMA, so the central theorem fails on the paper's own definitions.","rationale":"The reader's REJECT verdict is correct, and I do not move it. The most load-bearing concern is the public malleability of the signature map: since Definition 3 declares U_m and its inverse public, and Algorithm 3 verifies only after applying U_m^{-1}, any two signatures are related by a known unitary. This is an internal contradiction with the Theorem's EUF-qCMA claim, not a disagreement with complexity-theoretic consensus. I also considered the reduction's admission that signing queries need not be answered and the use of worst-case QMA-hardness as average-case one-wayness; both are independently serious, but the malleability attack is the cleanest refutation because it uses only the scheme's own algorithms. The proposed test is analytic and settles the point; no computational experiment is needed. I note the paper does provide explicit pseudocode, which made the attack check immediate, but no formal verification or implementation is present to offset the flaw.","tokens_in":11708,"tokens_out":7980,"duration_ms":83056,"concrete_test":"Symbolic check: take any message m and any new message m′ from the same message space, define W = U_{m′}U_m^{-1}, and set τ = W (U_m ρ_M U_m^{-1}) W† = U_{m′} ρ_M U_{m′}^{-1}. Run Algorithm 3 on (pk_A, m′, τ): it computes U_{m′}^{-1} τ U_{m′} = ρ_M and then compares the same k-qubit marginals as for the genuine signature σ_m, so it outputs Accept. This derivation settles the concern analytically; optionally instantiate with M=1, U_m = R_z(θ_m) for m≠m′, and a non-pure ρ_M to confirm numerically that Verify accepts the forged state.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem is refuted by the protocol's own signing and verification definitions. Algorithm 2 signs as σ_m = U_m ρ_M, and Algorithm 3 accepts (m, σ) iff after applying the public inverse U_m^{-1} the reduced marginals match pk_A. Definition 3 makes every U_m and U_m^{-1} publicly and efficiently computable. Given one valid signature σ_m for a queried message m, an adversary chooses a new m′ and computes W = U_{m′}U_m^{-1}. Since W is a public unitary, the adversary sets τ = W σ_m W† = U_{m′} ρ_M U_{m′}†. Verification of (m′, τ) first applies U_{m′}^{-1}, returning ρ_M, and then checks exactly the same marginals that made σ_m valid; hence Verify accepts. One signing query therefore yields valid signatures for every other message, regardless of BQP≠QMA. This is not a subtle proof gap but an algebraic property of the construction: signing is just conjugation of a fixed reduced state by a public unitary, so the message map is homomorphic. The security proof's assumption that signing queries do not help the adversary is false on the manuscript's own equations. A secondary flaw is the reduction's explicit statement that it need not answer signing queries; but the malleability attack is sufficient by itself.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a public-key quantum authentication and digital signature scheme whose security is claimed to be based on the QMA-completeness of the Consistency of Local Density Matrices (CLDM) problem. In the scheme, Alice's private key is an efficiently preparable N-qubit state, her public key is the collection of its k-qubit marginals, and authentication proceeds by Bob challenging an M-qubit subsystem that Alice returns. To sign a message m, Alice applies a public, efficiently invertible message-dependent unitary U_m to the challenged subsystem, producing σ_m = U_m ρ_M. Verification applies U_m^{-1} and checks the resulting local marginals against the public key. The main theorem claims existential unforgeability under adaptive quantum chosen-message attacks (EUF-qCMA) assuming BQP≠QMA. The paper also sketches authentication security, non-repudiation, transferability, and verification costs via partial quantum state tomography.","tokens_in":11836,"tokens_out":4897,"duration_ms":51780,"significance":"If the central claim were correct, the protocol would be a notable conceptual contribution: a public-key quantum signature scheme with no trusted third parties, no pre-shared secrets, and no authenticated classical channel, built on a natural QMA-complete problem. The manuscript is clearly written, gives explicit algorithms, and includes a useful discussion of verification resources and an explicit limitation (Lemma 1) about exposing the full private state. However, the central security theorem is invalid as stated: the scheme is publicly malleable, so a single valid signature for one message immediately yields valid signatures for every other message. The reduction in the proof also fails to instantiate the EUF-qCMA game because it explicitly declines to answer signing queries. These are not presentation issues but load-bearing errors that invalidate the main claim.","major_comments":[{"comment":"A direct forgery breaks the central theorem. Algorithm 2 signs as σ_m = U_m ρ_M, and Definition 3 makes U_m and U_m^{-1} public and efficiently computable. Given one valid signature σ_m for a queried message m, an adversary chooses a new message m' and computes the public unitary W = U_{m'} U_m^{-1}, then outputs τ = W σ_m W† = U_{m'} ρ_M U_{m'}^†. Verification of (m', τ) applies U_{m'}^{-1} and checks exactly the same marginals that made σ_m valid, so Verify accepts with the same probability. One signing-oracle query therefore yields valid signatures for every other message, independently of BQP≠QMA. This directly contradicts the EUF-qCMA theorem stated in the Security Analysis.","section":"Digital Signature; Definition 3; Algorithms 2–3"},{"comment":"The reduction does not instantiate the EUF-qCMA game. The proof states explicitly that 'the security proof does not require B to answer the queries correctly' and that the existence of a successful forger is assumed regardless of how oracle queries are handled. In the EUF-qCMA game, the adversary's success probability is defined after receiving valid signatures for its chosen messages; a reduction that answers queries incorrectly or not at all cannot use the adversary's output as evidence about the underlying instance. The step 'E successful forgery implies YES' is asserted rather than derived, and for a NO instance no valid signature can exist at all, so the claimed distinguishing procedure is not well defined.","section":"Security Analysis, Proof of Unforgeability"},{"comment":"The proof uses a worst-case QMA-complete instance as the public key, but the security assumption needed is an average-case or distributional hardness property. The adversary in the EUF-qCMA game sees public keys generated by Algorithm 1, whereas the reduction sets pk_E to an arbitrary CLDM instance. Without a worst-case-to-average-case reduction, a forger that breaks the scheme on the key distribution does not imply a solver for arbitrary CLDM instances. The manuscript provides no argument bridging this gap.","section":"Proof of Unforgeability"},{"comment":"The authentication-security argument is not formal. It claims that responding to arbitrary challenges with states matching the public marginals 'is equivalent to solving the CLDM problem,' but an adversary that participates in many sessions receives M-qubit fragments of ρ_A for different challenge sets; the protocol does not analyze whether these transcripts compose into a reconstruction or impersonation attack. The restriction k<M<N and random challenges are discussed informally, and Lemma 1 addresses only the trivial full-state attack, so the authentication claim is unsupported.","section":"Authentication Security"}],"minor_comments":[{"comment":"There is a typo in the introduction to the signature phase: 'A;ice' should read 'Alice'.","section":"Digital Signature"},{"comment":"The symbol k is used both for the subsystem size and as the loop index in Algorithm 1, which is confusing; using a different loop variable such as j would improve clarity.","section":"Algorithm 1"},{"comment":"The reduction algorithm is introduced as F and then referred to as B in the same proof; one consistent symbol should be used throughout.","section":"Proof of Unforgeability"},{"comment":"Definition 3 describes unitaries acting on 2^n qubits, but the signing procedure applies U_m to the M-qubit subsystem ρ_M; the intended domain of U_m, and how the message length |m| relates to M, should be clarified.","section":"Definition 3"},{"comment":"The statement that verification is a 'mathematical proof' is overstated, since Algorithm 3 is probabilistic and threshold-based (tomography with acceptance threshold ε); the wording should be softened.","section":"Non-Repudiation and Transferability"},{"comment":"There are several grammatical slips, for example 'E successful forgery by E' in the proof, and the notation for the reconstructed marginals alternates between ρ_C' and ρ_Ck without definition.","section":"Security Analysis"}],"recommendation":"reject","confidential_remarks":"The central theorem is invalidated by a simple public-malleability attack that follows directly from the protocol's own definitions (Algorithms 2 and 3, Definition 3). The reduction in the Security Analysis also does not answer signing queries and therefore does not instantiate the claimed EUF-qCMA game. These are foundational errors rather than local fixable gaps; a substantially different construction and a rigorous security model would be required before the manuscript could be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe central theorem in arXiv:2506.16904 is false. One signing query lets an adversary forge a signature for any other message. The signing algorithm outputs σ_m = U_m ρ_M, and U_m is public and invertible. For any m', the adversary computes U_{m'} U_m^{-1}, applies it to σ_m, and verification accepts. This is public-key malleability plain and simple, and it breaks EUF-qCMA regardless of BQP≠QMA.\n\nCredit where due: the construction is novel. Using the QMA-completeness of CLDM as the security foundation, with classical k-local marginals as the public key and a message-dependent unitary as the signing map, is an original idea. The paper is clearly written, has explicit algorithms, and its Lemma 1 honestly identifies why the full private state must not be revealed. That is a useful starting point.\n\nThe soft spots are severe. First, the malleability attack is not a proof gap; it is an algebraic fact about the scheme. Second, the reduction is invalid even if the attack did not exist: the proof states that the reduction need not answer signing oracle queries, but a forger in the EUF-qCMA game is only a forger when given valid responses. Ignoring queries makes the reduction circular. Third, the proof uses worst-case QMA-hardness where average-case one-wayness would be required; that implication is not established. Minor issues include the inconsistency between Algorithm 1, which sets sk_A=ρ_A, and the text, which says the private key is the circuit; and the admitted need for a public ledger to bind identity, which contradicts the claim of eliminating trusted third parties.\n\nThis paper is for quantum cryptographers interested in why public unitaries cannot be used as a signing primitive. It could also serve as a cautionary example in a teaching context. As submitted, it should not be published. I would still send it to a competent referee rather than desk-reject, because the idea is fresh and the failure mode is instructive; the recommended verdict would be reject, with the option of a major revision if the authors find a way to make the signing map non-malleable.","headline":"The central security theorem is false: one signing query yields universal forgery via public conjugation, so the claimed EUF-qCMA security collapses.","tokens_in":12541,"tokens_out":4707,"would_cite":false,"duration_ms":47756,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P94","81P68"],"pacs":["03.67.Dd","03.67.Lx"],"model":"deepseek-v4-flash","headline":"This paper claims that a public-key quantum signature and authentication scheme, built on the QMA-completeness of the quantum marginal problem, is existentially unforgeable under adaptive chosen-message attacks, assuming $BQP \\neq QMA$.","keywords":["quantum public-key cryptography","quantum digital signatures","quantum authentication","QMA-completeness","quantum marginal problem","consistency of local density matrices","existential unforgeability","adaptive chosen-message attack"],"falsifier":"Prepare a legitimate signature $\\sigma_m = U_m \\rho_M$ for a message $m$ using the scheme's Sign algorithm, then compute $\\sigma_{m'} = U_{m'} U_m^{-1} \\sigma_m$ for a new message $m'$ and feed $(m', \\sigma_{m'})$ to Verify($pk_A$, $m'$, $\\cdot$). If Verification accepts, the Theorem is false, and the experiment requires solving no QMA problem.","tokens_in":11329,"feed_emoji":"🔐","tokens_out":8310,"duration_ms":76242,"temperature":0.7,"pith_summary":"The paper proposes a public-key quantum authentication and digital signature protocol in which each user's private key is a quantum circuit that prepares a highly entangled global state, and the public key is the set of all $k$-qubit reduced density matrices of that state. It claims that a forger who can produce a valid signature for an unqueried message would be able to construct a quantum witness solving the QMA-complete Consistency of Local Density Matrices (CLDM) problem, and therefore the scheme is existentially unforgeable under adaptive chosen-message attacks assuming $BQP \\neq QMA$. If true, this would be the first quantum public-key scheme needing no trusted third parties, no pre-shared secrets, and no authenticated classical channel, which is why a sympathetic reader would care.","feed_headline":"Quantum signatures claimed safe unless BQP=QMA","feed_subtitle":"The scheme treats local density matrices as a public key, removing the need for trusted third parties.","key_machinery":"The central object is the Consistency of Local Density Matrices (CLDM) problem, the QMA-complete decision problem of whether a set of local density matrices is compatible with some global quantum state. The construction hinges on three pieces: (1) the private key is an $N$-qubit state $\\rho_A$ with published $k$-qubit marginals as the public key; (2) a challenge-response step in which Bob demands an $M$-qubit fragment with $k < M < N$ and verifies its $k$-qubit marginals; (3) a message-dependent unitary $U_m$, publicly specified and efficiently invertible, that maps a fragment $\\rho_M$ to the signature $\\sigma_m = U_m \\rho_M$. Verification applies $U_m^{-1}$ and checks the local marginals against the public key. The QMA-completeness of CLDM is what is supposed to make reconstruction of the global state from the marginals intractable.","core_discovery":"On its own terms, the central claim is the theorem: the digital signature scheme built from a global private state and its published local marginals is existentially unforgeable against quantum adaptive chosen-message adversaries, provided $BQP \\neq QMA$. The proof proceeds by reduction: a successful forger outputs a state $\\sigma_E$ for a new message $m_E$; applying the inverse message-dependent unitary $U_{m_E}^{-1}$ yields a state whose marginals match the public key, exactly a valid witness for the CLDM instance given to the reduction. Since CLDM is QMA-complete, a convincing witness for a NO instance is impossible by soundness, and the existence of such a witness for a YES instance would let the reduction distinguish the cases, contradicting $BQP \\neq QMA$. The paper further argues that the protocol achieves authentication, non-repudiation, and transferability, and that verification can be done efficiently via partial quantum state tomography when $k$ is fixed.","pith_inferences":["Because $U_m$ is public, known, and invertible, one valid signature $\\sigma_m = U_m \\rho_M$ immediately yields a valid signature for any other message $m'$ by computing $U_{m'} U_m^{-1} \\sigma_m$; this does not require solving any hard problem and appears to break unforgeability as soon as a single signing query is answered.","The reduction's assertion that the challenger 'does not require B to answer the queries correctly' (Security Analysis, proof of unforgeability) is a step the argument would need to justify; if signing queries are not actually answered, the forger's success is no longer guaranteed, so the implication from forgery to CLDM witness may be empty.","The paper's own Lemma 1 shows that revealing the entire $N$-qubit state destroys security; the observation in the first inference indicates that even a single $M$-qubit signature fragment is enough, a stronger form of the same key-extraction vulnerability that the paper does not address."],"forward_implications":["If the theorem holds, quantum public-key authentication and signatures can in principle be built without a trusted third party, pre-shared secrets, or an authenticated classical channel.","The scheme offers non-repudiation and transferability: any party with the public key can independently verify a signature and pass it on.","For fixed subsystem size $k$, verification is efficient, requiring $O(4^k/\\epsilon^2)$ copies per subsystem for partial quantum state tomography.","A successful forgery would imply an efficient quantum algorithm for the QMA-complete CLDM problem, so the scheme's security rests on the assumption $BQP \\neq QMA$."],"supporting_citations":[{"why":"Supplies the core complexity result that CLDM is QMA-complete, the hardness assumption on which the security reduction rests.","marker":"[41]"},{"why":"Establishes the QMA-completeness of the related N-representability problem, reinforcing the marginal-consistency hardness the scheme uses.","marker":"[44]"},{"why":"Provides the QMA-completeness framework (via the local Hamiltonian problem) that underlies the CLDM complexity classification.","marker":"[45]"},{"why":"Defines existential unforgeability under adaptive chosen-message attacks, the exact security notion the paper claims to achieve.","marker":"[47]"},{"why":"Defines the quantum chosen-message attack model (EUF-qCMA) that the security game follows.","marker":"[48]"},{"why":"Supplies the quantum state tomography resource bound used to argue that verification is efficient.","marker":"[49]"}],"fun_headline_variants":["Quantum signatures secure unless BQP equals QMA","No trusted third party: quantum signatures via QMA","Public-key quantum signatures proven unforgeable unless BQP=QMA","Quantum digital signatures without trusted third parties","QMA-complete security for public-key quantum authentication"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The security proof assumes that a forger can be run even when the reduction does not answer signing queries, and that a single valid signature does not enable the adversary to sign fresh messages; under the protocol's own public, invertible $U_m$, the latter fails.","fun_headline_variants_meta":{"raw":{"variants":["Quantum signatures secure unless BQP equals QMA","No trusted third party: quantum signatures via QMA","Public-key quantum signatures proven unforgeable unless BQP=QMA","Quantum digital signatures without trusted third parties","QMA-complete security for public-key quantum authentication"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000278,"raw_usage":{"total_tokens":1632,"prompt_tokens":905,"completion_tokens":727,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":651}},"tokens_in":521,"tokens_out":727,"duration_ms":7257,"temperature":1.0,"reasoning_tokens":651,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:17:20.474639+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Prepare a legitimate signature $\\sigma_m = U_m \\rho_M$ for a message $m$ using the scheme's Sign algorithm, then compute $\\sigma_{m'} = U_{m'} U_m^{-1} \\sigma_m$ for a new message $m'$ and feed $(m', \\sigma_{m'})$ to Verify($pk_A$, $m'$, $\\cdot$). If Verification accepts, the Theorem is false, and the experiment requires solving no QMA problem.","supporting_citations":[{"cited_title":"Consistency of Local Density Matrices is QMA-complete","cited_arxiv_id":"quant-ph/0604166","evidence_quote":"Supplies the core complexity result that CLDM is QMA-complete, the hardness assumption on which the security reduction rests."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the QMA-completeness of the related N-representability problem, reinforcing the marginal-consistency hardness the scheme uses."},{"cited_title":"Goldwasser, S","cited_arxiv_id":null,"evidence_quote":"Defines existential unforgeability under adaptive chosen-message attacks, the exact security notion the paper claims to achieve."},{"cited_title":"Boneh and M","cited_arxiv_id":null,"evidence_quote":"Defines the quantum chosen-message attack model (EUF-qCMA) that the security game follows."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the quantum state tomography resource bound used to argue that verification is efficient."}],"review_version":2}