PaperlayerView exact revision on arXiv

Source-linked AI summary

Semi-Quantum Cryptography with Certified Deletion

Yael Tauman Kalai, Justin Raizes

arXiv:2609.38915v1cs.CRquant-ph

TL;DR

Classical clients need ways to upload and manage encrypted data on quantum servers without relying on client-side quantum operations. This paper gives a compiler and classical protocols for certified deletion, auditing, and retrieval under post-quantum LWE hardness. The constructions provide publicly verifiable deletion across several primitives, with retrieval that hides the message from the server even given the decryption key.

  • Problem

    Classical clients need to upload and manage encrypted data on quantum servers, while ordinary classical ciphertexts can be copied without detectable erasure.

    Source: §1 · p. 3

  • Method

    The paper gives a compiler and simulation technique for classical upload of quantum ciphertexts, plus classical protocols for auditing and retrieval with deletion.

    Source: §1 · p. 4, §1.1 · p. 5

  • Results

    Assuming post-quantum LWE hardness, the paper constructs publicly verifiable certified deletion for several primitives and supports non-destructive audits and retrieval that hides the message from the server even given the key.

    Source: §1 · p. 4, §1.1 · pp. 4–5

  • Takeaways & Limitations

    A classical client can audit ciphertext without destroying it and retrieve the message while deleting the server copy.

    Source: §1.1 · p. 5

    The construction does not provide everlasting security: the classical transcript cannot be deleted and information-theoretically determines the prepared state.

    Source: §2 · p. 6

Abstract

from arXiv · show

Certified deletion allows a client to upload encrypted data to a server as a quantum state, then later request that the server delete their data and detect whether the server complies. If verification passes, then the data on the server will remain hidden even if the decryption key is later leaked. In publicly verifiable certified deletion, the verification key is published so that anyone may check for deletion compliance. In this work, we give a general compiler to publicly verifiable certified deletion that allows the client to initially upload the *quantum* ciphertext using purely *classical* communication, assuming the post-quantum hardness of LWE in the plain model. Our approach can be applied to a wide variety of primitives, including commitments and public-key, attribute-based, identity-based, and fully-homomorphic encryption. Moreover, our constructions allow the client to classically manage the encrypted data beyond just verifying its deletion. The classical client may non-destructively audit the ciphertext via a Proof of No Intrusion to check whether it has been leaked to a third party. The classical client may also retrieve the data while simultaneously verifying its deletion from the server. Thus, they do not have to choose between retrieving the data and protecting it against future key leakage. As our core technical contribution, we give a classical-communication protocol and simulation technique that allows adapting purification-based security arguments for BB84-style states which are prepared through classical interaction. It makes the required purification available in a hybrid experiment, despite the classical transcript uniquely determining the prepared state in a real execution.

1 Introduction

The introduction presents a classical-client approach to certified deletion, motivated by the difficulty and cost of quantum operations for clients. It gives a compiler, auditing and retrieval procedures, and a technique for adapting purification-based security arguments to classically prepared states.

1 Introduction

  • Classical-client management addresses the cost of quantum infrastructure for individual users, while retrieval matters because converted ciphertexts can remain exposed to future key leakage.The introduction notes that prior auditing work required an initial quantum upload and that classical upload remained open.Source: §1 · p. 3
  • Earlier classical-upload certified-deletion PKE relied on the quantum random oracle model or stronger assumptions, while a plain-model construction from standard assumptions remained open.The paper contrasts its approach with.Source: §1 · p. 3, §1.1 · p. 4

1.1 Results

  • Assuming post-quantum LWE hardness, the compiler provides publicly verifiable certified deletion with classical upload for commitments and several encryption and sharing primitives.The stated scope includes secret-sharing, PKE, ABE, IBE, commitments, and fully homomorphic encryption.Source: §1 · p. 4, §1.1 · p. 4

1 Introduction

  • A classical preparation protocol and simulation make purification available in a hybrid experiment, enabling entanglement-based security arguments for BB84-style states prepared through classical interaction.In a real execution, the classical transcript uniquely determines the prepared state.Source: §1 · p. 4

1.1 Results

  • Publicly verifiable deletion certificates support non-destructive Proofs of No Intrusion, allowing classical clients to audit uploaded ciphertexts for possible theft.The audit leaves the ciphertext intact and answers an open problem from.Source: §1.1 · pp. 4–5
  • The interactive classical Dec-Del procedure lets the client retrieve the message while the server remains unable to learn it, even given the decryption key.The protocol combines message recovery with deletion from the server.Source: §1.1 · p. 5

