PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.

Hua Sun, Syed A. Jafar

arXiv:1701.07807v2cs.ITcs.CRcs.IRmath.IT

TL;DR

MDS-TPIR asks how efficiently a user can retrieve a message stored across servers while hiding the desired index from colluding servers, but its general capacity is not known. The paper refutes the FGHK conjecture with a counterexample and characterizes capacity for a class of instances.

  • Problem

    The general capacity of MDS-TPIR is unknown beyond extreme parameter settings, leaving the FGHK conjectured expression unverified in non-degenerate cases.

    Source: §1 · pp. 2–3

  • Method

    The paper constructs a counterexample scheme and uses its insights to characterize capacity for a class of MDS-TPIR instances.

    Source: Summary of Contribution · p. 3, §6 · p. 20

  • Results

    Rate 3/5 exceeds the conjectured 4/7 for (K, N, T, Kc) = (2, 4, 2, 2), disproving the conjecture; the paper also characterizes cases with K = 2 and Kc = N − 1.

    Source: Summary of Contribution · p. 3

  • Takeaways & Limitations

    The general capacity remains unknown, and T and Kc cannot be treated as interchangeable in general.

    Source: §6 · p. 20

    For the counterexample setting, information-theoretic capacity remains open, although the linear capacity is settled.

    Source: §4 · p. 11

Abstract

from arXiv · show

A $(K, N, T, K_c)$ instance of the MDS-TPIR problem is comprised of $K$ messages and $N$ distributed servers. Each message is separately encoded through a $(K_c, N)$ MDS storage code. A user wishes to retrieve one message, as efficiently as possible, while revealing no information about the desired message index to any colluding set of up to $T$ servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either $T$ or $K_c$ belongs to $\{1,N\}$. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting $(K, N, T, K_c) = (2,4,2,2)$, which achieves the rate $3/5$, exceeding the conjectured capacity, $4/7$. Insights from the counterexample lead us to capacity characterizations for various instances of MDS-TPIR including all cases with $(K, N, T, K_c) = (2,N,T,N-1)$, where $N$ and $T$ can be arbitrary.

1 Introduction

The paper disproves the FGHK capacity conjecture with a rate-3/5 counterexample, then characterizes several MDS-TPIR cases. It also shows that storage and privacy parameters are not interchangeable in general.

1 Introduction

  • MDS-TPIR capacity is known at the extremes where T or Kc is 1 or N, while the general non-degenerate capacity remains unresolved.When T or Kc equals N, the capacity is 1/K; T = 1 and Kc = 1 specialize to MDS-PIR and TPIR, respectively.Source: §1 · pp. 2–3
  • The FGHK conjecture proposes a general capacity expression when T + Kc ≤ N, but in non-degenerate cases it was neither known achievable nor known to be an outer bound.Its appeal includes recovering the known TPIR and MDS-PIR capacities in their respective parameter settings.Source: §1 · pp. 2–3

Summary of Contribution

  • Rate 3/5 exceeds the conjectured 4/7 for (K, N, T, Kc) = (2, 4, 2, 2), disproving the FGHK conjecture; no linear scheme can exceed 3/5 there.The scheme uses the (2, 4) MDS code (x, y) → (x, y, x + y, x + 2y).Source: Summary of Contribution · p. 3
  • The paper characterizes capacity for (K, N, T, Kc) = (2, N, T, N − 1) for arbitrary N and T, with an achievable linear scheme and an information-theoretic converse.The stated capacity expression is not legible in the supplied passage.Source: Summary of Contribution · p. 3
  • The capacity expression is not symmetric in T and Kc, and neither parameter consistently has the greater effect on capacity.The paper's comparisons show both a change in capacity when the parameters are switched and cases where the relative sensitivity reverses.Source: Summary of Contribution · p. 3

2 Problem Statement

The problem statement models retrieval from an MDS-coded storage system, with privacy against colluding servers. It defines the scheme’s rate and capacity through downloaded information and achievable retrieval rates.

