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

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 $\text{000}\dots$, $\text{111}\dots$ and maximized by the alternating strings $\text{0101}\dots$, $\text{1010}\dots$. 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\to \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 commentPhD thesis, 152 pages, 5 figures

References in corpus (40)

• Mixed State Entanglement and Quantum Error Correction
• The Security of Practical Quantum Key Distribution
• Concentrating Partial Entanglement by Local Operations
• Simple Proof of Security of the BB84 Quantum Key Distribution Protocol
• Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
• Good Quantum Error-Correcting Codes Exist
• Unconditional Security Of Quantum Key Distribution Over Arbitrarily Long Distances
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum algorithms: an overview
• Conditions for a class of entanglement transformations
• No Signalling and Quantum Key Distribution
• Unconditionally secure quantum bit commitment is impossible
• Tight Finite-Key Analysis for Quantum Cryptography
• Monogamy of entanglement and other correlations
• An information-theoretic security proof for QKD protocols
• Insecurity of Quantum Secure Computations
• Negative entropy and information in quantum mechanics
• Free randomness can be amplified
• Quantum cryptography with finite resources: unconditional security bound for discrete-variable protocols with one-way post-processing
• Counterfactual Quantum Cryptography
• Estimates for practical quantum cryptography
• Quantum protocols for anonymous voting and surveying
• Are general quantum correlations monogamous?
• Towards quantum-based privacy and voting
• Covert Optical Communication
• The Case for Quantum Key Distribution
• A Generic Security Proof for Quantum Key Distribution
• Distilling entanglement from arbitrary resources
• Toward protocols for quantum-ensured privacy and secure voting
• Probabilistic Model--Checking of Quantum Protocols
• Covert Quantum Communication
• Anonymous quantum communication
• Bounds on the Capacity of Random Insertion and Deletion-Additive Noise Channels
• An Automated Analysis of the Security of Quantum Key Distribution
• Analysis of a Quantum Error Correcting Code using Quantum Process Calculus
• Efficiently implementable codes for quantum key expansion
• From Clustering Supersequences to Entropy Minimizing Subsequences for Single and Double Deletions
• Formal Analysis of Quantum Systems using Process Calculus
• A Proof of Entropy Minimization for Outputs in Deletion Channels via Hidden Word Statistics