2 Technical Overview

This technical overview presents phase-encoded TCF ciphertexts for classical upload and techniques for preparing and analyzing them, including purification-based deletion proofs over classical channels. It also discusses no-intrusion testing, deletion during decryption, and limitations arising in this approach.

2 Technical Overview

  • Certified deletion requires the message to remain hidden after decryption-key disclosure; everlasting security against unbounded adversaries is unlikely with classical upload because the undeletable transcript determines the prepared state.Source: §2 · pp. 5–6

2.1 Ciphertext Design

  • The ciphertext encodes a message mask in a TCF claw state's phase, uses publicly checkable preimages as deletion certificates, and can encapsulate the mask and trapdoor under semantically hiding primitives.This supports examples including ABE, commitments, IBE, and FHE.Source: §2.1 · pp. 6–7

2.2 Abstract Framework for Preparation of Hadamard States

  • Witness-preserving arguments retain the tested claw and can achieve negligible knowledge error; coherently extracting its witness and applying Z lets the same transcript prepare either |+⟩ or |−⟩ for purification.The phase-injection change remains indistinguishable when the revealed phase is updated to p⊕1.Source: §2.2 · pp. 8–9

2.3 Classical Upload

  • Two TCF instances create an entangled A claw whose preimages serve as the deletion certificate, while measuring B in the Hadamard basis adds the message phase to A.The witness-preserving argument ensures the required entanglement is retained during preparation.Source: §2.3 · pp. 9–10

2.4 Analysis: Entanglement Over Classical Channels

  • BB84-style purification adapts to classical preparation by decoupling phase from transcript; a valid deletion certificate forces register P into H|b⟩, limiting distinguishing advantage to 2·negl(λ).The argument relies on hardness of finding both preimages and on measuring the phase register in incompatible bases.Source: §2.4 · pp. 11–12
  • Indistinguishable-extraction uses a unitary extractor and its inverse to extract a witness while returning the prover’s view to an indistinguishable state without unnecessarily measuring the witness.The guaranteed extractor can be approximated by a polynomial-size unitary, yielding an arbitrarily small inverse-polynomial error; the same protocol remains secure for smaller error parameters, at the cost of a longer reduction.Source: §2.4 · pp. 12–13
  • The phase-injection lemma makes changing pB to pB ⊕ p′ indistinguishable even when the modified phase is revealed, enabling purification of the phase choice.Four hybrid experiments decouple the injected phase from the reported bit to establish the required indistinguishability relations.Source: §2.4 · pp. 13–14

2.5 Proofs of No-Intrusion and Classical Decryption with Deletion

  • A Proof of No Intrusion lets a classical client test whether a ciphertext exists outside the server while preserving it for later decryption or retesting.The generic compiler of Kalai, Khurana, and Raizes uses a witness-preserving argument of knowledge for a superposition of classical, publicly verifiable certificates, then uncomputes that superposition.Source: §2.5 · p. 15
  • Rerandomizing the quantum ciphertext before Hadamard-basis conversion lets a classical client learn the plaintext while deleting the server’s ciphertext without exposing the message to later key leakage.The client remotely adds a fresh phase through entanglement and a witness-preserving argument; the converted ciphertext decrypts to m ⊕ p′, with p′ discarded after decryption.Source: §2.5 · pp. 15–16

2.6 Discussion and Related Works

  • The preparation technique lacks simulation-security and verifiability, but offers a simple, efficient method for protocols whose security relies on BB84 purification arguments.An adversary can evaluate the function classically and pass the test; verifying a Hadamard-basis measurement is difficult because it requires a secret trapdoor, whereas the cited witness-preserving argument supports only publicly verifiable statements.Source: §2.6 · p. 16
  • Earlier classical-upload work includes publicly verifiable certified-deletion PKE using quantum random oracles or extractable witness encryption and one-shot signatures, and PoNI constructions whose original ciphertext upload requires quantum communication.Goyal and Raizes’ LWE-based PoNIs achieve search security in the plain model and decisional security in the quantum random oracle model; Kalai, Khurana, and Raizes [KKR26] give a generic compiler, with QROM for decisional security.Source: §2.6 · p. 16
  • Classical-upload secure key leasing suggests a route to certified deletion, but requires ciphertext equivocation and publicly verifiable revocation for public verifiability.Equivocation rules out fully homomorphic encryption; publicly verifiable revocation would imply public-key quantum money, currently known only from strong assumptions such as indistinguishability obfuscation.Source: §2.6 · p. 17
  • Other classical-upload work covers certified-deletion NIZKs and coset-state copy protection, with search-style security notions for each.The cited coset-state constructions assume sub-exponential LWE and indistinguishability obfuscation hardness, and their remote state preparation targets coset-state monogamy of entanglement and direct-product hardness.Source: §2.6 · p. 17

