A New Design of Private Information Retrieval for Storage Constrained Databases
share
Private information retrieval (PIR) allows a user to download one of K messages from N databases without revealing to any database which of the K messages is being downloaded. In general, the databases can be storage constrained where each database can only store up to μ K L bits where 1/N≤μ≤ 1 and L is the size of each message in bits. Let t= μ N, a recent work showed that the capacity of Storage Constrained PIR (SC-PIR) is ( 1+ 1/t + 1/t^2 + ... + 1/t^K-1)^-1, which is achieved by a storage placement scheme inspired by the content placement scheme in the literature of coded caching and the original PIR scheme. Not surprisingly, this achievable scheme requires that each message is L = N tt^K bits in length, which can be impractical. In this paper, without trying to make the connection between SC-PIR and coded caching problems, based on a general connection between the Full Storage PIR (FS-PIR) problem (μ = 1) and SC-PIR problem, we propose a new SC-PIR design idea using novel storage placement schemes. The proposed schemes significantly reduce the message size requirement while still meeting the capacity of SC-PIR. In particular, the proposed SC-PIR schemes require the size of each file to be only L = Nt^K-1 compared to the state-of-the-art L = N tt^K. Hence, we conclude that PIR may not meet coded caching when the size of L is constrained.
READ FULL TEXT