THE QUANTUM INTELLIGENCER

A preprint now on the arXiv proposes a unified framework for certified deletion, and the central fact is quantitative: where earlier constructions consumed a linear number of qubits for each encrypted bit of certified-deletable plaintext, the new construction achieves a constant rate in the plain model while preserving everlasting security. The framework covers the broad class of all-or-nothing primitives built on BB84-style encodings, among them commitment schemes, public-key encryption, attribute-based encryption and fully homomorphic encryption, and extends further to constructions from subspace coset states, including blind delegation, secure software leasing, functional encryption, differing-inputs iO and CCA-secure public-key encryption. It introduces no additional assumptions beyond those the underlying certified-deletion primitives already require. Under the hardness of the Short Integer Solution problem, public verifiability can likewise be incorporated into the BB84- and coset-based schemes. The paper is a preprint. The desk records it as a preprint: promising, of note, and not yet a settled finding. The reader will pardon a short glossary before we proceed, for the value of this paper lies in a handful of precise instruments, and each must carry its full weight. A qubit is the quantum counterpart of the ordinary bit, and the unit in which the constructions are counted. Certified deletion is the property the framework supplies. A receiver who chooses to destroy a quantum ciphertext performs a prescribed measurement and returns the classical outcome as a certificate; the sender, checking the certificate, learns that the plaintext can no longer be recovered. The weight rests on the adjective: ordinary deletion is asserted, certified deletion is demonstrated by a record of measurement that quantum mechanics will not reconcile with retention of the data. The rate of a scheme is the number of qubits spent for each encrypted bit of plaintext. A constant rate is one that does not grow with the length of the message; doubling the message doubles the cost, and no more. The plain model, in the cryptographer's usage, is the absence of trusted scaffolding: no common reference string, no idealized random oracle, no authority distributing parameters. The parties carry only the protocol and their own randomness, and a proof obtained in this model holds wherever the mathematics is correct. Everlasting security is a guarantee against deferred computation. The adversary is assumed bounded while the protocol runs, but after the protocol is complete no bound is placed on its future powers. For an age of harvest-now-decrypt-later, this is the property that closes the door: a ciphertext that is everlastingly secure does not become readable when the adversary's machine at last arrives. The certificate's assurance, too, is everlasting. BB84-style encodings take their name from the 1984 protocol of Bennett and Brassard, in which each bit is carried by a quantum state chosen from one of two incompatible bases. The incompatibility is the engine: a receiver who lacks the basis cannot extract the bit without disturbing the state, and the disturbance is detectable. Subspace coset states are a more algebraic instrument: a uniform superposition over the elements of a hidden coset of a subspace of a binary vector space. The paper's phrase all-or-nothing describes the primitives to which the framework attaches itself: commitment schemes, encrypted messages and the like, in which possession of the whole yields everything and possession of any proper part yields nothing. One may think of the coset state as the quantum embodiment of that structure. The Short Integer Solution problem asks for a short, nonzero integer vector satisfying a prescribed homogeneous linear system modulo a modulus. Its hardness is conjectured rather than proven, but the literature has long treated it as a reasonable foundation. The authors invoke it to add public verifiability, by which any party holding the deletion certificate can confirm deletion without private state. The certificate becomes a public record rather than a private acknowledgment. Here end the definitions. The instruments are now in their places. Let the boundary be drawn with the same care as the size. What the paper offers is an improvement in an efficiency parameter. It takes certified-deletion primitives that already exist in the mathematical sense and renders them cheaper by a constant factor; it does not conjure those primitives into being, and still less does it place them in silicon. The demonstrations are in the proofs, not in the laboratory. No measurement of a device appears, no physical implementation is claimed, and no existing scheme is reported to have changed its behaviour. The framework's breadth runs across a class of theoretical objects, and that class is genuinely wide; but the whole edifice remains a theorem about how constructions may be composed, rather than a report of anything that has yet been built. That is a narrowness of territory, not of achievement. For the engineer, the constant rate is the fact that matters; for the auditor, the absence of hardware is the fact that keeps the matter in the ledger of things yet to be done. —Ada H. Pemberley Dispatch from The Prepared E0