3 Preliminaries

The preliminaries establish the trapdoor-function assumptions and witness-preserving tools used in the paper’s security analysis. They also introduce indistinguishable extraction, which exposes a witness coherently and returns it without collapsing the prover’s state.

3 Preliminaries

  • The preliminaries use ≈c for computational indistinguishability against quantum polynomial-time algorithms and ≈s for statistical indistinguishability against unbounded quantum adversaries.A distribution is semantically hiding when its outputs for any two inputs are computationally indistinguishable.Source: §3 · pp. 17–18

3.1 Trapdoor Claw-Free Functions

  • Dual-mode trapdoor claw-free functions have computationally indistinguishable lossy and injective modes, and quantum-hard LWE yields balanced families with adaptive hardcore bits.The preliminaries also recall collapsing and trapdoor inversion properties used in the security arguments.Source: §3.1 · pp. 18–19

3.2 Witness-Preserving Arguments for NP

  • A witness-preserving argument lets a quantum prover convince a classical verifier while preserving its witness superposition, with an NP construction under post-quantum LWE.The cited construction achieves witness preservation with error 2^-λ.Source: §3.2 · pp. 20–21

3.3 Quantum Extraction for Arguments of Classical Knowledge

  • Indistinguishable extraction addresses the conflict between extracting a witness and preserving the prover’s state in a witness-preserving argument.The section contrasts it with state-preserving extraction, where obtaining the transcript and extracted witness together collapses the witness.Source: §3.3 · p. 21
  • Indistinguishable extraction simulates an adversarial view while coherently extracting a witness, then returns the witness without collapsing the prover’s state.A collapsing commitment yields statistically ε-indistinguishable extraction, and this combines with a witness-preserving argument to give approximate indistinguishable extraction for NP under the stated trapdoor-function assumption.Source: §3.3 · pp. 21, 23

4 Phase Injection Lemma

The phase-injection lemma considers whether an adversary can detect a phase inserted into a superposition of trapdoor-function preimages when the later-revealed inner product is adjusted by that phase. Under adaptive hardcore bits, the adversary’s success is at most 1/2 plus a negligible term.

4 Phase Injection Lemma

  • An adversary’s probability of winning the phase-injection game is at most 1/2 + negl(λ) for a dual-mode trapdoor claw-free function with adaptive hardcore bits.The game inserts a Z phase into the first qubit of the preimage register and adjusts the later inner-product response by the phase.Source: §4 · p. 24
  • The lemma’s game gives the adversary public parameters and a preimage register for a classical function output before the challenger applies the phase and reveals a response.The adversary then supplies a string d and guesses the challenge phase bit.Source: §4 · p. 24
  • The proof defines four hybrids, with the original game at phase bit p equal to Hyb_pp, then compares their adversarial views.Averaging over the response bit makes it independent of whether the inner product is valid, allowing use of the collapsing property; the remaining phase distinction reduces to adaptive hardcore bits.Source: §4 · pp. 24–25

5 Semi-Quantum Secret Sharing with Certified Deletion

This section formalizes a 2-out-of-2 secret-sharing scheme that splits a secret bit into classical and quantum shares, and constructs a scheme with publicly verifiable deletion security under adaptive semantic hiding. Its security analysis uses hybrid experiments to show that the adversary’s distinguishing advantage changes negligibly and reaches an experiment independent of the message, with one transition relying on a key measurement predicate holding with overwhelming probability.

5 Semi-Quantum Secret Sharing with Certified Deletion

  • The core construction generates classical and quantum shares of a random bit, allowing the quantum share to be certifiably deleted or both shares to recover the bit.Source: §5 · p. 26

5.1 Definition

  • The 2-out-of-2 interface has a classical sender and quantum receiver produce a verification key and classical share alongside a quantum share, with reconstruction, deletion-certificate, and verification algorithms.Source: §5.1 · p. 26
  • Auxiliary information may be split into two stages, allowing a public key before sharing and an encryption of the classical share as later information.This accommodates settings where the adversary uses the first-stage information during the sharing protocol.Source: §5.1 · pp. 27–28

