Reference : Information Leakage due to Revealing Randomly Selected Bits

	Document type :	Scientific congresses, symposiums and conference proceedings : Paper published in a book
	Discipline(s) :	Physical, chemical, mathematical & earth Sciences : Mathematics Engineering, computing & technology : Computer science
	Focus Areas :	Computational Sciences; Security, Reliability and Trust
	To cite this reference:	http://hdl.handle.net/10993/21251

Title :	Information Leakage due to Revealing Randomly Selected Bits
Language :	English
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) >]
Publication date :	25-Nov-2015
Main document title :	Security Protocols XXIII: Lecture Notes in Computer Science, Volume 9379, 2015
Publisher :	Springer
Pages :	325-341
Peer reviewed :	Yes
Audience :	International
Event name :	Security Protocols XXIII
Event date :	From 31-03-2015 to 02-04-2015
Event place (city) :	Cambridge
Event country :	UK
Keywords :	[en] 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.
Permalink :	http://hdl.handle.net/10993/21251
DOI :	10.1007/978-3-319-26096-9_33

	File(s) associated to this reference
	Fulltext file(s): File Commentary Version Size Access Open access information_leakage_due_to_revealing_randomly_selected_bits_preprint.pdf Author preprint 543.94 kB View/Open

All documents in ORBi^lu are protected by a user license.

 

University of Luxembourg Library |  Feedback |  Legal notices Site Map