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:2003.11663

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

Arash Atashpendar

Published Mar 25, 2020• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2003.11663

Related papers

Revisiting Deniability in Quantum Key Exchange via Covert Communication and Entanglement Distillation

Arash Atashpendar, Guru-Vamsi Policharla, Peter Browne Rønne +1 more

We revisit the notion of deniability in quantum key exchange (QKE), a topic that remains largely unexplored. In the only work on this subject by Donald Beaver, it is argued that QKE is not necessarily deniable due to an eavesdropping attack that limits key equivocation. We provide more insight into the nature of this attack and how it extends to other constructions such as QKE obtained from uncloneable encryption. We then adopt the framework for quantum authenticated key exchange, developed by Mosca et al., and extend it to introduce the notion of coercer-deniable QKE, formalized in terms of the indistinguishability of real and fake coercer views. Next, we apply results from a recent work by Arrazola and Scarani on covert quantum communication to establish a connection between covert QKE and deniability. We propose DC-QKE, a simple deniable covert QKE protocol, and prove its deniability via a reduction to the security of covert QKE. Finally, we consider how entanglement distillation can be used to enable information-theoretically deniable protocols for QKE and tasks beyond key exchange.

arXiv:1812.02245•Dec 5, 2018•2 citations

Deniability in Quantum Cryptography

Arash Atashpendar, Peter B. Roenne, Dimiter Ostrev +1 more

This poster describes ongoing work on deniability in quantum cryptography, an area of research that remains almost entirely unexplored in the quantum information processing literature. Deniability is a well-known and fundamental concept in classical cryptography and it can be defined as the ability for the sender of a message to deny the contents of a message or the very act of having participated in an exchange, e.g. having sent the said message. We discuss deniability in the context of quantum key exchange and address a particular problem, first discovered by Donald Beaver, where he claims that all QKD protocols are undeniable. The claim is that while we do get a one-time pad (OTP) using QKD, it does not provide the property of key equivocation as it is expected in the Shannon sense for a OTP. Intuitively, this difficulty lies in the quantum channel alone and it has to do with the fact that in QKD, while we generate entropy by expanding an initially short pre-shared key into an arbitrary longer secret key, we do so by exchanging information over a quantum as well as a classical channel, which could potentially leave a binding transcript of Alice's decisions to the final secret key. This is in contrast with the implicit assumption that Eve knows nothing about how two given parties have established their shared OTP in the first place. We discuss the importance of deniability in cryptography and its wide range of applications, along with cryptographic primitives other than key exchange where deniability might be a desired property. Finally, we present a series of fundamental open questions in this area of research and discuss quantum cryptographic primitives that lend themselves to devising deniable protocols.

•Jun 14, 2017•0 citations

Quantum Encryption with Certified Deletion

Islam, Rabib

In the context of classical information, every message is composed of 0s and 1s; these messages can generally be copied at will. However, when quantum phenomena are used to model information, this guarantee no longer exists. This difference gives rise to a range of cryptographic possibilities when one considers encoding certain messages as quantum information. In our case, we analyze a potential benefit of encoding part of an encryption scheme’s ciphertext as quantum information. We call this type of ciphertext a quantum ciphertext. In particular, quantum ciphertexts are useful when one wants to be able to prove the deletion of the plaintext underlying a ciphertext. Since classical ciphertexts can be copied, clearly such feat is impossible using classical information alone. However, we show that quantum encodings allow such certified deletion. More precisely, we show that it is possible to encrypt classical data into a quantum ciphertext such that the recipient of the ciphertext can produce a classical string which proves to the originator that the recipient has relinquished any chance of recovering the plaintext, should the decryption key be revealed. Our scheme is feasible with current quantum technology: the honest parties only require quantum devices for single-qubit preparation and measurements, and the scheme is robust against noise in these devices. Furthermore, we provide a proof of security which requires only a finite amount of communication, and which therefore avoids the common technique of relying on the analysis of an asymptotic case.

•Jan 20, 2020•39 citations

Entropy in Quantum Information Theory -- Communication and Cryptography

Christian Majenz

In this Thesis, several results in quantum information theory are collected, most of which use entropy as the main mathematical tool. *While a direct generalization of the Shannon entropy to density matrices, the von Neumann entropy behaves differently. A long-standing open question is, whether there are quantum analogues of unconstrained non-Shannon type inequalities. Here, a new constrained non-von-Neumann type inequality is proven, a step towards a conjectured unconstrained inequality by Linden and Winter. *IID quantum state merging can be optimally achieved using the decoupling technique. The one-shot results by Berta et al. and Anshu at al., however, had to bring in additional mathematical machinery. We introduce a natural generalized decoupling paradigm, catalytic decoupling, that can reproduce the aforementioned results when used analogously to the application of standard decoupling in the asymptotic case. *Port based teleportation, a variant of standard quantum teleportation protocol, cannot be implemented perfectly. We prove several lower bounds on the necessary number of output ports N to achieve port based teleportation for given error and input dimension, showing that N diverges uniformly in the dimension of the teleported quantum system, for vanishing error. As a byproduct, a new lower bound for the size of the program register for an approximate universal programmable quantum processor is derived. *In the last part, we give a new definition for information-theoretic quantum non-malleability, strengthening the previous definition by Ambainis et al. We show that quantum non-malleability implies secrecy, analogous to quantum authentication. Furthermore, non-malleable encryption schemes can be used as a primitive to build authenticating encryption schemes. We also show that the strong notion of authentication recently proposed by Garg et al. can be fulfilled using 2-designs.

arXiv:1810.10436•Oct 24, 2018•4 citations

Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness

Dakshita Khurana, Kabir Tomer

Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for $\mathsf{P^{\#P}}$ -- such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that $\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}$. We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. (3) The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.

arXiv:2409.15248•Sep 23, 2024•1 citation

A Phase-Encoded Quantum One-Time Pad for Sender-Deniable Encryption

Sougata Jana, Jaydeep Howlader

Coercion is the attack where a sender is forced to reveal the plaintext and secret key corresponding to an intercepted communication. Deniable encryption mitigates this threat by allowing the sender to generate a plausible alternative message-key pair that is consistent with the ciphertext.This work presents a phase-encoded quantum one-time pad that realizes sender-deniable encryption using single-qubit superpositions. The protocol uses phase-encoded quantum superpositions, where a classical message, XORed with a secret key, is encoded into the relative phases of single-qubit states. An honest receiver can deterministically recover the message by applying a key-dependent phase correction and measuring in the Hadamard basis; meanwhile, an eavesdropper or coercer without the key observes only a maximally mixed state. Because multiple message–key pairs yield identical quantum ciphertexts, the scheme provides information-theoretic plausible deniability without relying on computational hardness assumptions. The construction requires only Hadamard and phase-flip operations, thereby avoiding entanglement or multi-qubit gates, and can be implemented as a lightweight deniability layer on top of existing Quantum Key Distribution systems. This minimalist approach extends quantum communication from confidentiality toward coercion-resistant information transfer secured by physical principles rather than computational complexity.

•Jan 6, 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 revisit the notion of deniability in quantum key exchange (QKE), a topic that remains largely unexplored. In the only work on this subject by Donald Beaver, it is argued that QKE is not necessarily deniable due to an eavesdropping attack that limits key equivocation. We provide more insight into the nature of this attack and how it extends to other constructions such as QKE obtained from uncloneable encryption. We then adopt the framework for quantum authenticated key exchange, developed by Mosca et al., and extend it to introduce the notion of coercer-deniable QKE, formalized in terms of the indistinguishability of real and fake coercer views. Next, we apply results from a recent work by Arrazola and Scarani on covert quantum communication to establish a connection between covert QKE and deniability. We propose DC-QKE, a simple deniable covert QKE protocol, and prove its deniability via a reduction to the security of covert QKE. Finally, we consider how entanglement distillation can be used to enable information-theoretically deniable protocols for QKE and tasks beyond key exchange.
This poster describes ongoing work on deniability in quantum cryptography, an area of research that remains almost entirely unexplored in the quantum information processing literature. Deniability is a well-known and fundamental concept in classical cryptography and it can be defined as the ability for the sender of a message to deny the contents of a message or the very act of having participated in an exchange, e.g. having sent the said message. We discuss deniability in the context of quantum key exchange and address a particular problem, first discovered by Donald Beaver, where he claims that all QKD protocols are undeniable. The claim is that while we do get a one-time pad (OTP) using QKD, it does not provide the property of key equivocation as it is expected in the Shannon sense for a OTP. Intuitively, this difficulty lies in the quantum channel alone and it has to do with the fact that in QKD, while we generate entropy by expanding an initially short pre-shared key into an arbitrary longer secret key, we do so by exchanging information over a quantum as well as a classical channel, which could potentially leave a binding transcript of Alice's decisions to the final secret key. This is in contrast with the implicit assumption that Eve knows nothing about how two given parties have established their shared OTP in the first place. We discuss the importance of deniability in cryptography and its wide range of applications, along with cryptographic primitives other than key exchange where deniability might be a desired property. Finally, we present a series of fundamental open questions in this area of research and discuss quantum cryptographic primitives that lend themselves to devising deniable protocols.
In the context of classical information, every message is composed of 0s and 1s; these messages can generally be copied at will. However, when quantum phenomena are used to model information, this guarantee no longer exists. This difference gives rise to a range of cryptographic possibilities when one considers encoding certain messages as quantum information. In our case, we analyze a potential benefit of encoding part of an encryption scheme’s ciphertext as quantum information. We call this type of ciphertext a quantum ciphertext. In particular, quantum ciphertexts are useful when one wants to be able to prove the deletion of the plaintext underlying a ciphertext. Since classical ciphertexts can be copied, clearly such feat is impossible using classical information alone. However, we show that quantum encodings allow such certified deletion. More precisely, we show that it is possible to encrypt classical data into a quantum ciphertext such that the recipient of the ciphertext can produce a classical string which proves to the originator that the recipient has relinquished any chance of recovering the plaintext, should the decryption key be revealed. Our scheme is feasible with current quantum technology: the honest parties only require quantum devices for single-qubit preparation and measurements, and the scheme is robust against noise in these devices. Furthermore, we provide a proof of security which requires only a finite amount of communication, and which therefore avoids the common technique of relying on the analysis of an asymptotic case.
In this Thesis, several results in quantum information theory are collected, most of which use entropy as the main mathematical tool. *While a direct generalization of the Shannon entropy to density matrices, the von Neumann entropy behaves differently. A long-standing open question is, whether there are quantum analogues of unconstrained non-Shannon type inequalities. Here, a new constrained non-von-Neumann type inequality is proven, a step towards a conjectured unconstrained inequality by Linden and Winter. *IID quantum state merging can be optimally achieved using the decoupling technique. The one-shot results by Berta et al. and Anshu at al., however, had to bring in additional mathematical machinery. We introduce a natural generalized decoupling paradigm, catalytic decoupling, that can reproduce the aforementioned results when used analogously to the application of standard decoupling in the asymptotic case. *Port based teleportation, a variant of standard quantum teleportation protocol, cannot be implemented perfectly. We prove several lower bounds on the necessary number of output ports N to achieve port based teleportation for given error and input dimension, showing that N diverges uniformly in the dimension of the teleported quantum system, for vanishing error. As a byproduct, a new lower bound for the size of the program register for an approximate universal programmable quantum processor is derived. *In the last part, we give a new definition for information-theoretic quantum non-malleability, strengthening the previous definition by Ambainis et al. We show that quantum non-malleability implies secrecy, analogous to quantum authentication. Furthermore, non-malleable encryption schemes can be used as a primitive to build authenticating encryption schemes. We also show that the strong notion of authentication recently proposed by Garg et al. can be fulfilled using 2-designs.
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P\mathsf{\#P}#P-Hardness
Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for P#P\mathsf{P^{\#P}}P#P -- such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that P#P⊈(io)BQP/qpoly\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}P#P⊆(io)BQP/qpoly. We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. (3) The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.
Coercion is the attack where a sender is forced to reveal the plaintext and secret key corresponding to an intercepted communication. Deniable encryption mitigates this threat by allowing the sender to generate a plausible alternative message-key pair that is consistent with the ciphertext.This work presents a phase-encoded quantum one-time pad that realizes sender-deniable encryption using single-qubit superpositions. The protocol uses phase-encoded quantum superpositions, where a classical message, XORed with a secret key, is encoded into the relative phases of single-qubit states. An honest receiver can deterministically recover the message by applying a key-dependent phase correction and measuring in the Hadamard basis; meanwhile, an eavesdropper or coercer without the key observes only a maximally mixed state. Because multiple message–key pairs yield identical quantum ciphertexts, the scheme provides information-theoretic plausible deniability without relying on computational hardness assumptions. The construction requires only Hadamard and phase-flip operations, thereby avoiding entanglement or multi-qubit gates, and can be implemented as a lightweight deniability layer on top of existing Quantum Key Distribution systems. This minimalist approach extends quantum communication from confidentiality toward coercion-resistant information transfer secured by physical principles rather than computational complexity.