Journal
2020 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)
Volume -, Issue -, Pages 1083-1088Publisher
IEEE
DOI: 10.1109/isit44484.2020.9174126
Keywords
-
Funding
- Swiss National Science Foundation [169294]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available