{"id":"2c028901-d3ad-4311-a7fa-bacc22c4bc99","arxiv_id":"2601.10542","paper_version":3,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper defines pHE-CD and gives a composition theorem plus two instantiations, but the written verification predicate in Construction 2 is a tautology or an impossibility, breaking the certified-deletion claim as stated.","lead":"This paper proposes hybrid encryption with certified deletion in a preprocessing model (pHE-CD), combining an information-theoretic key encapsulation mechanism with a data-encapsulation mechanism that supports certified deletion. A generalist might care because it targets long-term, post-quantum data deletion without per-message shared keys; however, the main construction as written contains a broken verification predicate.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The written D-CD.Vrfy predicate in Construction 2 is a tautology (cert_i = x'_i where x'=cert), so any certificate is accepted; if the intended all-position check cert_i = x_i is used, legitimate certificates fail with overwhelming probability. Theorem 5's imported hypothesis is therefore not satisf","rationale":"The reader's rejection identifies the most load-bearing flaw: the deletion-verification predicate in Construction 2 is internally inconsistent, and the security proof imports a theorem whose verification condition (θ_i=1 only) is not satisfied by the written algorithms. I read the construction carefully: Del measures |x>_θ in the Hadamard basis, so on θ=0 positions the certificate bits are random; Vrfy as written parses cert as x' and checks cert_i=x'_i, which is self-identity, so it always accepts. The natural correction cert_i=x_i for all i would reject valid certificates with overwhelming probability. The proof of Theorem 5 and the appendix's application of [3, Theorem 3.1] explicitly rely on a verifier that checks only positions where θ_i=1; this is absent from the construction. Because the certificate verification is the mechanism that unlocks the everlasting guarantee (the game gives K to A2 only if Vrfy returns ⊤), a broken Vrfy destroys the central claim. The hybrid-reduction structure of Theorem 4 is standard and could be sound with a corrected DEM-CD, as the reader notes, but as written the paper's main construction does not deliver certified deletion. I do not see a separate concern more load-bearing than this mismatch: the DEM-DEM hybrid step, the neglect of qe queries in the D-CD reduction, and the overclaim about removing computational assumptions are all secondary to the fact that verification is either vacuous or impossible. Therefore the reader's REJECT verdict stands unchanged.","tokens_in":15597,"tokens_out":3115,"duration_ms":34499,"concrete_test":"Implement the one-bit D-CD from Construction 2 exactly as written (e.g., in a quantum simulator): for random x,θ, message m, key K, produce C2=(|x>_θ, D.Encap(K,(θ, m⊕⊕_{θ_i=0}x_i))), then run Del to get cert and Vrfy(vk,cert). Check: (1) Does Vrfy accept cert=0^λ and other arbitrary strings? If yes, verification is vacuous. (2) For a legitimate cert, what fraction of runs does Vrfy accept under the written all-position check? Expected acceptance probability is 2^{-#θ_i=0}, i.e., negligible for large λ. (3) Replace the check with the [3]-style check 'for all i with θ_i=1, cert_i = x_i' and rerun; legitimate certificates should be accepted with probability 1 and arbitrary certificates should be rejected with probability 1-2^{-#θ_i=1}. This distinguishes the three possible verification predicates and shows the written construction does not satisfy the hypothesis of Theorem 8.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim — that Construction 2 provides EV-qe-CD security — depends on the deletion certificate being a meaningful witness of measurement in the Hadamard basis. In the construction, D-CD.Del measures |x>_θ in the Hadamard basis to get cert, and D-CD.Vrfy (as written in Construction 2, step 5, and identically in pHE-CD.Vrfy) parses vk=(x,θ) and cert as x', then outputs ⊤ if cert_i = x'_i for all i∈[λ]. Since x' is exactly cert, this condition is always true: Vrfy is a tautology and accepts every string, including 0^λ or any adversary-chosen certificate. If the intended check was instead cert_i = x_i for all λ positions, then a legitimate certificate fails with probability 1-2^{-#θ_i=0} ≥ 1-2^{-λ/2}, since on positions with θ_i=0 the Hadamard measurement gives a uniformly random bit. Neither reading delivers correct verification. The proof of Theorem 5 imports [3, Theorem 3.1] (restated as Theorem 8), whose deletion experiment checks x_i = x'_i only on positions i with θ_i=1. That hypothesis is not met by the written construction. Consequently the composed scheme's deletion-certificate verification is either vacuous or incorrect, and the security bound Advev-qe-cd ≤ 2Adv(iKEM)+Adv(D-CD) does not go through for the implemented verification. This is a load-bearing flaw in the central construction, not a stylistic issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces hybrid encryption with certified deletion in the preprocessing model (pHE-CD), combining an information-theoretic key encapsulation mechanism (iKEM) with a data encapsulation mechanism that supports certified deletion (DEM-CD). It defines EV-q-e-CD security for the composed scheme and gives two constructions: Construction 1, which is claimed to provide information-theoretic security for both encryption and deletion, and Construction 2, which uses an AES-based DEM-CD to provide computational encryption security and everlasting deletion security. The central claim is that, after a deletion certificate is successfully verified, confidentiality becomes information-theoretic. The paper proves a composition theorem (Theorem 4) and instantiates it via Construction 2 (Theorems 5–7).","tokens_in":44,"tokens_out":10096,"duration_ms":259293,"significance":"If the construction and proofs were correct, the paper would make a useful contribution: it extends certified deletion from the one-time-pad and public-key settings to the preprocessing model, where an iKEM from correlated randomness/QKD could be reused, and it aims to encrypt arbitrary-length messages with a constant-length key. The composition framework is clean, and the idea of combining an iKEM with a DEM-CD is natural. The formal definitions of pHE-CD and EV-q-e-CD security are a reasonable starting point. However, the central instantiation as written has a load-bearing verification bug, and the proof of the main deletion-security theorem relies on that broken predicate. The contribution is therefore not yet established, though the flaw appears locally repairable.","major_comments":[{"comment":"In Construction 2, step 5 of both D-CD.Vrfy and pHE-CD.Vrfy parses vk=(x,θ) and cert as x′, then outputs ⊤ if cert_i = x′_i for all i∈[λ]. Since x′ is simply the parsed certificate, this predicate is cert_i=cert_i, so every string is accepted. This is not a minor typo: an adversary can output an arbitrary certificate without touching the quantum register, receive K (because verification passes), and then measure |x⟩_θ in basis θ using K and recover m. Hence the scheme does not satisfy one-time EV-CD security, and Theorems 5 and 7 do not hold for the written construction. If the intended check was cert_i=x_i on all λ positions, honest deletion certificates fail with probability 1 − E_θ[2^{−#{{i:θ_i=0}}}] = 1 − (3/4)^λ, since Hadamard-basis measurement is uniformly random on θ_i=0 positions. Thus neither reading yields a correct verification. The fix is to verify only positions with θ_i=1,","section":"IV, Construction 2 (pHE-CD.Vrfy and D-CD.Vrfy, steps 4–5)"},{"comment":"The proof of Theorem 5 invokes [3, Theorem 3.1], restated as Theorem 8, whose deletion check is 'x_i = x′_i for all i such that θ_i=1'. That hypothesis is not satisfied by the written Vrfy, which either checks nothing or checks the wrong set. Moreover, the application in the Appendix does not instantiate Theorem 8 cleanly: the operation Z_λ is said to 'compute m′ := m⊕...' with m undefined, and the three inputs (θ, b′, A) of Theorem 8 are not matched to the construction. The concluding step 'by the correctness of the certified deletion procedure' is exactly what is at issue and cannot be assumed. The trace-distance conclusion is therefore unsupported.","section":"IV, Theorem 5 and Appendix, Theorem 8"},{"comment":"Definition II.8 states verification correctness as Pr[Vrfy(vk,cert)=⊥]=1, i.e., an honest certificate is rejected with probability 1. The intended property is certainly Pr[...=⊤]=1. As printed, the definition makes verification trivially 'correct' and the deletion experiment always outputs ⊥; it must be corrected before the security definitions are meaningful.","section":"II, Definition II.8"},{"comment":"Construction 1 is not actually specified or proved: the text says the description and proof are omitted because they 'largely follow' Construction 2. Since Construction 2's verification and proof currently fail, the information-theoretic pHE-CD of Construction 1 is not established by the manuscript. Please provide the explicit scheme and a self-contained proof (or a correct reduction to the fixed Construction 2). This is load-bearing because Construction 1 is one of the two advertised contributions.","section":"IV, Construction 1"}],"minor_comments":[{"comment":"Missing closing parenthesis in 'D.Encap(K,(θ, m⊕ L_{i:θ_i=0} xi)'.","section":"IV, Construction 2, step 2(c)"},{"comment":"Definition III.1 gives pHE-CD.KeyGen input (1^λ, P), but the algorithm in Figure 5 calls iK.KeyGen(1^λ) without P; align the notation.","section":"III, Figure 5"},{"comment":"The heading contains the typo 'delection'; should be 'deletion'.","section":"IV, Theorem 5"},{"comment":"The syntax returns (vk, CT) from Enc, but the security experiments send only CT to the adversary. It should be stated explicitly that vk is challenger-side and never revealed before deletion; otherwise a reader may think the verification key is public, which would break the scheme.","section":"II, Definition II.9 and III, Definition III.2"},{"comment":"The paper claims 'post-quantum' security for the DEM in Construction 2, but Definition II.4 quantifies over computationally bounded adversaries without specifying QPT. State the quantum adversary model explicitly.","section":"II, Definition II.4"},{"comment":"The concluding remarks mention Grover's bound as a basis for security, but the formal proofs in the paper do not use Grover. Either remove that remark or justify it.","section":"V, Concluding Remarks"}],"recommendation":"major_revision","confidential_remarks":"The central flaw in Vrfy is serious but appears repairable: changing the verification predicate to check only positions with θ_i=1, and reworking Theorem 5 and the appendix around that predicate, would likely make the composition argument go through. I do not see grounds for reject if the authors can supply the corrected construction and proof. The relationship to [3] should also be stated more transparently: Construction 2's DEM-CD is essentially the Bartusek–Khurana PKE-CD component with the public-key part replaced by an iKEM."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the pHE-CD formalism and the composition theorem are plausible, and the paper does a service by connecting iKEM to certified deletion, but the actual instantiation (Construction 2) has a verification predicate that is a tautology, so the headline deletion guarantee is not delivered. This is not a stylistic issue; it is in the code of Vrfy.\n\nWhat is genuinely useful: defining DEM-CD and EV-q_e-CD, and showing a hybrid composition that reduces pHE-CD security to iKEM IND-q_e-CEA plus DEM-CD EV-CD. The reduction in Theorem 4 is standard and appears formally correct given the components. The idea of using an iKEM to get reusable keys without public-key assumptions is worth having on the table.\n\nThe soft spot is load-bearing. In D-CD.Vrfy (and pHE-CD.Vrfy), the verifier parses vk=(x,θ) and cert as x', then accepts iff cert_i = x'_i for all i. Since x' is just cert, this accepts every string, including 0^λ. That means a malicious Bob can get the key released with no deletion at all, and the everlasting-deletion claim is empty. If the intended check was cert_i = x_i for all λ positions, honest deletion certs fail with probability at least 1-2^{-λ/2}, because on positions with θ_i=0 the Hadamard measurement is random. The imported [3, Thm 3.1] checks only positions with θ_i=1; the written construction does neither. The proof of Theorem 5 and the appendix paper over this mismatch.\n\nThere are smaller issues: Theorem 5's proof is a one-line import of [3] without showing its hypothesis is satisfied; Construction 1 is only sketched; Definition II.8's verification correctness asks Pr[Vrfy=⊥]=1, which is backwards; and the conclusion overclaims that no computational intractability assumptions are used, despite the IND-OT DEM (e.g., AES).\n\nI would not cite this version. The framework is salvageable — changing Vrfy to check only the θ_i=1 positions would likely make the intended argument go through, since that is exactly what Bartusek–Khurana do — but as written the central result does not hold. If I were the editor, I would send it to review rather than desk reject, because the framework deserves referee time and the fix is small; but it needs major revision before it is publishable.","headline":"The framework is a reasonable synthesis, but the central DEM-CD verification is a tautology, so the paper's main claim collapses; a one-line fix would make it worth revisiting.","tokens_in":16486,"tokens_out":3548,"would_cite":false,"duration_ms":35536,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60","81P94"],"pacs":[],"model":"deepseek-v4-flash","headline":"A verified deletion certificate in the proposed hybrid scheme is claimed to erase the message information-theoretically, even from a computationally unbounded adversary.","keywords":["certified deletion","hybrid encryption","preprocessing model","everlasting security","information-theoretic security","quantum cryptography","conjugate coding","key encapsulation mechanism"],"falsifier":"Take Construction 2's deletion and verification procedures with a single qubit: if the qubit is encoded in the computational basis and deletion measures in the conjugate basis, the returned bit matches the encoded bit only with probability 1/2. Under an all-positions check, a valid deletion is rejected half the time; under the written comparison, every certificate is accepted. Neither behavior simultaneously satisfies correctness and the imported theorem's hypothesis, so the construction as stated is not a working instantiation.","tokens_in":15386,"feed_emoji":"🔐","tokens_out":8305,"duration_ms":91371,"temperature":0.7,"pith_summary":"This paper tries to show that certified deletion—the ability for a sender to get a verifiable guarantee that a remotely stored file has been irreversibly erased—can be combined with hybrid encryption in the preprocessing model, where sender and receiver start from correlated randomness instead of a one-time pad. The central claim is a composition theorem: if the key-encapsulation component is information-theoretically secure against chosen encapsulation queries and the data-encapsulation component is one-time secure with everlasting certified deletion, then the combined scheme is secure against a computationally unbounded adversary after a deletion certificate verifies. This would matter because it promises everlasting deletion for arbitrarily long messages while keeping the sender's key reusable, removing the one-time-pad key-length cost and making the deletion guarantee independent of computational hardness assumptions. The paper gives two instantiations: one with fully information-theoretic security, and one that uses a block cipher for encryption while still aiming for everlasting certified deletion.","feed_headline":"Verified deletion outlasts even unbounded attackers","feed_subtitle":"Hybrid encryption plus quantum conjugate coding makes verified deletion irreversible even for infinite computation.","key_machinery":"The carrying object is the composition theorem (Theorem 4), together with a conjugate-coding DEM-CD. The iKEM supplies a key that is statistically close to uniform given the adversary's side information and ciphertext; the DEM-CD supplies a one-time certified-deletion mechanism whose verification step is intended to certify that the conjugate-coded qubits have been measured and therefore no longer carry information about the message. The composition transfers the one-time deletion guarantee to a scheme with many encryption queries, which is what allows arbitrarily long messages to be encrypted efficiently.","core_discovery":"On the paper's own terms, the discovery is that the hybrid-encryption framework—an information-theoretic key encapsulation mechanism (iKEM) paired with a data encapsulation mechanism—can be upgraded to support certified deletion, provided the data component is a DEM-CD. The security goal is EV-q_e-CD: after the adversary makes up to q_e encryption queries and then supplies a deletion certificate, if the certificate verifies, even a computationally unbounded adversary who is handed the decryption key cannot tell which of two messages was encrypted. The proof uses a hybrid game that swaps the real encapsulated key for a uniform key, bounding the gap by the iKEM's IND-q_e-CEA advantage, and the","pith_inferences":["The composition theorem suggests a direct route from quantum key distribution to certified deletion: any iKEM instantiated with QKD that can be upgraded to answer encapsulation queries would satisfy Theorem 4; the paper notes this as future work, but the theorem makes it a natural next step.","The one-bit Construction 2 is extended to multi-bit messages by encrypting bits independently; this parallel composition would need its own security argument, because the DEM-CD proof is stated for a single challenge and the paper does not provide an explicit multi-bit reduction.","An implementer should treat the deletion-verification predicate as a parameter and audit it before deployment: the security proof imports a check that only inspects positions encoded in the conjugate basis, whereas the written verification step describes either an always-true comparison or an all-positions comparison that almost always rejects a valid deletion."],"forward_implications":["If Theorem 4 is sound, any IND-q_e-CEA iKEM can be paired with any one-time EV-CD-secure DEM-CD to yield an EV-q_e-CD pHE-CD scheme, giving a modular route to certified deletion.","If Construction 2 is secure, a constant-length key suffices to encrypt arbitrarily long messages with quantum-safe encryption and everlasting certified deletion, eliminating the key-length dependence of one-time-pad-based schemes.","If the construction is secure, the deletion guarantee is everlasting: once the certificate verifies, the adversary's advantage is negligible even with unbounded computation, so future algorithmic breakthroughs would not retroactively break past deletions.","Both constructions use conjugate coding, which is implementable with current quantum technology, so the achieved functionality is not merely theoretical."],"fun_headline_variants":["Deletion certificates shield data from infinite compute","Hybrid encryption makes verified deletion unconditional","Everlasting security after a verified deletion certificate","Post-verification confidentiality beats any adversary"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof hinges on the deletion certificate being accepted exactly when the message-carrying qubits have been measured in the conjugate basis, but the verification step as written either compares the certificate to itself or demands agreement on all positions, so the certificate's validity does not certify loss of the message.","fun_headline_variants_meta":{"raw":{"variants":["Deletion certificates shield data from infinite compute","Hybrid encryption makes verified deletion unconditional","Everlasting security after a verified deletion certificate","Post-verification confidentiality beats any adversary"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000641,"raw_usage":{"total_tokens":2812,"prompt_tokens":796,"completion_tokens":2016,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":1971}},"tokens_in":540,"tokens_out":2016,"duration_ms":12227,"temperature":1.0,"reasoning_tokens":1971,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T10:16:29.840589+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take Construction 2's deletion and verification procedures with a single qubit: if the qubit is encoded in the computational basis and deletion measures in the conjugate basis, the returned bit matches the encoded bit only with probability 1/2. Under an all-positions check, a valid deletion is rejected half the time; under the written comparison, every certificate is accepted. Neither behavior simultaneously satisfies correctness and the imported theorem's hypothesis, so the construction as stated is not a working instantiation.","supporting_citations":[],"review_version":1}