Source-linked AI summary
Private Information Retrieval from Coded Databases with Colluding Servers
Ragnar Freij-Hollanti, Oliver Gnilke, Camilla Hollanti, David Karpuk
TL;DR
The paper studies PIR from coded databases when servers may collude, seeking schemes whose rate can be adjusted to the suspected collusion level. It gives a general construction for coded storage, including GRS codes, that protects against flexible numbers of colluding servers while achieving the stated rate in the GRS setting. Whether these schemes are asymptotically capacity-achieving for general k and t remains open.
Problem
PIR from distributed coded databases must reduce download overhead while accounting for subsets of servers that may share their interactions with the user.
Method
The paper constructs a general PIR scheme for coded storage whose collusion protection can be selected through the retrieval-code construction.
Results
Theorem 10 provides GRS-based schemes for every 1 ≤ t ≤ n − k that protect against any t colluding servers and have rate n−(k+t−1)/n.
Takeaways & Limitations
The framework unifies PIR schemes across different collusion levels while keeping the rate independent of the number of stored files.
Takeaways & Limitations
Asymptotic capacity achievement remains open for general k and t, and the exposition restricts comparisons to retrieving one file because multi-message PIR has higher capacity.
Abstract
from arXiv · showhide
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.
1. Introduction.
The paper develops PIR for fixed coded storage systems with colluding servers, addressing communication and storage constraints in prior approaches. For GRS storage codes, its scheme supports flexible collusion levels with a rate determined by the code parameters.
- Motivation: Prior coded-PIR schemes faced trade-offs involving exponentially many servers, growing server counts, or storage overhead.The paper instead considers a fixed number of servers, while keeping storage overhead fixed rather than optimizing it.
- Contribution: The proposed framework handles any number 1 ≤ t ≤ n − k of colluding servers.Earlier schemes covered the endpoint cases t = n − k and t = 1.
- Contribution: For a GRS storage code, the scheme achieves rate 1 − (k + t − 1)/n while protecting against t colluding servers.The rate depends on the minimum distance of a star product, and the construction’s performance and field size do not depend on the number of files.
2. Coding-Theoretic Preliminaries.
This section introduces coding-theoretic notation, MDS and GRS codes, and the star product used in the PIR construction. It establishes that star products of GRS codes remain GRS codes with predictable dimension.
- Basic Definitions: An [n, k, d]-code has length n, dimension k, and minimum distance d, with minimum distance also characterized through codeword supports for linear codes.The Singleton bound gives the standard relationship among these parameters.
- Basic Definitions: MDS codes attain the Singleton bound with equality, so an [n, k] MDS code has d = n − k + 1.Every subset of k coordinates is an information set for an MDS code.
- Generalized Reed-Solomon Codes: A GRS code GRSk(α, v) consists of evaluations of degree-bounded polynomials at distinct α_i, scaled by nonzero multipliers v_i.GRSk(α, v) is an [n, k] MDS code, and its dual is another GRS code with dimension n − k.
- Star Products: The star product V ⋆ W is the span of coordinatewise products of vectors from V and W.It is central to the PIR scheme because it determines the scheme’s rate.
- Star Products: For GRS codes sharing evaluation points, GRSk(α, v) ⋆ GRSℓ(α, w) = GRSmin{k+ℓ−1,n}(α, v ⋆ w).The result follows by multiplying polynomial evaluations and spanning the resulting monomial degrees.
3. Coded Storage and Private Information Retrieval.
The paper formalizes coded storage and linear PIR, including rate and privacy against colluding servers. Files are encoded with a linear code and distributed across servers, while randomized queries support private reconstruction.
- Coded Storage: Each file is encoded as yi = xiGC, and each server stores one coordinate of every encoded file.For an MDS storage code, the system is maximally robust against server failures.
- Private Information Retrieval: A linear PIR scheme sends randomized query vectors to servers, receives scalar responses, and reconstructs the desired file from repeated iterations.The query, response, iteration, and reconstruction steps define the scheme’s operation.
- Rate: The PIR rate compares the file size with the total downloaded information, while query-upload costs are ignored.The paper permits adjusting file rows and iteration count to download exactly one whole file.
- Privacy: Protection against t colluding servers requires every t-server subset to have the same joint query distribution for every requested file.Consequently, those servers learn nothing about the requested index.
4. A General PIR Scheme for Coded Storage with Colluding Servers.
The scheme uses a storage code and a retrieval code to construct randomized queries that retrieve encoded symbols across iterations while protecting against colluding servers. Its rate is governed by the star-product distance, with file dimensions and iteration sets chosen to recover exactly one file.
- The framework targets high-rate PIR for coded databases while allowing protection against a flexible number of colluding servers.
- The storage code C distributes the database, while retrieval code D determines the scheme’s privacy properties.
- The parameter c is defined as d_(C⋆D)−1, the star-product minimum-distance quantity governing the scheme.
- Iteration: The file is sized so bk=sc, enabling s iterations to download k symbols from every encoded row and reconstruct one file.
- Iteration: The set J is partitioned into iteration-specific subsets so each row yields encoded symbols over successive iterations.
- Query Construction: Random query codewords are sampled from D for every file and row, then selectively modified by adding standard-basis vectors for the desired file.
2. Responses: To understand the response vector ri, we first calculate ri
Responses combine randomized codeword contributions with desired-file symbols, which can be isolated using the dual of the star-product code. The construction is correct under information-set conditions and private against colluding servers determined by the retrieval code.
- Responses: The response vector contains known desired-file symbols embedded among randomized contributions, with the desired symbols supported in identifiable locations.
- Iteration: After the iteration-specific sets are shifted across J, their disjoint union supplies k distinct symbols from each encoded row.
- Data Reconstruction: Multiplying responses by a generator matrix of (C⋆D)⊥ recovers c desired encoded symbols per iteration.
- Correctness: Theorem 7 gives rate (d_(C⋆D)−1)/n when its code and information-set conditions hold.
- Privacy: Theorem 8 protects the scheme against d_(D⊥)−1 colluding servers.
- Privacy: The query distribution is independent of the desired-file index because random retrieval-codeword distributions remain uniform after basis-vector translation.
- Examples: For an MDS storage code with D=C⊥, the scheme has rate 1/n and protects against any n−k colluding servers.
- Examples: For replicated storage with an MDS retrieval code, the scheme achieves rate (n−t)/n and protects against any t colluding servers.
5. Private Information Retrieval from GRS Codes.
For GRS storage codes, the construction supports any 1 ≤ t ≤ n − k colluding servers at rate 1 − (k+t−1)/n. It recovers the known non-colluding and replication cases asymptotically, while general capacity remains open.
- GRS codes attain equality in the star-product distance bound, making them optimal for this scheme’s privacy-rate tradeoff among storage codes covered by the theorem.The equality condition characterizes GRS codes under the stated non-repetition-code assumptions.
- For every 1 ≤ t ≤ n − k, a GRS storage code admits a retrieval code protecting against t colluding servers at rate 1 − (k+t−1)/n.The retrieval code is chosen so the star-product minimum distance yields the stated rate.
- When k = 1, the scheme has rate 1 − t/n and is asymptotically capacity-achieving as the number of files m grows.This is the replication-storage special case.
- When t = 1, the scheme has rate 1 − k/n and is likewise asymptotically capacity-achieving as m grows.This is the non-colluding special case.
- The general capacity for k > 1 and t > 1 remains unknown, and the paper leaves open whether these schemes are asymptotically capacity-achieving there.A prior capacity conjecture was disproven by an explicit coded-PIR scheme with m = 2, n = 4, k = 2, t = 2, and rate 3/5 versus conjectured 4/7.
- For n = 12 and m = 8, plotted achievable rates are described as quite close to capacity even with relatively large collusion.The figure varies t and storage-code rate; black curves and asterisks show known capacity cases.
6. An example in the intermediate regime.
The example uses generalized Reed–Solomon storage and query codes over F5 to retrieve a file while tolerating two colluding servers. The construction extracts two desired blocks using five queries and decodes them through the dual star-product code.
- Storage and query codes: Each file is divided into two blocks and distributed across five servers using a GRS2 storage code over F5.The example uses the storage code C = GRS2(α, 1) and distributes the file blocks across the servers.
- Storage and query codes: The query code is D = GRS2(α, 1), whose star product with C is GRS3(α, 1).Its dual is computed as (C ⋆ D)⊥ = GRS2(α, u), which becomes identical to C in this example.
- Privacy protection: D⊥ is a [5, 3] MDS code, so the scheme protects against t = 2 colluding servers.Different generator matrices are chosen for storage and queries because systematic form aids decoding while canonical form aids computation.
- Query and response process: Random codewords generate uniformly distributed queries, with the desired file index added through a standard basis vector.The servers respond by projecting their stored data onto the query vectors, producing response vectors for decoding.
- Decoding and outcome: The desired symbols are decoded by multiplying each response vector by G(C ⋆ D)⊥, yielding two data blocks from five queries.The construction maintains privacy against two colluding servers while extracting the requested blocks.