Rate-Distortion Theory for Secrecy Systems

Abstract

The purpose of any communication system is to ensure reliable transmission of data from a sender to a receiver. An important secondary goal is to suitably encrypt the data so that an eavesdropper cannot glean any useful information from the communication. From an information-theoretic point of view, an ideal secure communication system ensures that an eavesdropper's observations are statistically independent of the information source. Unfortunately, a prohibitively large amount of shared secret key is necessary to guarantee such perfect secrecy. This prompts a natural question: if perfect secrecy is relaxed in order to ease the key requirement, then what is a good measure of "imperfect" secrecy?

One of the successes of information theory has been to establish fundamental limits of lossy data compression through the use of rate-distortion theory. In rate-distortion theory, the receiver is allowed some loss in reproducing the source in order to reduce the compression ratio; the goal is to find the optimal tradeoff between the rate of compression and the receiver's distortion.

This thesis explores the consequences of applying the rate-distortion paradigm to the problem of measuring imperfect secrecy in a communication system. In particular, the key question is: what is the optimal tradeoff between the rate of secret key and the distortion that an eavesdropper suffers in trying to reconstruct the source? It turns out that distortion-based measures of security are most appropriate in settings where the eavesdropper is assumed to have additional side information about the source. This thesis examines two such settings. In the first setting, the eavesdropper is able to view the past behavior of various parts of the communication system and update his actions accordingly. In the second setting, the eavesdropper receives rate-limited communication from an omniscient assistant. This thesis characterizes the optimal information-theoretic tradeoff between the key rate and the eavesdropper's distortion for general versions of both settings.