Today, someone who stores an encrypted file on a remote storage service cannot prove that the file was really deleted. Encryption stops the service from reading the file today, but it doesn't stop the service from secretly keeping a spare copy. If the decryption key later leaks, that spare becomes readable. In their paper “Semi-Quantum Cryptography with Certified Deletion,” Yael Tauman Kalai of MIT and Justin Raizes of NTT Research provide a method for a classical computer to use a quantum server so that deletion makes the data inaccessible even if the key is compromised.[1]
Storing private encrypted information on a remote system run by a cloud service or other provider is a routine business process across verticals. A medical clinic may keep imaging files with a records host. A commercial company may keep customer records with a cloud storage provider. An individual may keep backups with a file service. In each case, the owner wants the service to hold the file, sometimes compute on it, and later erase it on command or when the retention period ends. Encryption ensures confidentiality; the storage service receives an encrypted copy of the user’s data and does not have the key.
When a classical computer stores the user’s data, encryption's protection has limits. The encrypted file is a string of bits which can be duplicated to create one or more identical copies without changing the original. A cloud service asked to erase a file can delete the copy it shows the owner and retain another in a different location. The decryption key then becomes the sole control mechanism, and such keys are often lost, stolen, or turned over under legal process. Once a copy of the encrypted data and the key are in the same hands, the data becomes accessible.
Quantum storage changes that equation. The encrypted data is held as a quantum state, a form of information that a measurement disturbs. In their 2020 paper, Anne Broadbent and Rabib Islam showed that this disturbance can verify deletion. To produce a valid deletion certificate, the server must measure the stored state. That measurement destroys the part of the state the key would later use. If the certificate is valid, a later key leak does not help because the copy that the key would have unlocked is gone.
The certificate is an ordinary string of bits, so an ordinary computer can check it. Public verification means the check does not depend on trusting the cloud or other storage service. The data owner, or anyone else with the verification key, runs a check that accepts or rejects the certificate. Acceptance shows that the holder of the encrypted data stored in the quantum state can no longer recover it. The same public check can also be used when the owner does not want the file discarded; it can test whether a third party holds a copy that would become readable if the key leaked.
The problem with this verification methodology was that preparing and uploading the quantum ciphertext required quantum hardware and a quantum link. Checking whether a copy had been stolen could require direct quantum access to the stored state. Getting the file back often meant converting the quantum version of the encrypted data into a classical version and then transmitting it to the client. In this case, the converted data becomes a permanent copy that a later key leak could compromise, exposing it, and the owner was forced to choose between being able to retrieve the data and being able to trust the deletion guarantee.
Earlier proposals for methods a classical computer could use to send encrypted data to a quantum server had significant limitations. One 2021 method let only the owner check the deletion, and its proof assumed an idealized calculator that real computers lack. Another allowed anyone to check the deletion, but only by assuming two tools that cryptographers do not know how to build. No method worked from a standard hardness assumption and still let anyone check the certificate. A separate test, which asks whether a copy was stolen without destroying the stored file, still required the owner to send quantum data.
The researchers provide a general method that enables the data owner to send encrypted information from a classical computer and later prove the server cannot read it. The owner never has to use a quantum device or send a quantum message. Anyone can check the deletion certificate, so the owner does not have to take the server’s word that the file is gone. The method’s security rests on the Learning With Errors (LWE) problem, a standard math problem widely believed to stay hard even for a quantum computer, rather than on an idealized calculator or on tools nobody knows how to build. Starting with an already secure encryption scheme, the method adds a classical upload and a public deletion check. It covers sending a file to a named recipient and letting a server compute on data it cannot read. The recipient still decrypts with the key already in use. A verified deletion still hides the file if that key later leaks.
In the researchers’ method, the data to be stored starts on the owner’s classical computer. The owner generates two sets of public numbers, keeps a private key for each set, and sends only the public numbers to the quantum storage server. The server uses the public numbers to prepare a quantum state locally. A quantum state is information stored so that measuring it changes it. The server sends back two classical results that identify the state it prepared, then proves that it holds the hidden inputs matching those results.
The server then measures one part of the quantum state, sends that measurement to the owner, and keeps the rest. The owner uses a private key that was never transmitted to compute a bit string from the measurement, then combines that bit string with the data. The owner encrypts the combined result under the public key of the person allowed to read the data. If the owner is storing the data for personal use, that public key is the owner's. This is the same kind of key a mail program uses to send a file to a named person. The server can store the encrypted result.
The server cannot read the uploaded data. It holds the remaining quantum state, which contains the bit-string information needed to recover the data from the encrypted result. Neither the remaining quantum state nor the encrypted combined result reveals the data on its own. Reading the data requires both, plus the recipient’s private key. When the owner wants the data destroyed, the owner asks the server to measure the remaining quantum state and return the result. That result is a classical string. Anyone can check it with a published checking key, and the measurement destroys the bit-string information. If the check succeeds, a later leak of the recipient’s private key can open the encrypted result, but the bit-string information on the server is gone, so the data remains inaccessible.
The proof prevents the server from learning the bit string. If the server could keep the two parts of its quantum state separate, it could compute that bit string, delete one part, and still recover the data once the recipient’s private key leaked. The proof ties the two parts together, so the server cannot do that. The security proof does not change the messages the owner and server exchange.
The researchers are explicit about what their method does not achieve. It does not prove that the server is storing the quantum state it claims to store. A cheating server can do the calculation on a classical computer and still pass this test. The method fits this deletion scheme because the earlier proof already included a place for this step. It does not turn every protocol that used to require a quantum message into one that uses only classical messages.
The same method supports several different use cases. The encrypted combined result can be encrypted again for a named recipient. It can also be locked so the sender cannot later claim the dataset was different. It can be encrypted in a form that lets the server compute on the data without reading it. Earlier methods that used only classical messages for the upload could not support that computation. This method can. The deletion check applies to the stored data, not to the result of a computation. After the server computes, it returns the result, reverses the computation, and then deletes the restored stored data.
The method also enables the owner to test whether someone stole a copy that would become readable if the private key leaked, without destroying the stored data. The server proves that it still holds a valid deletion result, then reverses that step. The stored data can still be decrypted, and the test can be run again. One guarantee rests on LWE alone: an intruder who has the private key still cannot recover the data. A stronger guarantee, that the intruder cannot even tell which data set it was, requires an idealized model that real computers do not provide.
Retrieval is a separate exchange, and both sides use classical messages. The owner holds the private key. The server holds the stored data. Before the server measures its quantum state, the owner binds that state to a new set of public numbers and adds a new bit string. The owner receives the data. The server is left with a record that can be opened only with random bits the owner then discards. If the private key later reaches the server, the data stays hidden. The owner no longer has to choose between reading the data and keeping the deletion protection.
The protection provided by the researchers’ method is not absolute. Absolute protection would hide the data from an attacker with unlimited computing power. The researchers say that is unlikely here, because the classical messages from the upload remain, and those messages determine what the server prepared. The random bits used in the encryption can be thrown away as soon as the encryption operation is complete. The private key is the lasting secret the proof assumes can leak. Against an attacker limited to a realistic amount of computing, including an attacker with a quantum computer, an accepted deletion check means the stored copy is no longer useful if that key leaks.
The paper does not say when a quantum storage service could offer this capability, and it does not tell an owner or a regulator what to do. It provides the method, the proof, and the limits. Within those limits, an owner can upload the data with a classical computer, test for a stolen copy without destroying the stored data, and retrieve the data in an exchange that also deletes it. The checks are public, and the proof rests on LWE alone. The method does not replace every protocol that sends a quantum state, nor does it protect against an attacker with unlimited computing power or prove that the server is storing a quantum state rather than doing the calculation on a classical computer and still passing this test.
The research points toward a path to a hybrid quantum computing future, where only one side of an exchange, the storage service, is required to have a quantum computer. The owner continues to use a classical computer and gets a deletion check that keeps the data hidden if the private key leaks later.
This article is shared at no charge for educational and informational purposes only.
Red Sky Alliance is a Cyber Threat Analysis and Intelligence Service organization. We provide indicators of compromise information (CTI) via a notification/Tier I analysis service (RedXray) or an analysis service (CTAC). For questions, comments, or assistance, please contact the office directly at 1-844-492-7225 or feedback@redskyalliance.com
- Reporting: https://www.redskyalliance.org/
- Website: https://www.redskyalliance.com/
- LinkedIn: https://www.linkedin.com/company/64265941
Weekly Cyber Intelligence Briefings:
REDSHORTS - Weekly Cyber Intelligence Briefings
https://attendee.gotowebinar.com/register/7855487668891299929
[1] https://six3ro.substack.com/p/when-physics-proves-that-deleted
Comments