A general private information retrieval scheme for MDS coded databases with colluding servers

Abstract

The problem of private information retrieval gets renewed attentions in recent years due to its information-theoretic reformulation and applications in distributed storage systems. PIR capacity is the maximal number of bits privately retrieved per one bit of downloaded bit. The capacity has been fully solved for some degenerating cases. For a general case where the database is both coded and colluded, the exact capacity remains unknown. We build a general private information retrieval scheme for MDS coded databases with colluding servers. Our scheme achieves the rate $(1+R+R^2+\cdots +R^{M-1})$, where $R=1-\frac{\left(\genfrac{}{}{0ex}{}{N-T}{K}\right)}{\left(\genfrac{}{}{0ex}{}{N}{K}\right)}$. Compared to existing PIR schemes, our scheme performs better for a certain range of parameters and is suitable for any underlying MDS code used in the distributed storage system.

Submitted to IEEE Transactions on Information Theory

References in corpus (11)

• Private Information Retrieval from Coded Databases with Colluding Servers
• PIR with Low Storage Overhead: Coding instead of Replication
• Lower Bound on the Redundancy of PIR Codes
• The Capacity of Robust Private Information Retrieval with Colluding Databases
• A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers
• Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns
• Multiround Private Information Retrieval: Capacity and Storage Overhead
• On private information retrieval array codes
• Symmetric Private Information Retrieval For MDS Coded Distributed Storage
• Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
• Binary, Shortened Projective Reed Muller Codes for Coded Private Information Retrieval

Cited by in corpus (8)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• The Capacity of Private Information Retrieval with Partially Known Private Side Information
• Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
• The Capacity of Private Information Retrieval with Private Side Information Under Storage Constraints
• Cache-Aided Private Information Retrieval with Partially Known Uncoded Prefetching: Fundamental Limits
• A Capacity-Achieving $T$-PIR Scheme Based On MDS Array Codes
• The Capacity of Multi-round Private Information Retrieval from Byzantine Databases