Information Leakage due to Revealing Randomly Selected Bits
| Autor: | Atashpendar, Arash, Roscoe, Bill, Ryan, Peter |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Computer science [C05] [Engineering
computing & technology] Deletion Channel Entropy Information Leakage Quantum Key Distribution Subsequence Supersequence Mathematics [G03] [Physical chemical mathematical & earth Sciences] Mathématiques [G03] [Physique chimie mathématiques & sciences de la terre] Sciences informatiques [C05] [Ingénierie informatique & technologie] Simulation |
| Zdroj: | Security Protocols XXIII: Lecture Notes in Computer Science, Volume 9379, 2015 (pp. 325-341). Springer (2015). |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|