PaperlayerView exact revision on arXiv

Source-linked AI summary

The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers

Rui Sun, Yiwei Zhang

arXiv:2610.37412v1cs.ITmath.IT

TL;DR

The paper addresses the finite-M capacity of private retrieval from coded storage with colluding, unresponsive, and Byzantine servers, a quantity not characterized generally beyond K=1. It characterizes capacity for linear, full support-rank schemes under a threshold and extends the construction to multi-file retrieval. The resulting multi-file scheme achieves capacity for P≥M/2 when K=1 or T=1.

  • Problem

    The exact finite-M capacity of U-B-MDS-TPIR remains unknown in general except for K=1.

    Source: §I · p. 2

  • Method

    The paper characterizes capacity using Schur product codes and carefully designed query matrices for GRS-coded storage under N−U−2B≥KT.

    Source: §VI · p. 21

  • Results

    For N−U−2B≥KT, capacity is characterized among linear, full support-rank schemes, and the same expression gives unrestricted capacity when K=1 or T=1.

    Source: §I · p. 2, §VI · p. 21

  • Takeaways & Limitations

    For P≥M/2, the multi-file scheme achieves capacity when either K=1 or T=1.

    Source: §VI · p. 21

Abstract

from arXiv · show

We consider the problem of private information retrieval from MDS-coded databases with $T$ colluding servers, $U$ robust servers, and $B$ Byzantine servers, referred to as U-B-MDS-TPIR. In the U-B-MDS-TPIR setting, $M$ files are stored across $N$ servers, and in this paper each file is independently encoded using an $(N,K)$ GRS code. We characterize the capacity among linear, full support-rank U-B-MDS-TPIR schemes as $C=\frac{N-U-2B}{N-U}(1+\frac{K+T-1}{N-U-2B}+\cdots+(\frac{K+T-1}{N-U-2B})^{M-1})^{-1}$ when $N-U-2B\ge KT$. When $K=1$ or $T=1$, the same expression gives the capacity without the linearity and full support-rank restrictions. We further extend the construction to the retrieval of $P$ out of $M$ files. For $P \ge \frac{M}{2}$, the resulting multi-file scheme achieves capacity when $K=1$ or $T=1$.

I. INTRODUCTION

The paper studies private retrieval from coded storage when servers may collude, fail to respond, or return Byzantine answers. It characterizes capacity for a broad class of schemes under a stated threshold, extends the construction to multi-file retrieval, and relates finite-file rates to an asymptotic capacity.

A. Problem setting of U-B-MDS-TPIR

  • Files are independently encoded with an [N,K] MDS code, and retrieval must remain private against up to T colluding servers despite U unresponsive and B Byzantine servers.The setting assumes independent files and requires decoding despite the specified server behaviors.Source: §I · p. 1, A. Problem setting of U-B-MDS-TPIR · p. 3

I. INTRODUCTION

  • The exact finite-M capacity remains unknown in general beyond K=1, including the non-colluding case T=1.This motivates characterizing the capacity for restricted scheme classes and the stated special cases.Source: §I · pp. 1–2
  • The capacity is characterized for linear, full support-rank U-B-MDS-TPIR schemes when N−U−2B ≥ KT; for K=1 or T=1, the expression gives capacity without those restrictions.The expression's finite-M rate approaches the conjectured asymptotic value while retaining a finite-M gain.Source: §I · p. 2
  • The construction extends to retrieving P out of M files, and its resulting rate is capacity-achieving when K=1 or T=1.The stated condition for the multi-file scheme is N−U−2B ≥ KT.Source: §I · p. 2
  • As M grows, the finite-M rate decreases toward the previously conjectured asymptotic capacity, with an additional gain at every finite M.The capacity expression connects the finite-M and asymptotic results.Source: §I · p. 2

II. PRELIMINARIES

  • The preliminaries define notation for vectors, matrices, generated codes, and repeated horizontal concatenation of a matrix.For G, G⟨a⟩ denotes a matrix formed by concatenating G horizontally a times.Source: §II · p. 2

B. Preparations

The preparations establish properties of Schur product codes and matrices used in the paper's coding arguments, alongside an MDS error-correction fact.

