### 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 paper, we suppose that an eavesdropper produces a list of 2^{nR}_{L} 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 language | English (US) |
---|---|

Article number | 7454714 |

Pages (from-to) | 3436-3450 |

Number of pages | 15 |

Journal | IEEE Transactions on Information Theory |

Volume | 62 |

Issue number | 6 |

DOIs | |

State | Published - Jun 2016 |

### All Science Journal Classification (ASJC) codes

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

### Keywords

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

## Fingerprint 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

*IEEE Transactions on Information Theory*,

*62*(6), 3436-3450. [7454714]. https://doi.org/10.1109/TIT.2016.2548470