MURAL - Maynooth University Research Archive Library

    Hiding Symbols and Functions: New Metrics and Constructions for Information-Theoretic Security

    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.

    Download (346kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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

      Repository Staff Only(login required)

      View Item Item control page


      Downloads per month over past year