B. Preparations

  • The Schur product code is generated by component-wise products of generator-matrix rows, and inner-product vectors described in the lemma lie in that code.The product generator's rows need not be linearly independent.Source: B. Preparations · p. 4
  • Uniformly selecting or puncturing the same columns across each matrix block yields, respectively, a full-column-rank matrix or a column-MDS matrix under the defined properties.The uniformity means the same column indices are selected or deleted from every block.Source: B. Preparations · p. 5
  • For independently uniform random full-rank matrices, the stated transformed submatrices have the same joint distribution as the corresponding leading-column submatrices.The lemma's conditions specify fixed full-column-rank matrices and index vectors with distinct indices.Source: B. Preparations · p. 5
  • An [N,K] MDS code corrects error patterns up to the stated bound, allowing unique recovery when the number of errors is at most τ.The supplied passage identifies the code's minimum distance as N−K+1.Source: B. Preparations · pp. 3, 5

III. THE MDS-TPIR SCHEME WITH ROBUST AND BYZANTINE SERVERS

The paper gives the capacity of linear, full support-rank U-B-MDS-TPIR schemes under the stated server-count condition, with an unrestricted capacity result when K=1 or T=1. A worked example illustrates privacy, recovery despite unresponsive and Byzantine servers, and the achieved rate.

III. THE MDS-TPIR SCHEME WITH ROBUST AND BYZANTINE SERVERS

  • When N-U-2B≥KT, capacity is R=(N-U-2B)/(N-U)·(1+(K+T-1)/(N-U-2B)+…+((K+T-1)/(N-U-2B))^(M-1))^-1 for linear, full support-rank schemes.When K=1 or T=1, the same expression gives capacity without those restrictions.Source: §III · p. 5

A. An illustrative example for (U, B, M, N, T, K) = (1, 1, 2, 7, 1, 2)

  • In the example with (U,B,M,N,T,K)=(1,1,2,7,1,2), uniformly random invertible matrices and query-matrix column properties provide privacy while supporting recovery.Each server sees two uniformly random linearly independent query vectors and cannot distinguish the desired file; the column properties are assigned separately to privacy and correctness.Source: A. An illustrative example for (U, B,… · p. 6
  • The example recovers the desired file despite one unresponsive server and one Byzantine server, then eliminates undesired-file interference from mixed sums.Puncturing the relevant code columns allows correction of one error; the example retrieves the file at rate 4/9.Source: A. An illustrative example for (U, B,… · pp. 6–7

B. General achievable scheme

The general achievable scheme builds query matrices with specified rank and puncturing properties, then arranges queries into single-file and mixed layers. Its construction assumes N-U-2B≥KT and uses a sufficiently large finite field.

B. General achievable scheme

  • The construction assumes N-U-2B≥KT and chooses δ, γ, and β to satisfy divisibility and layer-size constraints.At the boundary N-U-2B=K+T-1, β=0 and the mixed-query part disappears, reducing the structure to a single-layer construction.Source: B. General achievable scheme · pp. 7–8
  • The resulting construction is linear and, as established by the privacy analysis, has the full support-rank property.Files contain L=δ(γ+β)^(M-1)(N-U-2B) symbols, and the queries are generated using independent uniformly selected full-rank matrices.Source: B. General achievable scheme · pp. 7–8
  • The scheme uses matrices H and X with uniform selection-rank and puncturing-MDS properties, alongside GRS generator matrices whose componentwise product has dimension K+T-1.The matrices are constructed over a sufficiently large finite field; H is block diagonal across the query layers.Source: B. General achievable scheme · p. 7
  • For N-U-2B>K+T-1, queries comprise single-index and mixed queries, with mixed-query layers encoded using shared undesired-file structure.The mixed blocks divide into γN vectors for a subset of undesired files and βN vectors associated with that subset plus the desired file.Source: B. General achievable scheme · p. 8

C. Correctness, privacy and rate

The proof establishes that the matrices needed by the construction exist over sufficiently large finite fields and verifies their rank and code-structure properties. These properties underpin the scheme’s correctness and privacy arguments.

C. Correctness, privacy and rate

  • A sufficiently large finite field guarantees existence of H by applying the Schwartz–Zippel lemma to determinant polynomials for its required column submatrices.A nonzero determinant polynomial is shown by assigning rows to form invertible blocks.Source: C. Correctness, privacy and rate · pp. 8–9
  • The same determinant-polynomial approach establishes existence of X with uniform selection full rank and the required column-MDS property.The nonzero-polynomial conditions hold simultaneously when the field is sufficiently large.Source: C. Correctness, privacy and rate · p. 9
  • H′ has the required uniform selection full-rank property, and X⋆F⟨γ+β⟩ generates the same row space as G⟨γ+β⟩⋆H′.The row-space identity follows from the shared GRS product-code structure and the full row rank of X⋆F⟨γ+β⟩.Source: C. Correctness, privacy and rate · pp. 9–10

1) Correctness:

The correctness argument recovers desired symbols despite unresponsive and Byzantine servers, while interference from undesired files remains removable. The privacy argument uses uniform selection-rank properties and random invertible matrices to make queries indistinguishable to colluding servers.

1) Correctness:

  • Puncturing the desired-symbol code for U unresponsive servers leaves a column-MDS structure that recovers the desired symbols despite up to δB corrupted downloads.Repeating recovery across the blocks and rows of S[1] retrieves the entire desired file.Source: 1) Correctness · p. 10
  • Mixed-query interference from undesired files retains a common code structure, so it can be recovered and eliminated before the truthful desired symbols are reconstructed.The construction confines erroneous information to the B Byzantine servers.Source: 1) Correctness · pp. 10–11

