@inproceedings{5dd53797717c41c0bb743271f70e54e4,
title = "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 2nRL 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.",
author = "Curt Schieler and Paul Cuff",
year = "2014",
doi = "10.1109/ISIT.2014.6874902",
language = "English (US)",
isbn = "9781479951864",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "596--600",
booktitle = "2014 IEEE International Symposium on Information Theory, ISIT 2014",
address = "United States",
note = "2014 IEEE International Symposium on Information Theory, ISIT 2014 ; Conference date: 29-06-2014 Through 04-07-2014",
}