Search

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.

Existing mobile devices have the capability to use multiple network technologies simultaneously to help increase performance; but they rarely, if at all, effectively use these technologies in parallel. We first present empirical data to help understand the mobile environment when three heterogeneous networks are available to the mobile device (i.e., a WiFi network, WiMax network, and an Iridium satellite network). We then propose a reliable, multi-path protocol called Multi-Path TCP with Network Coding (MPTCP/NC) that utilizes each of these networks in parallel. An analytical model is developed and a mean-field approximation is derived that gives an estimate of the protocol's achievable throughput. Finally, a comparison between MPTCP and MPTCP/NC is presented using both the empirical data and mean-field approximation. Our results show that network coding can provide users in mobile environments a higher quality of service by enabling the use of multiple network technologies and the capability to overcome packet losses due to lossy, wireless network connections., United States. Dept. of Defense. Assistant Secretary of Defense for Research & Engineering (Air Force Contract FA8721-05-C-0002)