The Henchman problem: Measuring secrecy by the minimum distortion in a list

Abstract

We introduce a new measure of information-theoretic secrecy based on rate-distortion theory and study it in the context of the Shannon cipher system. Whereas rate-distortion theory is traditionally concerned with a single reconstruction sequence, in this work we suppose that an eavesdropper produces a list of 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">nRL</sup> reconstruction sequences and measure secrecy by the minimum distortion over the entire list.We show that this setting is equivalent to one in which an eavesdropper must reconstruct a single sequence, but also receives side information about the source sequence and public message from a rate-limited henchman. We characterize the optimal tradeoff of secret key rate, list rate, and eavesdropper distortion. The solution hinges on a problem of independent interest: lossy compression of a codeword drawn uniformly from a random codebook.

Locations

• arXiv (Cornell University) - View - PDF