Paper Info
Title
An Optimal Iterative Placement Algorithm for PIR from Heterogeneous Storage-Constrained Databases.
Abstract
We propose a capacity-achieving scheme for private information retrieval (PIR) from databases (DBs) with hetero-geneous storage constraints. In the PIR setting, a user queries a set of DBs to privately download a message, where privacy implies that no one DB can infer which message the user desires. Our PIR scheme uses an uncoded storage placement and we derive sufficient conditions to meet capacity in this design architecture. We translate the storage placement design to a "filling problem" where messages are partitioned into sub-messages and stored at subsets of DBs. We prove a set of necessary and sufficient conditions for the existence of the filling problem solution and design an iterative algorithm to find a filling problem solution. Our proposed algorithm requires at most a number of iterations equal to the number of DBs. Furthermore, we significantly reduce the number of sub-messages compared to the state-of-the-art PIR scheme, as our proposed PIR scheme requires that each message is split into a polynomial number of sub-messages with respect to the number of DBs.
Year
DOI
Venue
2019
10.1109/GLOBECOM38437.2019.9013430
IEEE Global Communications Conference
Field
DocType
Volume
Integer,Discrete mathematics,Algorithm,Mathematics,Database
Journal
abs/1904.02131
ISSN
Citations 
PageRank 
2334-0983
2
0.42
References 
Authors
0
3
Name
Order
Citations
PageRank
Nicholas Woolsey1156.06
Rong-Rong Chen27010.31
Mingyue Ji364151.43