Reference : Information Leakage due to Revealing Randomly Selected Bits
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
Computational Sciences; Security, Reliability and Trust
Information Leakage due to Revealing Randomly Selected Bits
Atashpendar, Arash mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Roscoe, Bill [University of Oxford > Department of Computer Science]
Ryan, Peter [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Security Protocols XXIII: Lecture Notes in Computer Science, Volume 9379, 2015
Security Protocols XXIII
From 31-03-2015 to 02-04-2015
[en] Information Leakage ; Quantum Key Distribution ; Entropy ; Subsequence ; Supersequence ; Deletion Channel ; Simulation
[en] This note describes an information theory problem that arose from some analysis of quantum key distribution protocols. The problem seems very natural and is very easy to state but has not to our knowledge been addressed before in the information theory literature: suppose that we have a random bit string y of length n and we reveal k bits at random positions, preserving the order but without revealing the positions, how much information about y is revealed? We show that while the cardinality of the set of compatible y strings depends only on n and k, the amount of leakage does depend on the exact revealed x string. We observe that the maximal leakage, measured as decrease in the Shannon entropy of the space of possible bit strings corresponds to the x string being all zeros or all ones and that the minimum leakage corresponds to the alternating x strings. We derive a formula for the maximum leakage (minimal entropy) in terms of n and k. We discuss the relevance of other measures of information, in particular min-entropy, in a cryptographic context. Finally, we describe a simulation tool to explore these results.

File(s) associated to this reference

Fulltext file(s):

Open access
information_leakage_due_to_revealing_randomly_selected_bits_preprint.pdfAuthor preprint543.94 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.