2) Privacy:

  • Uniform selection full-rank properties and independent uniformly random invertible matrices make the queries seen by any T servers identically distributed across files.The construction also has the full support-rank property because query vectors for each file at up to T servers are linearly independent.Source: 2) Privacy · p. 11

3) Rate:

The rate analysis gives the PIR rate for the general case and treats the boundary case separately. A worked example illustrates the construction and verifies privacy for two colluding servers.

3) Rate:

  • The PIR rate is computed for N − U − 2B > K + T − 1, with a separate derivation for the boundary N − U − 2B = K + T − 1.The boundary case has β = 0, so the authors recompute the rate because the general derivation involves β^-1.Source: 3) Rate · p. 11

D. An example for (U, B, M, N, T, K) = (1, 0, 3, 7, 2, 2)

1) T = 2 privacy:

  • The example’s queries make the scheme T = 2 private, and the construction is linear with full support-rank.For the desired and undesired files, the observed query vectors are identically distributed as uniformly chosen columns of their respective random matrices.Source: 1) T = 2 privacy · p. 13

2) Correctness:

The worked example establishes correctness despite one unresponsive server by recovering desired symbols and removing interference from undesired files. The converse bounds the retrieval rate and, with the achievable scheme, proves the stated capacity results.

2) Correctness:

  • The example retrieves the desired file from 24 downloaded desired symbols, for a PIR rate of 4/7.Puncturing permits recovery despite one unresponsive server, while the user recovers and removes undesired-file interference.Source: 2) Correctness · pp. 13–14

IV. CONVERSE BOUND

  • The converse first bounds the rate of any U-B-MDS-TPIR scheme, then specializes the bound to linear, full support-rank schemes without assuming server symmetry.When K = 1 or T = 1, the resulting capacity expression also holds without linearity or full support-rank restrictions; together with the achievable scheme, this proves Theorem III.1.Source: §IV · pp. 14–15

V. EXTENSION TO MULTI-FILE U-B-MDS-TPIR

The paper extends U-B-MDS-TPIR to simultaneous retrieval of P files while retaining the storage model and robust- and Byzantine-server assumptions. Its construction combines single-index and M-wise queries, with M-wise sums encoded by a fixed column-MDS matrix.

V. EXTENSION TO MULTI-FILE U-B-MDS-TPIR

  • The extension retrieves P of M files simultaneously while hiding their indices from any set of up to T colluding servers.The storage model and assumptions on robust and Byzantine servers remain unchanged.Source: §V · p. 15

