Technical Summary: Semi-Quantum Cryptography with Certified Deletion

1. Problem Statement

The paper addresses the challenge of Certified Deletion in a Semi-Quantum setting. Certified deletion allows a client to upload encrypted data to a server as a quantum state and later request that the server delete the data, providing a verifiable certificate that the server can no longer recover the data even if the decryption key is subsequently leaked.

While previous works established certified deletion for various primitives, they typically required the client to possess quantum capabilities for the initial upload and management of the data. Specifically:

• Upload: Preparing and uploading the initial quantum ciphertext required quantum communication.
• Auditing: Detecting whether data had been stolen (intrusion detection) often required coherent access to the stored ciphertext.
• Retrieval: Retrieving data while simultaneously deleting it from the server was difficult without leaving a permanent classical copy that could be decrypted if the key leaked later.

The central question posed is: Can a classical client upload, audit, and erase or retrieve encrypted data from a quantum server while protecting against future key leakage?

2. Methodology and Core Techniques

The authors propose a general compiler that converts any semantically secure cryptographic primitive (e.g., PKE, ABE, IBE, FHE, Commitments) into a version with certified deletion where the initial upload is purely classical. The construction relies on the post-quantum hardness of the Learning With Errors (LWE) problem in the plain model.

2.1 Ciphertext Design: Phase Injection

The core construction utilizes Trapdoor Claw-Free Functions (TCFs) and the Adaptive Hardcore Bit property. Unlike prior approaches that used preimages to hide the message and the Hadamard basis for deletion, this work inverts the relationship:

• Message Encoding: The message $m$ is encoded in the phase of a quantum state.
• Certificate: The preimages of the TCF serve as the deletion certificate.

The resulting ciphertext takes the form of a quantum state:
$$|0, x_0\rangle + (-1)^p |1, x_1\rangle$$
where $p$ is related to the message ($p \oplus m$). The classical share contains $(p \oplus m, td_A)$, where $td_A$ is the trapdoor for the TCF instance $A$.

Decryption: The client measures the quantum state in the Hadamard basis to recover the phase $p$, then uses the trapdoor $td_A$ to recover the preimages and unmask $m$.
Deletion: The server measures the state in the computational basis to obtain a preimage ($x_0$ or $x_1$). This measurement destroys the phase $p$, rendering the message unrecoverable even with the trapdoor.

2.2 Classical Upload via Entanglement

To enable a classical client to upload this quantum state, the authors develop a protocol using two TCF instances ($A$ and $B$) and Witness-Preserving Arguments of Knowledge (based on [KKR26]):

1. The server prepares a superposition over preimages for both TCFs.
2. The client challenges the server to prove knowledge of preimages for both instances using the same bit $b$ (entangling the two instances).
3. The server measures the preimages of instance $B$ in the Hadamard basis. This measurement injects a phase $p_B$ into the superposition of instance $A$.
4. The client computes the phase $p_B$ and sends back an encryption of $(p_B \oplus m, td_A)$.

This process forces the server to hold an entangled state where the phase is determined by the measurement of the second TCF, allowing the client to verify the state's integrity without quantum communication.

2.3 Purification Over Classical Channels

A major technical hurdle is adapting purification-based security arguments (common in BB84-style proofs) to a setting where the state is prepared via classical interaction. In standard quantum proofs, the challenger can prepare a state in superposition. Here, the classical transcript uniquely determines the state.

The authors introduce a Phase Injection Lemma and a simulation technique to overcome this:

• Indistinguishable Extraction: The protocol uses a unitary extractor to coherently extract the witness (preimages) from the server's state, apply a phase shift (Z-gate), and then invert the extractor to return the witness.
• Purification: This allows the security reduction to treat the phase as being in a superposition (purified) even though the transcript is classical. The reduction can "purify" the choice of the phase by controlling whether a Z-gate is applied, making the server's view indistinguishable from a scenario where the phase was chosen coherently.

2.4 Advanced Management Features

• Proofs of No Intrusion (PoNI): Using the generic compiler from [KKR26], the scheme supports non-destructive auditing. The server can prove it holds a valid deletion certificate without destroying the ciphertext, allowing the client to verify the data hasn't been leaked to a third party.
• Decryption with Deletion: The paper presents an interactive protocol where a classical client retrieves the message while simultaneously deleting it from the server. This is achieved by rerandomizing the ciphertext (adding a fresh phase) before converting it to a classical form, ensuring that even if the server later learns the decryption key, the original message remains hidden.

3. Key Results

The paper establishes the following main results, assuming the post-quantum hardness of LWE:

1. General Compiler: A compiler exists that transforms any primitive $X \in \{\text{Secret Sharing, PKE, ABE, IBE, Commitments, FHE}\}$ into a semi-quantum version with publicly verifiable certified deletion and classical upload.
2. Publicly Verifiable: The deletion certificates are classical and can be verified by anyone, enabling non-destructive auditing.
3. Classical Retrieval: The client can retrieve the plaintext while ensuring the server deletes the data, preventing future key-leakage attacks on the retrieved data.
4. Specific Constructions:
   • Semi-Quantum Secret Sharing: A 2-out-of-2 scheme with certified deletion.
   • Public-Key Encryption (PKE), ABE, IBE: Schemes where the ciphertext is a quantum state, but the upload is classical.
   • Commitments: Schemes with computational hiding and collapse binding.
   • Fully Homomorphic Encryption (FHE): Supports coherent evaluation of circuits on quantum ciphertexts with certified deletion.

4. Significance and Claims

The authors claim the following significance for their work:

• Bridging the Gap: The work solves the open problem of enabling fully classical clients to manage quantum-encrypted data (upload, audit, delete/retrieve) without requiring quantum infrastructure.
• New Technique: The primary technical contribution is a method to apply purification-based security arguments to states prepared via classical interaction. This technique allows the security reduction to maintain a "purified" view of the state despite the classical transcript uniquely determining the state in a real execution. The authors note this technique may be of independent interest for other quantum cryptographic constructions.
• Broad Applicability: The compiler is generic, applying to a wide range of primitives including advanced encryption schemes like ABE and FHE, which were previously incompatible with certain certified deletion approaches (e.g., those requiring receiver non-committing encryption).
• Modest Assumptions: The constructions rely only on the post-quantum hardness of LWE in the plain model, avoiding complex primitives like extractable witness encryption or one-shot signatures required by prior classical-upload attempts.

The paper explicitly states that while their technique achieves certified deletion and management capabilities, it does not achieve simulation-security or verifiability in the strict sense of Remote State Preparation (RSP), as an adversary could theoretically evaluate the TCF classically. However, for the specific goal of certified deletion, the provided indistinguishability guarantees are sufficient.