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

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

Research output: Contribution to journalArticlepeer-review

5 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 when all files are stored uncoded on a single server. Information leakage is measured in terms of the average success probability for the server of correctly guessing the identity of the desired file. The main findings are: i) The derivation of the optimal tradeoff between download rate, distortion, and information leakage when the file size is infinite. Closed-form expressions of the optimal tradeoff for the special cases of 'no-leakage' and 'no-privacy' are also given. ii) A novel approach based on linear programming (LP) to construct schemes for a finite file size and an arbitrary number of files. The proposed LP approach can be leveraged to find provably optimal schemes with corresponding closed-form expressions for the rate-distortion-leakage tradeoff when the database contains at most four bits. Finally, for a database that contains 320 bits, we compare two construction methods based on the LP approach with a nonconstructive scheme downloading subsets of files using a finite-length lossy compressor based on random coding.

Original languageEnglish (US)
Pages (from-to)832-846
Number of pages15
JournalIEEE Journal on Selected Areas in Communications
Issue number3
StatePublished - Mar 1 2022

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Capacity
  • information leakage
  • information-theoretic privacy
  • lossy compression
  • private information retrieval
  • rate-distortion theory
  • single server


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

Cite this