PaperlayerView exact revision on arXiv

Source-linked AI summary

The Capacity of Private Information Retrieval from Byzantine and Colluding Databases

Karim Banawan, Sennur Ulukus

arXiv:1706.01442v1cs.ITcs.CRcs.IR

TL;DR

The paper studies single-round private information retrieval with Byzantine databases, zero-error recovery, and privacy against T colluding databases. It develops an error-correcting achievable scheme and a cut-set-based converse, characterizing the BPIR capacity and its penalties from adversarial databases.

  • Problem

    The paper asks how to privately reconstruct a desired message without errors when B databases may return incorrect answer strings while T databases can collude.

  • Method

    The achievable scheme extends robust PIR using punctured MDS codes, successive interference cancellation, and an outer-layer MDS code, while the converse adapts the adversarial network-coding cut-set bound.

  • Results

    The paper determines the exact BPIR capacity and shows that correcting Byzantine errors requires 2B redundant storage nodes plus a retrieval-rate penalty reflecting uncertainty about which databases are honest.

  • Takeaways & Limitations

    For unsynchronized PIR without knowledge of the mis-synchronized fraction, the single-round capacity is the same as the BPIR capacity.

  • Takeaways & Limitations

    The formulation assumes no advance knowledge of the mis-synchronized fraction and considers only single-round schemes, preventing direct rate comparison with the two-round scheme in.

Abstract

from arXiv · show

