Technical Program

Paper Detail

Paper IDP.10.3
Paper Title Single-Server Multi-message Private Information Retrieval with Side Information: the General Cases
Authors Su Li, Michael Gastpar, EPFL, Switzerland
Session P.10: Private Information Retrieval III
Presentation Lecture
Track Cryptography, Security and Privacy
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract The single-server multi-message private information retrieval with side information problem is studied for general cases. In this problem, K independent messages are stored at a single server. One user initially has M messages as side information and wants to download N demand messages while not leaking any information about the indices of demand messages to the server. In our previous work, we characterized the minimum number of required download bits and presented an achievability scheme for this problem with the constraint of linear codes. In this paper, we extend the results to general (non-linear) codes and present the closed-form expression for the minimum number of required download bits. Moreover, we show that linear coding schemes are sufficient to achieve the optimal (minimum) download bits. Additionally, we show that the trivial MDS coding scheme with K-M transmissions is optimal if N>M or N^2+N >= K-M. This means if one wishes to privately download more than the square-root of the number of messages in the database, then one must effectively download the full database (minus the side information), irrespective of the amount of side information one has available.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!