2 Problem Statement

  • There are N servers, and any Kc servers’ stored data suffice to recover each of the K messages.Each message contributes L/Kc symbols to each server’s stored representation.Source: §2 · p. 4
  • The user privately chooses a desired message and sends queries; each server returns an answer based on its query and stored messages, after which the user decodes the message.The scheme permits error probability Pe, with decoding based on the received answers and queries.Source: §2 · pp. 4–5
  • Privacy requires that any set of up to T colluding servers cannot distinguish which message is desired from the joint distribution of their queries and stored data.The strategies for different desired messages must be identically distributed from those servers’ perspective.Source: §2 · p. 5
  • The PIR rate is desired-message bits per downloaded bit, and capacity is the supremum of achievable rates as decoding error tends to zero.The total download is measured in expectation, and the error probability approaches zero as message size grows.Source: §2 · p. 5

3 Settling the Conjecture

For (K, N, T, Kc) = (2, 4, 2, 2), the paper constructs a private MDS-TPIR scheme achieving rate 3/5, exceeding the conjectured capacity of 4/7. Its query dependencies limit undesired information, enabling a 20-symbol download to recover the desired message.

3 Settling the Conjecture

  • 3/5 is achievable for (K, N, T, Kc) = (2, 4, 2, 2), exceeding the conjectured capacity of 4/7 and disproving the FGHK conjecture.Theorem 1 specifies the (2, 4) MDS code (x, y) → (x, y, x+y, x+2y).Source: §3 · p. 5

3.1 Storage Code

  • The (2, 4) MDS storage code stores (a, b, a+b, a+2b) for one message and the same form for the other; any two servers suffice to recover both.Each server stores six symbols for each message.Source: §3.1 · p. 6

3.2 Construction of Queries

  • 12 independent desired symbols are retrieved because each desired query vector is used twice, while dependencies among undesired queries reduce their information to eight dimensions.The construction makes query distributions indistinguishable to any two colluding servers by arranging a shared vector among the query sets.Source: §3.2 · p. 7, §3.2.2 · p. 8

3.2.1 Case 1. Wk is Desired

  • The desired-message queries recover all 12 message symbols because the user obtains projections along a full-rank matrix of query vectors.This is the correctness argument for the desired-message case.Source: §3.2.1 · p. 7, §3.4 · p. 10

3.2.2 Case 2. Wk is Undesired

  • The 12 undesired symbols have only eight dimensions, so four are linear combinations of the other eight.The scheme identifies eight independent undesired symbols across the four servers.Source: §3.2.2 · p. 8

3.3 Combining Answers for Efficient Download

  • Each server’s six queried symbols are combined into five downloads, yielding 20 total symbols for the 12 desired and eight independent undesired symbols.The combining map downloads four symbols directly and mixes the last symbol.Source: §3.3 · pp. 8–9

3.4 The Scheme is Correct (Retrieves Desired Message)

  • The scheme is correct: it eliminates the recovered interference and then decodes 12 independent linear combinations of desired symbols.The full-rank server matrices leave enough independent combinations to recover all 12 desired message symbols.Source: §3.4 · p. 10

3.5 The Scheme is Private (to any T = 2 Colluding Servers)

  • Queries to any two servers are identically distributed regardless of the desired message, establishing T = 2 privacy.The proof uses a bijection between query-vector collections and their uniformly distributed counterparts.Source: §3.5 · pp. 10–11

4 Optimality of Rate 3/5

For the specified (2, 4, 2, 2) instance and storage code, the linear capacity is 3/5. The paper leaves the unrestricted information-theoretic capacity open.

4 Optimality of Rate 3/5

  • The information-theoretic capacity remains open, because the best proven information-theoretic upper bound does not settle the unrestricted problem.The paper defines linear capacity separately as the highest rate achievable by scalar or vector linear PIR schemes.Source: §4 · p. 11
  • 3/5 is the linear capacity for the specified (2, 4, 2, 2) instance and (2, 4) MDS storage code.The converse shows no scalar or vector linear PIR scheme for this code can exceed the achievable rate.Source: §4 · p. 11

Lemma 1

  • The converse bounds redundant desired-message downloads by analyzing overlaps among the servers’ query-vector spaces.Symbols are redundant when they are linear combinations of downloads from other servers and contribute no new information.Source: §4 · p. 12

5 Capacity of a Class of MDS-TPIR Instances

The paper characterizes capacity for the family (K, N, T, Kc) = (2, N, T, N−1), with arbitrary N and T. Examples for T = 2 and T = 3 illustrate schemes achieving the stated capacities.

5 Capacity of a Class of MDS-TPIR Instances

  • For (K, N, T, Kc) = (2, N, T, N−1), the paper gives the capacity for arbitrary N and T.The T = N case is the single-database setting, where downloading everything gives capacity 1/2.Source: §5 · p. 14

5.1 Example: Capacity achieving scheme for (K, N, T, Kc) = (2, 4, 2, 3)

  • The presented scheme achieves rate 6/11, which is the capacity for this setting according to Theorem 3, and builds upon ideas introduced for Theorem 1.Source: §5.1 · p. 14

5.1.1 Message and Storage Code

  • The example uses a (3, 4) MDS storage code in which each message is stored as (a, b, c, a+b+c) or its counterpart.Any three servers store enough information to recover both messages.Source: §5.1.1 · p. 15

5.1.2 Construction of Queries

  • For the T = 2 construction, 12 desired symbols and at most 10 independent undesired symbols are resolved from 22 downloads, yielding rate 6/11.Repeated undesired query vectors create dependencies; query sets are arranged to support privacy.Source: §5.1.2 · pp. 15–16

5.1.3 Combining Answers, Correctness and Rate

  • The T = 2 example combines answers and decodes the interfering symbols before extracting desired symbols, achieving rate 6/11.The combining matrices need only exist over a sufficiently large field.Source: §5.1.3 · p. 16

5.2 Example: Capacity achieving scheme for (K, N, T, Kc) = (2, 4, 3, 3)

  • For (2, 4, 3, 3), the example achieves capacity rate 12/23 but only establishes vanishing error probability as message size grows.It sends query spaces rather than query vectors to support privacy against three colluding servers.Source: §5.2 · p. 16

5.2.2 Construction of Queries

  • In the T = 3 construction, 12 desired symbols and at most 11 independent undesired symbols are resolved from 23 downloads.The query-space mapping is designed so that query distributions remain indistinguishable to any three colluding servers.Source: §5.2.2 · pp. 17–18

5.2.3 Combining Answers, Correctness and Rate

  • Random combining matrices yield error probability tending to zero as field size grows, while the construction achieves rate 12/23.The privacy proof establishes the required distributional equivalence for the three-server query spaces.Source: §5.2.3 · p. 18, §5.2.4 · p. 20

6 Conclusion

The paper refutes the FGHK conjecture with a counterexample and characterizes capacity for a class of MDS-TPIR instances. The general capacity expression remains unknown.

6 Conclusion

  • The rate beating the FGHK conjecture is the best possible among linear schemes for the same storage code.The paper does not establish unrestricted information-theoretic optimality for that counterexample.Source: §6 · p. 20
  • The counterexample’s insights lead to capacity characterizations for a class of MDS-TPIR instances.The class includes (K, N, T, Kc) = (2, N, T, N−1).Source: §6 · p. 20
  • The capacity expression cannot be symmetric in T and Kc, and the general MDS-TPIR capacity remains unknown.Source: §6 · p. 20

7.1 Examples of Optimal Schemes over Small Fields

The section gives explicit small-field MDS-TPIR schemes, including capacity-achieving examples for two settings. The examples show rates of 6/11 and 4/7, respectively.

7.1 Examples of Optimal Schemes over Small Fields

  • The section presents two explicit small-field examples to show that large field size may not be essential for capacity-achieving MDS-TPIR schemes.The examples cover the binary-field (2, 3, 2, 2) and F13 (2, 4, 3, 2) settings.Source: §7.1 · p. 20, §7.1.1 · p. 20, §7.1.2 · p. 21

7.1.1 Example 1

  • 6/11 is achieved over the binary field for (K, N, T, Kc) = (2, 3, 2, 2), matching the setting’s capacity.Each message has 6 bits; the scheme downloads 4 bits from each of the first two servers and 3 from the third.Source: §7.1.1 · pp. 20–21

7.1.2 Example 2

  • 4/7 is achieved over F13 for (K, N, T, Kc) = (2, 4, 3, 2), matching the setting’s capacity.The construction uses 4 symbols per message and 6 upload bits per server.Source: §7.1.2 · pp. 21, 23
  • The second scheme exploits that the undesired symbol downloaded from Server 4 is determined by downloads from the first three servers, while desired symbols are independent.The example is not covered by Theorem 3; the authors also describe a related scheme for a specified MDS storage code over a sufficiently large field.Source: §7.1.2 · pp. 22–23

7.2 Achievability Proof for Theorem 3 when T = 2

For T = 2 and an (N − 1, N) storage code, the construction makes interference dependent, combines answers to remove it, and proves correctness and privacy. It achieves rate (N^2 − N)/(2N^2 − 3N + 2).

7.2.1 Storage Code

  • The (N − 1, N) storage code stores each message’s final server share as the sum of its shares at the first N − 1 servers.This makes the storage at any N − 1 servers sufficient under the MDS code.Source: §7.2.1 · p. 24

7.2.2 Construction of Queries

  • Queries use rows of independently and uniformly chosen full-rank matrices, with N − 2 common vectors forming dependent interference symbols.The N − 2 interference symbols are linear combinations of the other symbols, reducing interference dimension to at most N(N − 1) − (N − 2).Source: §7.2.2 · p. 24

7.2.3 Combining Answers for Efficient Download

  • The answer-combining construction reduces each server’s 2(N − 1) queried symbols to (L + I)/N downloads, where I bounds the independent interference dimensions.The required combining matrices exist over a sufficiently large prime field, as established using the Schwartz-Zippel lemma.Source: §7.2.3 · pp. 25–26

7.2.4 The Scheme is Correct (Retrieves Desired Message)

  • The construction yields L independent desired symbols, and the user recovers and eliminates the interference to decode with zero error.The scheme recovers I independent interference dimensions, enough because interference spans at most I dimensions.Source: §7.2.2 · p. 24, §7.2.4 · p. 26

7.2.5 The Scheme is Private (to any T = 2 Colluding Servers)

  • Privacy against any two colluding servers follows by showing their queries have the same distribution regardless of the desired message.The proof reduces this to showing that the vectors for one message are identically distributed.Source: §7.2.5 · p. 26

7.2.6 Rate Achieved is (N 2 −N)/(2N 2 −3N + 2)

  • The scheme achieves rate (N^2 − N)/(2N^2 − 3N + 2) by downloading 2N^2 − 3N + 2 symbols for N(N − 1) desired symbols.The messages contain L = N(N − 1) independent symbols over a sufficiently large finite field.Source: §7.2 · p. 23, §7.2.6 · p. 27

7.3 Achievability Proof of Theorem 3 when T > 2

For T > 2, the achievability proof generalizes the N = 4, T = 3 construction, using query spaces and answer-combining matrices over sufficiently large finite fields. The resulting scheme ensures privacy against any T colluding servers and achieves rate (N² − N)/(2N² − 3N + T).

7.3.1 Storage Code

  • The storage code is an (N − 1, N) MDS code whose final server stores the sum of the message’s first N − 1 coded symbols.The proof takes each message to contain L = N(N − 1) independent symbols.Source: §7.3.1 · p. 27, §7.3 · p. 27

7.3.2 Construction of Queries

  • Each server receives two query spaces, while common interference dimensions make N − T undesired symbols linear combinations of the others.The construction uses full-rank matrices S and S′ and a deterministic matrix P chosen to enable bijections among query spaces observed by up to T colluding servers.Source: §7.3.2 · pp. 27–28

7.3.3 Combining Answers for Efficient Download

  • Random combining matrices satisfying full-rank and interference-independence conditions exist with probability approaching 1 as the field size grows.The proof uses Schwartz–Zippel and a union bound to show that both properties hold simultaneously with high probability.Source: §7.3.3 · p. 29

7.3.4 The Scheme is Correct (Retrieves Desired Message)

  • The scheme retrieves the desired message with error probability approaching zero as the field size and corresponding message size increase.The user recovers I independent interference dimensions, eliminates the interference, then recovers the L independent desired symbols.Source: §7.3.4 · p. 29

7.3.5 The Scheme is Private (to any T Colluding Servers)

  • A matrix P satisfying the two required privacy properties exists over a sufficiently large finite field.Schwartz–Zippel and a union bound establish existence; the resulting query spaces for any T servers are identically distributed whether a message is desired or undesired.Source: §7.3.5 · pp. 30–32
  • The scheme is private against any T colluding servers, with the proof using that S and S′ have the same distribution.The argument concludes by establishing equations (186) and (176).Source: §7.3.5 · p. 32

7.3.6 Rate Achieved is (N 2 −N)/(2N 2 −3N + T)

  • (N^2 − N)/(2N^2 − 3N + T) is achieved by downloading 2N^2 − 3N + T symbols for a desired message of N(N − 1) symbols.Source: §7.3.6 · p. 32

7.4 Converse for Arbitrary K

The converse section develops recursive capacity outer bounds for arbitrary K in two MDS-TPIR settings. It gives specific finite- and large-K consequences, while leaving some capacity questions open.

7.4 Converse for Arbitrary K

7.4.1 (K, N, T, Kc) = (K, 4, 2, 2)

  • For (K, 4, 2, 2), the converse gives an information-theoretic bound of 8/13 when K = 2; as K → ∞, its upper bound converges to 5/14, leaving asymptotic optimality open.The Freij-Hollanti et al. scheme achieves rate 1/4 asymptotically in this setting.Source: §7.4.1 · p. 35

7.4.2 (K, N, T, Kc) with N < T + Kc

  • When N < T + Kc, the recursive bound implies capacity decays as 1/K for fixed N, T, and Kc, making download-everything rate 1/K order optimal as K grows.For K = 2 and Kc = N − 1, the bound is (N^2 − N)/(2N^2 − 3N + T).Source: §7.4.2 · pp. 35, 37

7.5 Restricted Colluding Sets

The section examines how restricting colluding sets affects MDS-TPIR capacity. Unlike TPIR, these restrictions can change capacity, with examples giving exact rates for several settings.

7.5 Restricted Colluding Sets

  • In TPIR, restricting collusions to cyclically contiguous sets or disjoint sets of size T does not affect capacity, motivating a test of whether the same holds for MDS-TPIR.The section reports contrasting MDS-TPIR outcomes.Source: §7.5 · p. 37, §7.5.2 · p. 39

7.5.1 (K, N, T, Kc) = (2, 4, 2, 2) with Cyclically Adjacent Colluding Sets

  • With (K, N, T, Kc) = (2, 4, 2, 2), allowing only cyclically adjacent colluding pairs gives capacity 8/13.The scheme is not private against non-adjacent pairs, so this result applies only under the stated privacy restriction.Source: §7.5.1 · p. 38

7.5.2 Disjoint Colluding Sets of T Servers Each

  • For (2, 4, 3, 2), restricting collusions to the disjoint pairs {1, 2} and {3, 4} raises capacity from 6/11 to 4/7.This contrasts with TPIR, where the described disjoint-set restriction leaves capacity unchanged.Source: §7.5.2 · p. 39

Example 1

For (K, N, Kc) = (2, 4, 2), the stated restricted-collusion patterns both have capacity 2/3.

Example 1

  • For (K, N, Kc) = (2, 4, 2), colluding sets {1, 2}, {3, 4} or {1, 2}, {3}, {4} give capacity 2/3.The stated scheme achieves rate 4/6 = 2/3.Source: Example 1 · p. 40

Example 2

For (K, N, Kc) = (2, 3, 2), each of two stated collusion patterns has capacity 4/7.

Example 2

  • For (K, N, Kc) = (2, 3, 2), colluding sets {1, 2}, {2, 3} or {1, 2}, {3} give capacity 4/7.The converse normalizes the bound and yields an upper bound of 4/7 on rate.Source: Example 2 · pp. 40–41
Loading 1701.07807v2…