We consider the problem of single-round private information retrieval (PIR) from $N$ replicated databases. We consider the case when $B$ databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of $M$ messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the $T$-privacy constraint in this paper, where any $T$ databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of \emph{correct symbols} that can be retrieved privately (under the $T$-privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be $C=\frac{N-2B}{N}\cdot\frac{1-\frac{T}{N-2B}}{1-(\frac{T}{N-2B})^M}$, if $2B+T < N$. This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing $2B$ databases from the system, with a penalty factor of $\frac{N-2B}{N}$, which signifies that even though the number of databases needed for PIR is effectively $N-2B$, the user still needs to access the entire $N$ databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the \emph{errors} introduced by the Byzantine databases as opposed to \emph{erasures} in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes.

1 Introduction

The paper studies single-round private retrieval when databases may be Byzantine or unsynchronized while any T databases may collude. It characterizes the exact capacity and develops an error-correcting scheme extending robust PIR.

  • Problem setting: The BPIR problem requires zero-error retrieval despite B databases returning incorrect answer strings, while preserving privacy against any T colluding databases.The Byzantine databases may coordinate their answers, and the user does not know which databases are adversarial.
  • Achievability: The achievable scheme extends robust PIR by correcting Byzantine errors rather than merely handling erasures from unresponsive databases.Its new components include punctured MDS coding, successive interference cancellation, and outer-layer MDS coding for desired symbols.
  • Converse: The converse adapts a cut-set bound from network coding against adversarial nodes to the PIR setting.Earlier Byzantine PIR work included generic transformations and schemes under restricted parameter ranges, whereas this paper characterizes the capacity.
  • Main result: The paper determines the exact BPIR capacity when 2B + T < N.The capacity is expressed in terms of N, B, T, and M, with Byzantine databases reducing the effective number of databases by 2B.
  • Main result: The capacity equals the T-private PIR capacity with N − 2B databases multiplied by (N − 2B)/N.The multiplicative factor reflects that the user must access all N databases without knowing which N − 2B databases are honest.
  • Unsynchronized PIR: For unsynchronized PIR with no knowledge of the fraction of messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity.This formulation differs from prior work that assumes only a small number of records are mis-synchronized and permits multiround retrieval.

2 Problem Formulation

The formulation models replicated messages, single-round queries, Byzantine answer corruption, and T-privacy under zero-error recovery. It defines resilient PIR rate and capacity while including unsynchronized and adversarial settings.

  • System model: The system stores M independent messages of length L over a finite field, with each of N databases ideally holding the complete message set.The replicated storage is an (N, 1) repetition code.
  • PIR operation: The user sends one query to each database to retrieve W_i without revealing the desired message index.The message set and queries are statistically independent because the user does not know the stored messages in advance.
  • Reliability model: B unknown Byzantine databases may coordinate and return arbitrary erroneous answer strings, while the remaining databases respond truthfully.No specific error pattern is assumed, and the Byzantine set need not have any specified relation to the colluding set.
  • Privacy constraint: Any T databases may exchange queries, so their joint query distribution must be statistically independent of the desired index.This is the information-theoretic T-privacy constraint.
  • Rate and capacity: The user must reconstruct W_i for every possible Byzantine action, and resilient PIR rate is defined as message size divided by total download cost.Capacity is the supremum of this rate over all single-round retrieval schemes satisfying reliability and privacy.
  • Assumptions and scope: The formulation assumes sufficiently large message and field sizes and ignores upload cost.When B = 0, BPIR with colluding databases reduces to the TPIR problem.
  • Included scenarios: In the unsynchronized setting, B databases may store different database versions, and the user has no knowledge of the mis-synchronized fraction.The resulting schemes must tolerate the worst case in which the entirety of a database is mis-synchronized; only single-round schemes are considered here.
  • Included scenarios: Adversarial attacks fit the formulation when databases alter stored contents, answer strings, or both to obstruct retrieval.These attacks are treated as arbitrary Byzantine behavior rather than a specified error channel.

3 Main Result and Discussions

The paper characterizes the exact single-round BPIR capacity under T-privacy and zero-error recovery, showing how Byzantine databases reduce the effective system size and impose a download penalty.

  • Capacity theorem: Theorem 1 gives the BPIR capacity for 2B + T < N.The capacity is established for single-round retrieval with B Byzantine databases and T colluding databases.
  • Feasibility regimes: If 2B + 1 ≤ N ≤ 2B + T, the capacity is the trivial rate 1/((2B + 1)M); otherwise, the problem is infeasible with C = 0.The trivial-rate regime requires downloading the entire database from at least 2B + 1 databases.
  • Capacity interpretation: BPIR has the same capacity as PIR with T colluding databases over N − 2B databases, multiplied by the penalty factor (N − 2B)/N.The user must download from all N databases because it cannot identify which N − 2B databases are honest.
  • Asymptotic behavior: As M →∞, the capacity approaches (N − 2B)/N, behaving as if 2B + T databases collude.This describes the large-message asymptotic form of the capacity expression.
  • Asymptotic behavior: When B = T = o(N), capacity strictly increases with N and approaches 1; when B scales as γN, the asymptotic capacity decreases linearly with slope −2 and approaches 0.The linear asymptotic behavior applies to the fraction γ of Byzantine databases.
  • Unsynchronized PIR: The same capacity applies to single-round unsynchronized PIR when the user knows only that B databases may be unsynchronized, without knowing the mis-synchronized fraction.The achievable BPIR scheme remains valid because Byzantine databases constitute a stronger adversarial model.

4 Achievability Proof

The paper presents a single-round achievable BPIR scheme that tolerates arbitrary errors from Byzantine databases, extending robust PIR from erasure correction to error correction.

  • The scheme corrects any error pattern introduced by up to B Byzantine or outdated databases.It does not assume a specific error pattern and guarantees correct decoding of the desired message.

4.1 Preliminaries

The preliminaries establish coding and statistical tools for correcting errors and erasures and preserving the distributional properties needed for privacy.

  • Puncturing an MDS code by z<n−k symbols preserves an (n−z,k) MDS code.
  • Multiplication by deterministic invertible matrices preserves the statistical equivalence of selected rows from independent random full-rank matrices.The equivalence applies to indexed row selections and supports privacy arguments.
  • A linear block code corrects up to τ errors and ρ erasures when 2τ+ρ≤d−1.
  • The no-erasure case specializes the coding capability to correcting errors according to the code’s minimum distance.

4.2 Motivating Example: M = 2 Messages, N = 5, T = 2, B = 1 Databases

The motivating example uses MDS-coded desired and undesired mixtures to correct Byzantine errors, recover the desired message, and maintain T=2 privacy for M=2, N=5, B=1.

  • Considering N−2B=3 honest databases yields 9 desired symbols, so the desired message has length L=9.A random 9×9 mixing matrix is followed by a (15,9) MDS encoding.
  • The undesired message uses 6 random symbols and a (15,6) MDS code so side-information equations can be reconstructed from any 6 symbols.
  • The punctured undesired-message code corrects errors before side information is canceled from the desired-message sums.Any 6 correct codeword symbols determine the remaining side-information equations through MDS invertibility.
  • The desired-message outer MDS code corrects the remaining errors after interference removal, yielding the true desired mixtures.The (15,9) code has minimum distance 7 and corrects the bounded errors.
  • The construction identifies the Byzantine database by comparing corrected and downloaded mixture symbols, while remaining 2-private.The privacy argument uses statistical identity of desired and undesired observations at every two databases.
  • For this example, correct decoding requires downloading the entire database from 3 databases, giving a trivial rate of 1/6.

4.3 General Achievable Scheme

The general scheme extends robust PIR across M rounds, using message and database symmetry, side information, interference alignment, and layered MDS error correction.

  • General construction: The scheme runs for M rounds and requires message length L=(N−2B)^M.Round i contains combinations of sums involving i messages.
  • Decoding: The decoding procedure corrects undesired symbols with punctured MDS codes, cancels interference successively, and corrects desired-message errors with an outer MDS code.
  • General construction: Initialization downloads T^(M−1) mixed symbols from the desired message, then each round applies message and database symmetry.The same structured quantities are downloaded across databases to support privacy.
  • Side information: Each undesired symbol generates (N−2B−T)/T side-information equations that are added to mixed desired symbols in the next round.
  • Mixture construction: The construction partitions mixtures by message subsets and uses common MDS matrices for undesired messages in each subset to enable interference alignment and joint error correction.
  • Mixture construction: Desired-message mixtures are partitioned by subsets containing the requested message, while undesired mixtures use subsets excluding it.
  • Query construction: Queries are defined for every nonempty message subset and distributed randomly and evenly among the N databases.

4.4 Decodability, Privacy, and the Achievable Rate

The scheme corrects Byzantine errors through layered MDS coding and successive side-information cancellation, while preserving T-privacy. Its achievable rate matches the stated BPIR capacity, with extensions for unresponsive databases and multiround identification.

  • Decodability: The decoder first corrects undesired-symbol errors, regenerates correct side information through MDS invertibility, and then cancels interference successively.Successive cancellation introduces nonlinear decoding, but leaves a desired-message codeword differing only at positions affected by Byzantine answers.
  • Decodability: The outer MDS code corrects the bounded errors contributed by all B Byzantine databases, yielding the desired message with zero error.Each database returns (N −2B)M−1 desired-message symbols, so the Byzantine databases introduce at most B(N −2B)M−1 errors.
  • Decodability: Corrected-versus-retrieved symbol discrepancies identify Byzantine or unsynchronized databases, which can then be expurgated.This identification is based on changes between correct codeword versions and their counterparts from the retrieval process.
  • Privacy: Queries observed by any T colluding databases consist of mixed symbols that are independent and uniformly distributed by the MDS property, guaranteeing privacy.The construction requires |I| = T(N −2B)M−1 < (N −2B)M when 2B + T < N.
  • Achievable rate: The scheme operates in M rounds, and its total download for message length L = (N −2B)M gives the BPIR capacity expression.At each round, desired symbols are combined with undesired symbols or side information before downloading from all databases.
  • Extensions: With multiple rounds, identified Byzantine databases can be removed, increasing later-round rates; with U unresponsive databases, N −2B is replaced by N −2B −U.After all B Byzantine databases are identified, the subsequent rate equals the rate for B merely unresponsive databases.

4.5 Further Examples

The examples instantiate the scheme for two privacy–Byzantine configurations and show error correction, privacy, and the differing severity of Byzantine and colluding behavior.

  • M = 3, N = 6, T = 1, B = 2: For M = 3, N = 6, T = 1, B = 2, the scheme uses L = 8 and generates side information across three-message query combinations.The construction starts with one mixed symbol from each message per database and proceeds through aligned sums in later rounds.
  • M = 3, N = 6, T = 1, B = 2: B = 2 Byzantine databases can introduce at most 2 errors in each undesired-symbol layer and 8 errors in the desired-message layer, all of which are corrected.Punctured MDS codes correct the undesired-symbol errors, while an outer MDS code corrects the desired-message errors.
  • M = 3, N = 6, T = 1, B = 2: The T = 1 example is private because each database receives four mixed symbols from every message, which are independent and uniformly distributed.This follows from the full-rank property of the MDS mixing.
  • M = 3, N = 6, T = 2, B = 1: For M = 3, N = 6, T = 2, B = 1, the scheme generates side information over three rounds using 64-symbol messages and 64 × 64 mixing matrices.The first round downloads 4 symbols from each message per database; later rounds use aligned sums and generated side information.
  • M = 3, N = 6, T = 2, B = 1: The T = 2 example corrects 4 errors in undesired layers and 16 errors in the desired layer, while remaining 2-private.Punctured and outer MDS codes provide the two correction layers; any two databases observe independent uniformly distributed mixed symbols.
  • Comparison: For the same M and N, the achievable rate is 4/21 with T = 1, B = 2 versus 8/21 with T = 2, B = 1.The comparison indicates that Byzantine behavior is more severe than colluding behavior in these examples.

5 Converse Proof

The converse adapts a cut-set bound to BPIR by showing that any N −2B honest databases must uniquely determine the desired message. Restricting the system to those databases then invokes the T-private PIR capacity as an upper bound.

  • Proof strategy: The converse adapts a cut-set upper bound from adversarial network coding to the single-round PIR setting.The bound can be viewed as a network analogue of the Singleton bound.
  • Assumptions: The proof restricts Byzantine actions to altering entire database contents and returning deterministic functions of those altered contents, which weakens the adversary for an upper bound.The argument also assumes symmetric retrieval without changing the rate.
  • Uniqueness lemma: Any set U of N −2B honest databases must produce answer strings uniquely identifying every message realization for correct decoding.If two realizations produced the same answers, swapping which B databases are Byzantine would make the scenarios indistinguishable and violate reliability.
  • Capacity bound: Because answers from any N −2B honest databases determine the desired message, restricting decoding to that set yields an upper bound by the T-private PIR capacity on N −2B databases.The final bound uses the supremum defining T-private PIR capacity and its known capacity expression.

6 Conclusions and Future Directions

The paper determines BPIR capacity and supplies an error-correcting scheme and converse for replicated databases with Byzantine and colluding nodes. It also identifies scope-dependent extensions where additional synchronization knowledge or attack structure may improve rates.

  • Main result: The exact BPIR capacity is determined for N replicated databases with B Byzantine and T-colluding databases.The capacity requires the condition 2B + T < N.
  • Interpretation: Byzantine errors require 2B redundant storage nodes and impose an additional factor (N −2B)/N because the user does not know which databases are honest.As B, N →∞ with B = γN, the capacity converges to 1 −2γ.
  • Contributions: The achievable scheme extends robust PIR using punctured MDS coding, successive interference cancellation, and an outer MDS code, while the converse adapts a cut-set bound.These components correct arbitrary Byzantine error patterns and establish the matching upper bound.
  • Future directions: Without advance knowledge of the fraction of mis-synchronized messages, single-round unsynchronized PIR and BPIR have the same capacity under this formulation.If only a small number of records are mis-synchronized and multiround schemes are allowed, higher rates may be possible.
  • Future directions: The formulation assumes Byzantine databases may be any B-subset, leaving restricted Byzantine configurations as an extension.A model allowing only certain subsets of Byzantine configurations is identified as a possible direction.
Loading 1706.01442v1…