IEEE Transactions on Information Theory, volume 65, issue 9, pages 5565-5573
On Private Information Retrieval Array Codes
Yiwei Zhang
1
,
Xin Wang
2
,
Hengjia Wei
1
,
Gennian Ge
1
Publication type: Journal Article
Publication date: 2019-09-01
scimago Q1
wos Q1
SJR: 1.464
CiteScore: 5.5
Impact factor: 2.9
ISSN: 00189448, 15579654
Computer Science Applications
Library and Information Sciences
Information Systems
Abstract
Given a database, the private information retrieval (PIR) protocol allows a user to make queries to several servers and retrieve a certain item of the database via the feedbacks without revealing the identity of the specific item to any single server. Classic
$k$
-server PIR protocols work on replicated databases, i.e., each of the
$k$
servers stores a whole copy of the database. Recently, new PIR models were proposed with coding techniques arising from the distributed storage system. In these new models, each server only stores a fraction
$1/s$
of the whole database, where
$s>1$
is the given rational number. The PIR array codes are recently proposed by Fazeli, Vardy, and Yaakobi to characterize the new models. The central problem in designing a PIR array code with
$m$
servers and the
$k$
-PIR property (which indicates that these
$m$
servers may emulate a classic
$k$
-server PIR protocol) is to maximize
$k/m$
, known as the virtual server rate. Our main contribution to this problem is twofold. First, for the case
$1 < s\le 2$
, although the PIR array codes with optimal rate have been constructed recently by Blackburn and Etzion, the number of servers in their construction is rather large. We determine the minimum number of servers admitting the existence of a PIR array code with an optimal rate for a certain range of parameters. Second, for the case
$s>2$
, a new upper bound on the rate of a PIR array code is presented. Besides, we also have some discussions on an asymptotically optimal construction by Blackburn and Etzion.
Found
Nothing found, try to update filter.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
19
Total citations:
19
Citations from 2024:
2
(10%)