2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | P.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
