Reference : From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Crypto...
Dissertations and theses : Doctoral thesis
Engineering, computing & technology : Computer science
Security, Reliability and Trust
From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography
Atashpendar, Arash mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
University of Luxembourg, ​​Luxembourg
Docteur en Informatique
Ryan, Peter
Mauw, Sjouke
Cremers, Cas
Ding, Jintai
Roenne, Peter
[en] 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
[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.
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Applied Security and Information Assurance Group (APSIA)

There is no file associated with this reference.

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.