5.2 Construction

  • The constructions yield publicly verifiable Z-deletion security for every Z satisfying adaptive semantic hiding, using primitives that exist under post-quantum LWE.The required tools are a dual-mode trapdoor claw-free function family with adaptive hardcore bits and a witness-preserving NP argument of knowledge.Source: §5.2 · pp. 28, 30

5.3 Analysis

  • Reconstruction is correct because the quantum share is negligibly close to a claimed coset state, whose Hadamard-basis measurement yields a bit that recovers the message by XOR.Source: §5.3 · p. 31
  • The deletion-security proof uses hybrids to extract a witness, insert and purify a random phase, replace the masked message with a random bit, and reach an experiment that does not use the message.The final hybrid checks the certificate and phase register, then outputs ⊥ with probability 1/2 anyway.Source: §5.3 · p. 32
  • Hyb0-to-Hyb1 changes the distinguishing advantage by at most 2ε/3; the phase-injection step to Hyb2 is negligible, and Hyb3 is equivalent to Hyb2.Source: §5.3 · pp. 32–33
  • In Hyb5, the check aborts with probability 1/2 independently of m, yielding Hyb6, which is independent of m.Source: §5.3 · p. 33
  • The Hyb4-to-Hyb5 distinguishing advantage changes negligibly because the measurement on P outputs H|b⟩⟨b|H with overwhelming probability.The proof uses truncated hybrids to establish the measurement condition; the corresponding predicate holds with overwhelming probability in Hyb5.Source: §5.3 · pp. 33–34
  • The proof replaces Z2(csh; r) with Z2(0; r) using adaptive semantic hiding, then uses a reversed controlled-Z and the claw-free property of F to rule out an incorrect accepting certificate.These steps rely on r not being revealed and on csh, hence tdA, remaining unrevealed in the relevant hybrid.Source: §5.3 · p. 34

6 Applications

This section applies semi-quantum certified deletion to commitment and encryption primitives, giving constructions with publicly verifiable deletion, including a compiler for public-key encryption and schemes for commitments and fully homomorphic encryption. The FHE application supports polynomial-size classical circuits and compact evaluated ciphertexts, with LWE-based instantiations.

6 Applications

  • The application framework splits a message into classical and quantum shares, then encodes the classical share with a semantically hiding primitive.Its stated scope includes commitments, public-key encryption, and advanced schemes such as attribute-based, identity-based, and fully homomorphic encryption.Source: §6 · p. 34

6.1 Public-Key Encryption

  • Because interactive encryption requires the adversary’s cooperation, the authors prove multi-bit adaptive security directly rather than relying on the folklore bitwise selective-to-adaptive reduction.The reduction’s timing is problematic because encryption cannot begin before receiving the public key.Source: §6.1 · p. 36
  • Assuming post-quantum LWE and PKE, ABE, or IBE, semi-quantum schemes with publicly verifiable certified deletion exist for the corresponding encryption primitives.The PKE compiler also applies to ABE and IBE by encrypting the classical share under the scheme; the message is then revealed only when its attribute or identity conditions are satisfied.Source: §6.1 · pp. 37, 39

6.2 Commitments

  • For commitments, the section adapts the syntax and security requirements of, requiring ordinary hiding separately from hiding after an accepted deletion certificate.The latter ensures hiding persists even if decommitment information is subsequently exposed.Source: §6.2 · pp. 39, 41
  • The semi-quantum commitment construction is introduced using a post-quantum hiding classical commitment scheme and a 2-out-of-2 secret-sharing scheme with publicly verifiable Z-deletion security.The classical commitment must have computational or statistical collapse binding.Source: §6.2 · p. 41
  • The commitment compiler preserves computational or statistical collapse binding from its classical commitment primitive while providing computational hiding and publicly verifiable certified deletion.Theorem 8 applies when the classical commitment and semi-quantum secret-sharing schemes satisfy the stated properties.Source: §6.2 · p. 41
  • Assuming post-quantum LWE hardness, there exists a computationally hiding, statistically collapse-binding semi-quantum commitment scheme with publicly verifiable certified deletion.This follows by combining post-quantum hiding, statistically binding classical commitments with the LWE-based semi-quantum secret-sharing scheme.Source: §6.2 · p. 42

