Paper Info
Title
A general private information retrieval scheme for MDS coded databases with colluding servers.
Abstract
The problem of private information retrieval (PIR) gets renewed attentions in recent years due to its information-theoretic reformulation and applications in distributed storage systems. Let M files be stored in a distributed storage system consisting of N servers, where each file is stored via an (N, K)-MDS code. A PIR scheme will allow a user to retrieve a specific file from the distributed storage system without revealing the identity of the file to any T colluding servers. PIR rate is defined as the number of symbols privately retrieved per one downloaded symbol and the supremum of all achievable rates is called the PIR capacity. The capacity has been solved for some degenerate cases, i.e. $$K=1$$ or $$T=1$$ . For the general case $$K\ge 2$$ and $$T\ge 2$$ , the exact PIR capacity remains unknown. In this paper we propose a general private information retrieval scheme for MDS coded databases with colluding servers achieving PIR rate $$(1+R+R^2+\cdots +R^{M-1})$$ , where $$R=1-\frac{{{N-T}\atopwithdelims ()K}}{{N\atopwithdelims ()K}}$$ . Our scheme captures the essence of the optimal schemes for degenerate cases. We also compare our scheme with some other known PIR schemes for non-degenerate cases. The advantages of our scheme include its independence of the property of the storage code and a better performance when the number of files M is small.
Year
DOI
Venue
2017
10.1007/s10623-019-00640-x
Designs, Codes and Cryptography
Keywords
Field
DocType
Private information retrieval, Distributed storage system, PIR capacity, 94A15
Discrete mathematics,Server,Distributed data store,Private information retrieval,Database,Mathematics
Journal
Volume
Issue
ISSN
87
11
0925-1022
Citations 
PageRank 
References 
12
0.64
12
Authors
2
Name
Order
Citations
PageRank
Yiwei Zhang15212.65
Gennian Ge290495.51