IEEE Transactions on Information Theory, volume 65, issue 9, pages 5565-5573

On Private Information Retrieval Array Codes

Publication typeJournal Article
Publication date2019-09-01
scimago Q1
wos Q1
SJR1.464
CiteScore5.5
Impact factor2.9
ISSN00189448, 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 
Found 

Top-30

Journals

1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9

Publishers

2
4
6
8
10
12
14
16
2
4
6
8
10
12
14
16
  • We do not take into account publications without a DOI.
  • Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
  • Statistics recalculated weekly.

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
Share
Cite this
GOST | RIS | BibTex | MLA
Found error?