Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models

Abstract

Private information retrieval (PIR) gets renewed attentions due to its information-theoretic reformulation and its application in distributed storage system (DSS). The general PIR model considers a coded database containing $N$ servers storing $M$ files. Each file is stored independently via the same arbitrary $(N,K)$-MDS code. A user wants to retrieve a specific file from the database privately against an arbitrary set of $T$ colluding servers. A key problem is to analyze the PIR capacity, defined as the maximal number of bits privately retrieved per one downloaded bit. Several extensions for the general model appear by bringing in various additional constraints. In this paper, we propose a general PIR scheme for several variant PIR models including: PIR with robust servers, PIR with Byzantine servers, the multi-file PIR model and PIR with arbitrary collusion patterns.

The current draft is extended by considering several PIR models. The original version named "Multi-file Private Information Retrieval from MDS Coded Databases with Colluding Servers" is abridged into a section within the current draft. arXiv admin note: text overlap with arXiv:1704.06785

References in corpus (9)

• Private Information Retrieval from Coded Databases with Colluding Servers
• The Capacity of Robust Private Information Retrieval with Colluding Databases
• A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns
• The Capacity of Private Information Retrieval with Partially Known Private Side Information
• The Capacity of Symmetric Private Information Retrieval
• Symmetric Private Information Retrieval For MDS Coded Distributed Storage
• Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes

Cited by in corpus (8)

• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• Unified Approach to Secret Sharing and Symmetric Private Information Retrieval with Colluding Servers in Quantum Systems
• Cross Subspace Alignment and the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval
• On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage
• Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers
• The Capacity of Multi-round Private Information Retrieval from Byzantine Databases
• Robust low-delay Streaming PIR using convolutional codes
• The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns