Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Information Leakage due to Revealing Randomly Selected Bits
Atashpendar, Arash; Roscoe, Bill; Ryan, Peter
2015In Security Protocols XXIII: Lecture Notes in Computer Science, Volume 9379, 2015
Peer reviewed


Full Text
Author preprint (556.99 kB)

All documents in ORBilu are protected by a user license.

Send to


Keywords :
Information Leakage; Quantum Key Distribution; Entropy; Subsequence; Supersequence; Deletion Channel; Simulation
Abstract :
[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.
Disciplines :
Computer science
Author, co-author :
Atashpendar, Arash ;  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)
External co-authors :
Language :
Title :
Information Leakage due to Revealing Randomly Selected Bits
Publication date :
25 November 2015
Event name :
Security Protocols XXIII
Event place :
Cambridge, United Kingdom
Event date :
From 31-03-2015 to 02-04-2015
Audience :
Main work title :
Security Protocols XXIII: Lecture Notes in Computer Science, Volume 9379, 2015
Publisher :
Pages :
Peer reviewed :
Peer reviewed
Focus Area :
Computational Sciences
Security, Reliability and Trust
Available on ORBilu :
since 08 June 2015


Number of views
390 (59 by Unilu)
Number of downloads
148 (7 by Unilu)

Scopus citations®
Scopus citations®
without self-citations


Similar publications

Contact ORBilu