Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2411.05176 · Lecture notes in computer science

How to Delete Without a Trace: Certified Deniability in a Quantum World

Alper Çakan, Vipul Goyal, Justin Raizes

Published Jan 1, 2026• 1 citation
arXivHTMLPDF
DOI
10.1007/978-3-032-35409-9_7

Related papers

Quantum Encryption with Certified Deletion

Anne Broadbent, Rabib Islam

arXiv:1910.03551•Lecture notes in computer science•Jan 1, 2020•70 citations

Cryptography with Certified Deletion

James Bartusek, Dakshita Khurana

arXiv:2207.01754•Lecture notes in computer science•Jan 1, 2023•43 citations

Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication

Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki +1 more

arXiv:2105.05393•Lecture notes in computer science•Jan 1, 2021•48 citations

Impossibility of deleting an unknown quantum state

Arun Kumar Pati, Samuel L. Braunstein

arXiv:quant-ph/9911090•Nature•Mar 9, 2000•383 citations

From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography

Arash Atashpendar

From the output produced by a memoryless deletion channel with a uniformly random input of known length $n$, one obtains a posterior distribution on the channel input. The difference between the Shannon entropy of this distribution and that of the uniform prior measures the amount of information about the channel input which is conveyed by the output of length $m$. We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings $\texttt{000}\ldots$, $\texttt{111}\ldots$ and maximized by the alternating strings $\texttt{0101}\ldots$, $\texttt{1010}\ldots$. We present related combinatorial theorems involving binary (sub/super)-sequences and prove the minimal entropy conjecture for single and double deletions using clustering techniques. We then prove the minimization conjecture in the asymptotic limit using results from hidden word statistics by showing how the analytic-combinatorial methods of Flajolet, Szpankowski and Vallée, relying on generating functions, can be applied to resolve the case of fixed output length and $n\rightarrow\infty$. Next, we revisit the notion of deniability in quantum key exchange (QKE). We introduce and formalize the notion of coercer-deniable QKE. We then establish a connection between covert communication and deniability to propose DC-QKE, a simple and provably secure construction for coercer-deniable QKE. We relate deniability to fundamental concepts in quantum information theory and suggest a generic approach based on entanglement distillation for achieving information-theoretic deniability, followed by an analysis of other closely related results such as the relation between the impossibility of unconditionally secure quantum bit commitment and deniability. Finally, we present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.

arXiv:2003.11663•Mar 25, 2020•2 citations

Constant-Rate Certified Deletion

Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung +1 more

We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of "all-or-nothing"-type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84- and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.

cs.CRCross-listedarXiv:2610.03590•Lecture notes in computer science•Oct 5, 2026•0 citations
From the output produced by a memoryless deletion channel with a uniformly random input of known length nnn, one obtains a posterior distribution on the channel input. The difference between the Shannon entropy of this distribution and that of the uniform prior measures the amount of information about the channel input which is conveyed by the output of length mmm. We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings 000…\texttt{000}\ldots000…, 111…\texttt{111}\ldots111… and maximized by the alternating strings 0101…\texttt{0101}\ldots0101…, 1010…\texttt{1010}\ldots1010…. We present related combinatorial theorems involving binary (sub/super)-sequences and prove the minimal entropy conjecture for single and double deletions using clustering techniques. We then prove the minimization conjecture in the asymptotic limit using results from hidden word statistics by showing how the analytic-combinatorial methods of Flajolet, Szpankowski and Vallée, relying on generating functions, can be applied to resolve the case of fixed output length and n→∞n\rightarrow\inftyn→∞. Next, we revisit the notion of deniability in quantum key exchange (QKE). We introduce and formalize the notion of coercer-deniable QKE. We then establish a connection between covert communication and deniability to propose DC-QKE, a simple and provably secure construction for coercer-deniable QKE. We relate deniability to fundamental concepts in quantum information theory and suggest a generic approach based on entanglement distillation for achieving information-theoretic deniability, followed by an analysis of other closely related results such as the relation between the impossibility of unconditionally secure quantum bit commitment and deniability. Finally, we present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.
We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of "all-or-nothing"-type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84- and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.