Calmon, Flavio P. and Medard, Muriel and Varia, Mayank and Duffy, Ken R. and Christiansen, Mark M. and Zeger, Linda M. (2015) Hiding Symbols and Functions: New Metrics and Constructions for Information-Theoretic Security. Working Paper. arXiv.

Preview

Download (346kB) | Preview

Abstract

We present information-theoretic definitions and results for analyzing symmetric-key encryption schemes beyond the perfect secrecy regime, i.e. when perfect secrecy is not attained. We adopt two lines of analysis, one based on lossless source coding, and another akin to ratedistortion theory. We start by presenting a new information-theoretic metric for security, called ǫ-symbol secrecy, and derive associated fundamental bounds. This metric provides a parameterization of secrecy that spans other information-theoretic metrics for security, such as weak secrecy and perfect secrecy. We then introduce list-source codes (LSCs), which are a general framework for mapping a key length (entropy) to a list size that an eavesdropper has to resolve in order to recover a secret message. We provide explicit constructions of LSCs, and show that LSCs that achieve high symbol secrecy also achieve a favorable tradeoff between key length and uncertainty list size. We also demonstrate that, when the source is uniformly distributed, the highest level of symbol secrecy for a fixed key length can be achieved through a construction based on minimum-distance separable (MDS) codes. Using an analysis related to rate-distortion theory, we then show how symbol secrecy can be used to determine the probability that an eavesdropper correctly reconstructs functions of the original plaintext. More specifically, we present lower bounds for the minimum-mean-squared-error of estimating a target function of the plaintext given that a certain set of functions of the plaintext is known to be hard (or easy) to infer, either by design of the security system or by restrictions imposed on the adversary. We illustrate how these bounds can be applied to characterize security properties of symmetric-key encryption schemes, and, in particular, extend security claims based on symbol secrecy to a functional setting. Finally, we discuss the application of our methods in key distribution, storage and privacy.

Item Type:	Monograph (Working Paper)
Additional Information:	Preprint submitted to IEEE Transactions on Information Theory.
Keywords:	Hiding Symbols; Functions; Metrics; Constructions; Information-Theoretic Security; encryption;
Academic Unit:	Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	6761
Identification Number:	arXiv:1503.08513
Depositing User:	Dr Ken Duffy
Date Deposited:	11 Jan 2016 16:43
Publisher:	arXiv
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads