The Henchman Problem: Measuring Secrecy by the Minimum Distortion in a List

Curt Schieler, Paul Cuff

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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 paper, 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 (a helper for an adversary). 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 uniformly drawn from a random codebook. We also characterize the solution to the lossy communication version of the problem in which distortion is allowed at the legitimate receiver. The analysis in both the settings is greatly aided by a recent technique for proving source coding results with the use of a likelihood encoder.

Original languageEnglish (US)
Article number7454714
Pages (from-to)3436-3450
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number6
StatePublished - Jun 2016

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • List decoding
  • Rate-distortion theory
  • information-theoretic secrecy
  • likelihood encoder
  • shared secret key


Dive into the research topics of 'The Henchman Problem: Measuring Secrecy by the Minimum Distortion in a List'. Together they form a unique fingerprint.

Cite this