A. Achievable scheme

  • For N − U − 2B > K + T − 1, the multi-file scheme uses only 1-wise and M-wise summations, unlike the single-file scheme’s m-wise summations for every m.A fixed P × M column-MDS matrix encodes the M-wise summations.Source: §V · p. 15
  • The construction uses GRS storage and random full-rank matrices, with a fixed P × M column-MDS matrix for combining query components.The theorem gives an achievable P-out-of-M rate when N − U − 2B ≥ KT; the supplied passage does not include the rate expression.Source: §V · p. 15, A. Achievable scheme · pp. 16–17

B. Correctness, privacy and rate

Desired-file symbols are recovered using puncturing properties that tolerate unresponsive servers and Byzantine errors. The construction also maintains privacy against T colluding servers through the distribution of their observed queries.

1) Correctness:

  • For each undesired file, the scheme recovers the missing M-wise query components despite U unresponsive and B Byzantine servers, then removes undesired-file interference.The P × M column-MDS encoding allows recovery of all P desired symbols after removing the M − P undesired symbols from each summation; errors remain confined to Byzantine servers.Source: 1) Correctness · p. 17
  • Puncturing the desired-query code across U unresponsive servers yields a column-MDS matrix that can correct up to δB erroneous symbols.Repeating recovery across the query blocks yields the desired-file symbols.Source: 1) Correctness · p. 17

2) Privacy:

  • Any T colluding servers observe query vectors identically distributed as columns of independently and uniformly chosen full-rank matrices, supporting privacy.The passage describes these distributions for each file’s queries.Source: 2) Privacy · p. 17

3) Rate:

The section computes the retrieval rate and illustrates the multi-file scheme’s query structure and correctness for a concrete parameter choice.

3) Rate:

  • The rate subsection introduces a download-based PIR-rate calculation for the multi-file scheme.The supplied rate expressions do not provide a reliably readable general formula.Source: 3) Rate · p. 18

C. An example for (P, M, U, B, N, T, K) = (2, 3, 1, 0, 7, 2, 2)

2) Correctness:

  • The example retrieves 24 symbols with a total download of 30, giving a PIR rate of 4/5.The example’s correctness argument recovers the desired symbols despite one unresponsive server.Source: 2) Correctness · p. 19

D. The converse bound

The converse bound matches the achievable multi-file rate when K = 1 or T = 1. The conclusion states the single-file capacity scope, extends the construction to multi-file retrieval, and identifies the unresolved general case.

D. The converse bound

  • When K = 1 or T = 1, the converse bounds match the achievable rates, establishing capacity for the multi-file scheme.This conclusion applies in the stated parameter regime N − U − 2B ≥ KT.Source: D. The converse bound · p. 20

VI. CONCLUSION

  • For N − U − 2B ≥ KT, the paper characterizes linear, full support-rank U-B-MDS-TPIR capacity; the same expression is unrestricted when K = 1 or T = 1.The construction is based on Schur product codes and carefully designed query matrices.Source: §VI · p. 21
  • The construction extends to retrieving P out of M files and achieves capacity for P ≥ M/2 when K = 1 or T = 1.The extension is stated under N − U − 2B ≥ KT.Source: §VI · p. 21
  • Characterizing capacity without linearity and full support-rank restrictions remains future work for K > 1 and T > 1.Source: §VI · p. 21

APPENDIX

The appendix supplies converse proofs for multi-file TPIR and MDS-PIR, which support the capacity result for U-B-MDS-TPIR in the special cases K = 1 or T = 1.

APPENDIX

  • The appendix gives direct proofs of converse bounds used to establish multi-file U-B-MDS-TPIR capacity when K = 1 or T = 1.It considers those two cases separately.Source: APPENDIX · p. 22

A. Converse bound for multi-file TPIR

B. Converse bound for multi-file MDS-PIR

  • For multi-file MDS-PIR, the proof uses T = 1 privacy and independence of the contents on K servers, then averages inequalities over K-server subsets.The averaging step also invokes Han’s inequality.Source: B. Converse bound for multi-file MDS-PIR · p. 23

Related papers

Loading 2610.37412v1…