6.3 Fully Homomorphic Encryption

  • The FHE construction supports every polynomial-size classical circuit, with evaluated ciphertext size and decryption time polynomial in security parameter and output length, independent of circuit size or depth.Evaluation can be performed coherently and uncomputed before deleting the restored original ciphertext.Source: §6.3 · pp. 42–43
  • The FHE compiler yields publicly verifiable certified deletion given post-quantum semantically secure classical FHE and a 2-out-of-2 secret-sharing scheme with publicly verifiable Z-deletion security and diagonal PPT reconstruction.The construction also requires the sharing scheme’s security for each semantically hiding distribution Z.Source: §6.3 · p. 44
  • Assuming post-quantum LWE hardness, there exists a semi-quantum fully homomorphic encryption scheme with publicly verifiable certified deletion.The construction uses post-quantum semantically secure FHE and the LWE-based secret-sharing scheme with basis changes.Source: §6.3 · p. 45

7 Proofs of No Intrusion with Classical Upload

The section adds Proofs of No Intrusion (PoNIs) to semi-quantum encryption with classical communication, allowing a classical client to audit ciphertexts. Under post-quantum LWE, it obtains computational search PoNIs and decisional PoNIs in the quantum random oracle model.

Generic PoNI Compiler

  • The resulting PoNI construction follows the generic approach of [KKR26] and lets the auditing client remain entirely classical.The generic compiler guarantees computational search PoNIs under its stated assumptions; decisional PoNIs are available in the quantum random oracle model.Source: §7 · pp. 45, 49

PoNIs with Classical Upload

  • The encryption protocol uses classical communication between a classical sender and quantum receiver, while PoNI uses classical communication between a quantum prover and classical verifier.The sender inputs the public key, message, and secret verification key; the receiver outputs a quantum ciphertext.Source: §7 · p. 45

PoNI Properties

  • PoNIs are non-destructive: after an accepting proof, the server retains a ciphertext decrypting to the same message and can be tested again.The verification key may be reused across ciphertexts, including ciphertexts under different public keys.Source: §7 · pp. 46, 48

Generic PoNI Compiler

  • A generic compiler adds PoNIs to publicly verifiable certified-deletion encryption using post-quantum signatures and a state-preserving argument of knowledge for NP.Its proof uses the deletion certificate as the prover's witness, then uncomputes the coherent deletion operation.Source: §7 · p. 48

PoNIs with Classical Upload

  • Under post-quantum LWE, semi-quantum public-key encryption achieves computational search PoNIs and decisional PoNIs in the quantum random oracle model.The same transformation can be applied to the other primitives constructed in the section.Source: §7 · p. 49

8 Decryption with Deletion

Construction 8 adds a classical-communication decryption protocol that lets the decryptor recover the message while deleting the server’s ability to decrypt it, even after later key exposure. Under post-quantum LWE security, the paper proves a semi-quantum scheme with publicly verifiable certified deletion and decryption-with-deletion.

8 Decryption with Deletion

  • Dec-Del uses only classical communication between a classical decryptor and a quantum server, and outputs both a decision and a message or ⊥.The decryptor’s output is local; it sends no further message to the server.Source: §8 · pp. 49, 51
  • The protocol sends the ciphertext’s classical component to the decryptor, who postpones decryption while the parties execute the deletion protocol.The server prepares a fresh C-instance, sends its function output, and participates as prover in a witness-preserving argument before sending its measurement outcomes.Source: §8 · p. 51
  • Under post-quantum LWE security, a semi-quantum encryption scheme can provide publicly verifiable certified deletion and decryption-with-deletion.Theorem 11 establishes the existence of such a scheme.Source: §8 · p. 52
  • Correctness follows because witness preservation keeps the honest state negligibly close to its pre-argument state, and the verifier accepts with overwhelming probability.State-preparation, witness-preservation, and underlying decryption errors contribute only negligible total failure probability.Source: §8 · p. 52
  • The forward-security proof shows that an adversary’s advantage distinguishing the two message-bit cases is negligible.It reduces the central hybrid transition to publicly verifiable certified-deletion security; the hybrid bounds yield advantage less than any inverse-polynomial ε, up to negligible error.Source: §8 · pp. 52–53

10 AI Disclosure

ChatGPT was used mainly to give feedback on human-generated drafts and to help develop application proofs. The authors state that the technical ideas were wholly their own.

10 AI Disclosure

  • The authors state that the technical ideas were wholly human-authored, and that application proofs were heavily edited or rewritten by humans for accuracy and exposition.Source: §10 · p. 53
  • ChatGPT’s primary use was giving feedback on human-generated drafts.Source: §10 · p. 53
  • Its largest contribution was in the applications section, where it was asked to import definitions and prove specific applications based on the main technical sections.Source: §10 · p. 53

Related papers

Loading 2609.38915v1…