Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost Conference Paper

abstract

• 2019 IEEE. We propose a new capacity-achieving code for the private information retrieval (PIR) problem, and show that it has the minimum message size (being one less than the number of servers) and the minimum upload cost (being roughly linear in the number of messages) among a general class of capacity-achieving codes, and in particular, among all capacity-achieving linear codes. Different from existing code constructions, the proposed code is asymmetric, and this asymmetry appears to be the key factor leading to the optimal message size and the optimal upload cost. The converse results on the message size and the upload cost are obtained by a strategic analysis of the information theoretic proof of the PIR capacity, from which a set of critical properties of any capacity-achieving code in the code class of interest is extracted.

name of conference

• ICC 2019 - 2019 IEEE International Conference on Communications (ICC)

authors

• Tian, Chao

published proceedings

• ICC 2019 - 2019 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS (ICC)

author list (cited authors)

• Tian, C., Sun, H., & Chen, J.

citation count

• 5

complete list of authors

• Tian, Chao||Sun, Hua||Chen, Jun

publication date

• January 2019

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• 2013 National Conference on Communications, NCC 2013  Journal

Digital Object Identifier (DOI)

• 10.1109/icc.2019.8761802

International Standard Book Number (ISBN) 13

• 9781538680889

start page

• 1

end page

• 6

volume

• 00

URL

• http://dx.doi.org/10.1109/icc.2019.8761802