@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",

month = jan,

day = "1",

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",

}