A Capacity-Achieving T-PIR Scheme Based On MDS Array Codes

2019/01/17 by Xu, Jingke, Zhang, Yaqian, Zhang, Zhifang
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1901.05772

Abstract

Suppose a database containing M records is replicated in each of N servers, and a user wants to privately retrieve one record by accessing the servers such that identity of the retrieved record is secret against any up to T servers. A scheme designed for this purpose is called a T-private information retrieval (T-PIR) scheme. In this paper we focus on the field size of T-PIR schemes. We design a generalcapacity-achieving T-PIR scheme whose queries are generated by using some \rm MDS array codes. It only requires field size q≥√[ℓ]N, where ℓ=min\t^M-2,(n-t)^M-2\, ~t=T/\rm gcd(N,T),~n=N/\rm gcd(N,T) and has the optimal sub-packetization Nn^M-2. Comparing with existing capacity-achieving T-PIR schemes, our scheme has the following advantage, that is, its field size monotonically decreases as the number of records M grows. In particular, the binary field is sufficient for building a capacity-achieving T-PIR scheme as long as M≥ 2+\lceillog_μlog₂N\rceil, where μ=min\t,n-t\>1.

Related

• Building Capacity-Achieving PIR Schemes with Optimal Sub-Packetization over Small Fields
• Capacity-Achieving PIR Schemes with Optimal Sub-Packetization
• Achieving Capacity of PIR with Private Side Information with Low Sub-packetization and without MDS Codes
• Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.
• A general private information retrieval scheme for MDS coded databases with colluding servers