Private Information Retrieval from Coded Databases with Colluding Servers

Abstract

We present a general framework for Private Information Retrieval (PIR) from arbitrary coded databases, that allows one to adjust the rate of the scheme according to the suspected number of colluding servers. If the storage code is a generalized Reed-Solomon code of length n and dimension k, we design PIR schemes which simultaneously protect against t colluding servers and provide PIR rate 1-(k+t-1)/n, for all t between 1 and n-k. This interpolates between the previously studied cases of t=1 and k=1 and asymptotically achieves the known capacity bounds in both of these cases, as the size of the database grows.

References in corpus (4)

• PIR with Low Storage Overhead: Coding instead of Replication
• The Capacity of Robust Private Information Retrieval with Colluding Databases
• A general private information retrieval scheme for MDS coded databases with colluding servers
• On private information retrieval array codes

Cited by in corpus (59)

• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
• Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns
• Private and Secure Distributed Matrix Multiplication Schemes for Replicated or MDS-Coded Servers
• Capacity of Private Linear Computation for Coded Databases
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• Towards the Capacity of Private Information Retrieval from Coded and Colluding Servers
• Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective
• The Capacity of Private Information Retrieval with Partially Known Private Side Information
• On Single Server Private Information Retrieval with Private Coded Side Information
• Double Blind $T$-Private Information Retrieval
• On the Capacity of Secure Distributed Batch Matrix Multiplication
• Towards Practical Private Information Retrieval from MDS Array Codes
• Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
• Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers
• Squares of Matrix-product Codes
• Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries
• On Sub-Packetization and Access Number of Capacity-Achieving PIR Schemes for MDS Coded Non-Colluding Servers
• Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost
• Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
• $X$-secure $T$-private Information Retrieval from MDS Coded Storage with Byzantine and Unresponsive Servers
• Cross Subspace Alignment and the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval
• ON-OFF Privacy Against Correlation Over Time
• On the Information Leakage in Private Information Retrieval Systems
• On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage
• Preserving Privacy while Broadcasting: $k$-Limited-Access Schemes
• Efficient Recovery of a Shared Secret via Cooperation: Applications to SDMM and PIR
• Multi-Party Private Set Intersection: An Information-Theoretic Approach
• Private Function Computation for Noncolluding Coded Databases
• Private Polynomial Computation for Noncolluding Coded Databases
• On the Storage Cost of Private Information Retrieval
• The Capacity of Private Information Retrieval with Private Side Information Under Storage Constraints
• Multi-Server Weakly-Private Information Retrieval
• Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers
• On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information
• Cache-Aided Private Information Retrieval with Partially Known Uncoded Prefetching: Fundamental Limits
• Private Information Retrieval Schemes Using Cyclic Codes
• Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.
• Prior Entanglement Exponentially Improves One-Server Quantum Private Information Retrieval for Quantum Messages
• Generative Adversarial User Privacy in Lossy Single-Server Information Retrieval
• Private Proximity Retrieval Codes
• ON-OFF Privacy in the Presence of Correlation
• Robust low-delay Streaming PIR using convolutional codes
• The Capacity of Single-Server Weakly-Private Information Retrieval
• Two-Server Oblivious Transfer for Quantum Messages
• t-Private Information Retrieval Schemes Using Transitive Codes
• Symmetric Private Polynomial Computation From Lagrange Encoding
• Private Information Retrieval Schemes with Regenerating Codes
• On single server private information retrieval in a coding theory perspective
• Secret Sharing in the Rank Metric
• Capacity of Quantum Private Information Retrieval with Colluding Servers
• Weighted Lifted Codes: Local Correctabilities and Application to Robust Private Information Retrieval
• Quantum $X$-Secure $T$-Private Information Retrieval From MDS Coded Storage With Unresponsive and Byzantine Servers
• Low-Complexity PIR Using Subfield Subcodes
• Quantum Private Information Retrieval for Quantum Messages
• Local Reconstruction Codes: A Class of MDS-PIR Capacity-Achieving Codes
• Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding