No full text
Doctoral thesis (Dissertations and theses)
From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography
Atashpendar, Arash
2019
 

Files


Full Text
No document available.

Send to



Details



Keywords :
Information Theory; Deletion Channels; Entropy Extremization; Posterior Distribution; Subsequence Embeddings; Combinatorial Mathematics; Quantum Cryptography; Quantum Key Exchange; Deniability; Deniable Quantum Key Exchange; QKE; QKD; Covert Quantum Communication; Quantum Entanglement Distillation; Coercion-Resistance; Quantum-Secure E-Voting; View Indistinguishability; Coercer-Deniability; Covert Quantum Key Exchange; Fully Homomorphic Encryption; Post-Quantum Cryptography; Threshold Cryptography; Zero-Knowledge Proof; Homomorphic Hashing; Closed-form Solution; Information Entropy; Binary Sequences; Analytic Combinatorics; Hidden Word Statistics
Abstract :
[en] Research questions, originally rooted in quantum key exchange (QKE), have branched off into independent lines of inquiry ranging from information theory to fundamental physics. In a similar vein, the first part of this thesis is dedicated to information theory problems in deletion channels that arose in the context of QKE. 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 000..., 111... and maximized by the alternating strings 0101..., 1010.... Among other things, we derive analytic expressions for minimal entropy and propose alternative approaches for tackling the entropy extremization problem. We address a series of closely related combinatorial problems involving binary (sub/super)-sequences and prove the original minimal entropy conjecture for the special cases of single and double deletions using clustering techniques and a run-length encoding of strings. The entropy analysis culminates in a fundamental characterization of the extremal entropic cases in terms of the distribution of embeddings. We confirm 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 → ∞. In the second part, we revisit the notion of deniability in QKE, a topic that remains largely unexplored. In a work by Donald Beaver it is argued that QKE protocols are not necessarily deniable due to an eavesdropping attack that limits key equivocation. We provide more insight into the nature of this attack and discuss how it extends to other prepare-and-measure QKE schemes such as QKE obtained from uncloneable encryption. We 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. We also elaborate on the differences between our model and the standard simulation-based definition of deniable key exchange in the classical setting. We establish a connection between the concept of covert communication and deniability by applying results from a work by Arrazola and Scarani on obtaining covert quantum communication and covert QKE to propose a simple construction for coercer-deniable QKE. We prove the deniability of this scheme via a reduction to the security of covert 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 (FHE) and recent advances in various FHE primitives such as hashing, zero-knowledge proofs of correct decryption, verifiable shuffles and threshold FHE.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Applied Security and Information Assurance Group (APSIA)
Disciplines :
Computer science
Author, co-author :
Atashpendar, Arash ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Language :
English
Title :
From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography
Defense date :
23 January 2019
Number of pages :
151
Institution :
Unilu - University of Luxembourg, Luxembourg
Degree :
Docteur en Informatique
Promotor :
President :
Jury member :
Cremers, Cas
Ding, Jintai
Roenne, Peter 
Focus Area :
Security, Reliability and Trust
Available on ORBilu :
since 15 February 2019

Statistics


Number of views
558 (136 by Unilu)
Number of downloads
213 (56 by Unilu)

Bibliography


Similar publications



Contact ORBilu