Towards Practical Private Information Retrieval from MDS Array Codes

Abstract

Private information retrieval (PIR) is the problem of privately retrieving one out of $M$ original files from $N$ severs, i.e., each individual server learns nothing about the file that the user is requesting. Usually, the $M$ files are replicated or encoded by a maximum distance separable (MDS) code and then stored across the $N$ servers. Compared to mere replication, MDS coded servers can significantly reduce the storage overhead. Particularly, PIR from minimum storage regenerating (MSR) coded servers can simultaneously reduce the repair bandwidth when repairing failed servers. Existing PIR schemes from MSR coded servers either require large sub-packetization levels or are not capacity-achieving. In this paper, a PIR protocol from MDS array codes is proposed, subsuming PIR from MSR coded servers as a special case. Particularly, the case of non-colluding, honest-but-curious servers is considered. The retrieval rate of the new PIR protocol achieves the capacity of PIR from MDS/MSR coded servers. By choosing different MDS array codes, the new PIR protocol can have some advantages when compared with existing protocols, e.g., 1) small sub-packetization, 2) (near-) optimal repair bandwidth, 3) implementable over the binary field ${\mathbf{F}}_2$.

Accepted for publication in the IEEE Transactions on Communications

References in corpus (11)

• Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction
• Private Information Retrieval from Coded Databases with Colluding Servers
• Private Information Retrieval from MDS Coded Data in Distributed Storage Systems
• Characterizing the Rate Region of the (4,3,3) Exact-Repair Regenerating Codes
• A Generic Transformation to Enable Optimal Repair in MDS Codes for Distributed Storage Systems
• An Explicit, Coupled-Layer Construction of a High-Rate MSR Code with Low Sub-Packetization Level, Small Field Size and All-Node Repair
• HashTag Erasure Codes: From Theory to Practice
• On Sub-Packetization and Access Number of Capacity-Achieving PIR Schemes for MDS Coded Non-Colluding Servers
• Bandwidth Adaptive & Error Resilient MBR Exact Repair Regenerating Codes
• On the PIR capacity of MSR codes
• Private Information Retrieval Schemes with Regenerating Codes

Cited by in corpus (4)

• Private and Secure Distributed Matrix Multiplication Schemes for Replicated or MDS-Coded Servers
• Towards the Capacity of Private Information Retrieval from Coded and Colluding Servers
• Efficient Recovery of a Shared Secret via Cooperation: Applications to SDMM and PIR
• Multi-Server Weakly-Private Information Retrieval