### 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^{nRL} 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.

Original language | English (US) |
---|---|

Title of host publication | 2014 IEEE International Symposium on Information Theory, ISIT 2014 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 596-600 |

Number of pages | 5 |

ISBN (Print) | 9781479951864 |

DOIs | |

State | Published - Jan 1 2014 |

Event | 2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States Duration: Jun 29 2014 → Jul 4 2014 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

ISSN (Print) | 2157-8095 |

### Other

Other | 2014 IEEE International Symposium on Information Theory, ISIT 2014 |
---|---|

Country | United States |

City | Honolulu, HI |

Period | 6/29/14 → 7/4/14 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics

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

*2014 IEEE International Symposium on Information Theory, ISIT 2014*(pp. 596-600). [6874902] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6874902