Optimal Rate-Distortion-Leakage Tradeoff for Single-Server Information Retrieval

Yauhen Yakimenka, Hsuan Yin Lin, Eirik Rosnes, Jorg Kliewer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


Private information retrieval protocols guarantee that a user can privately and losslessly retrieve a single file from a database stored across multiple servers. In this work, we propose to simultaneously relax the conditions of perfect retrievability and privacy in order to obtain improved download rates in the single server scenario, i.e., all files are stored uncoded on a single server. In particular, we derive the optimal tradeoff between download rate, distortion, and information leakage when the file size is infinite and the information leakage is measured in terms of the average success probability for the server of correctly guessing the identity of the requested file. Moreover, we present a novel approach based on linear programming to construct schemes for a finite file size and an arbitrary number of files. When the database contains at most four bits, this approach can be leveraged to find provably optimal schemes.

Original languageEnglish (US)
Title of host publication2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781538682098
StatePublished - Jul 12 2021
Event2021 IEEE International Symposium on Information Theory, ISIT 2021 - Virtual, Melbourne, Australia
Duration: Jul 12 2021Jul 20 2021

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Conference2021 IEEE International Symposium on Information Theory, ISIT 2021
CityVirtual, Melbourne

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Optimal Rate-Distortion-Leakage Tradeoff for Single-Server Information Retrieval'. Together they form a unique fingerprint.

Cite this