PaperlayerView exact revision on arXiv

Source-linked AI summary

The Capacity of Robust Private Information Retrieval with Colluding Databases

Hua Sun, Syed A. Jafar

arXiv:1605.00635v1cs.ITcs.CRcs.IR

TL;DR

The paper studies how efficiently messages can be privately retrieved when databases may collude and some may fail to respond. It constructs capacity-achieving schemes and shows robust T-private PIR has capacity (1 + T/N + T^2/N^2 + ... + T^(K-1)/N^(K-1))^-1.

  • Problem

    PIR seeks efficient message retrieval while protecting the desired message index, including against collusion among any T databases and nonresponse from some databases.

  • Method

    The paper characterizes T-private PIR capacity and extends its capacity-achieving scheme to incorporate robustness constraints.

  • Results

    The capacity of robust T-private PIR is (1 + T/N + T^2/N^2 + ... + T^(K-1)/N^(K-1))^-1.

  • Takeaways & Limitations

    Robustness imposes no capacity cost from not knowing in advance which N databases will respond.

  • Takeaways & Limitations

    Optimizing upload costs and symbol size remains an avenue for future work.

Abstract

from arXiv · show

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of $K$ messages from $N$ non-communicating replicated databases (each holds all $K$ messages) while keeping the identity of the desired message index a secret from each individual database. The information theoretic capacity of PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. $T$-private PIR is a generalization of PIR to include the requirement that even if any $T$ of the $N$ databases collude, the identity of the retrieved message remains completely unknown to them. Robust PIR is another generalization that refers to the scenario where we have $M \geq N$ databases, out of which any $M - N$ may fail to respond. For $K$ messages and $M\geq N$ databases out of which at least some $N$ must respond, we show that the capacity of $T$-private and Robust PIR is $\left(1+T/N+T^2/N^2+\cdots+T^{K-1}/N^{K-1}\right)^{-1}$. The result includes as special cases the capacity of PIR without robustness ($M=N$) or $T$-privacy constraints ($T=1$).

1 Introduction

PIR retrieves one message from replicated databases while hiding its identity, and this privacy problem connects to major topics in cryptography, coding theory, complexity theory, and wireless communications. The paper studies stronger privacy against colluding databases and robustness to nonresponding databases.

  • PIR is connected to oblivious transfer, locally decodable codes, secure multiparty computation, secret sharing, and blind interference alignment.
  • PIR retrieves a desired message from N databases storing all K messages without revealing the message identity to any individual database.
  • The Shannon-theoretic formulation allows arbitrarily large messages, making upload cost negligible compared with download cost.
  • T-private PIR protects the desired message index even when any T of the N databases collude.
  • Robust PIR considers M ≥ N databases where any M − N may fail to respond, requiring privacy and correctness from any N responses.

2 Problem Statement

The problem models retrieval of one replicated message through queries and deterministic database answers, requiring correctness and information-theoretic privacy against any T colluding databases. Robustness additionally requires decoding from any N of M databases that respond.

  • The user retrieves W_k from N databases, each storing W_1, ···, W_K, while hiding k from every colluding subset of up to T databases.
  • The user generates and sends queries independently of the message realizations, and each database deterministically computes an answer from its query and all messages.
  • Correctness requires the user to decode W_k from the collected answers and queries.
  • T-privacy requires every set of T queries, and consequently every set of T answer strings, to be independent of k.
  • The PIR rate measures desired information per downloaded bit, and capacity is the supremum of this rate over all PIR schemes.
  • Robust T-private PIR uses M ≥ N databases and must remain correct when any N answering strings are collected.

3 Main Result: Capacity of Robust T-Private PIR

The paper characterizes the capacity of T-private PIR and shows that robustness does not reduce it. The same expression applies when the responding databases are not known in advance, although the achieving scheme's communication complexity grows with M.

  • The capacity of T-private PIR is (1 + T/N + T^2/N^2 + ··· + T^(K−1)/N^(K−1))^−1.
  • The capacity decreases with T and K, increases with N, approaches 1 − T/N as K grows, and approaches 1 as N grows with T fixed.
  • When T = N, capacity is 1/K, so the user must download all K messages to remain private.
  • The capacity of robust T-private PIR is the same expression, (1 + T/N + T^2/N^2 + ··· + T^(K−1)/N^(K−1))^−1.
  • Robustness imposes no capacity penalty from uncertainty about which N databases respond, but the achieving scheme's communication complexity increases with M.

4 Proof of Theorem 1: Achievability

The achievable scheme combines a structured query design with specializations that enforce T-privacy and correctness. Its construction uses symmetry, message symmetry, previously acquired undesired-message side information, and an iterative matrix-based argument.

  • The scheme has two key components: a query structure and its specialization to ensure T-privacy and correctness.
  • The query structure enforces symmetry across databases and message symmetry within each database's query.
  • The scheme exploits previously acquired side information about undesired messages to retrieve new desired-message symbols.
  • The construction uses independently uniform full-rank matrices, invertible transformations, and index vectors to establish identical-distribution properties.
  • The proof uses row-rank invariance and bijective transformations to show that transformed selected rows preserve the relevant distribution.

4.1 K = 2 Messages, N = 3 Databases, T = 2 Colluding Databases

This construction uses an MDS-coded query structure so any two colluding databases can exploit external undesired-message side information while preserving privacy and correctness. For N=3, K=2, and T=2, it achieves the capacity rate 3/5.

  • Query Structure: The query skeleton requests desired symbols, adds undesired-message counterparts, and combines further symbols with side information.The first two databases request a1–a4, database symmetry adds a5–a6, and message symmetry adds b1–b6 before combined queries are introduced.
  • Query Structure: A (9,6) MDS code makes every three additional undesired symbols functions of the other six, supporting the side-information dependencies required for any colluding pair.This simultaneously addresses the possible colluding pairs DB1–DB2, DB1–DB3, and DB2–DB3.
  • Specialization to Ensure Correctness and Privacy: The specialization encodes b[1:9] from six randomized undesired-message symbols using a publicly known MDS generator matrix.Any six elements of b[1:9] recover all nine because every six rows of the generator matrix are invertible.
  • Specialization to Ensure Correctness and Privacy: Correctness follows by recovering b[1:6], then all b[1:9], and finally all desired symbols; privacy follows from the indistinguishable randomized maps for desired and undesired messages.The queries seen by any two colluding databases contain six variables from each message’s coded representation.
  • Specialization to Ensure Correctness and Privacy: 9 desired symbols are recovered from 15 downloaded symbols, yielding rate 9/15 = 3/5, which matches capacity.The construction therefore achieves the capacity for this setting.

4.2 K = 2 Messages, N = 4 Databases, T = 2 Colluding Databases

For two messages, four databases, and two colluding databases, the construction balances side information across databases and specializes it with an MDS code. It recovers 16 desired symbols at the capacity rate 2/3.

  • Query Structure: The query structure begins with two desired symbols per first database, then enforces symmetry across databases and messages.The construction introduces a1–a8 and corresponding b-symbols before adding combined queries.
  • Query Structure: Four external side-information symbols provide a budget of two exploited symbols per database for generating new desired information.The side information is b5–b8 for the first two databases, and the resulting combined queries are symmetrically added to databases three and four.
  • Specialization: Each message is represented by 16 symbols, with private full-rank random matrices used to form the coded symbol vectors.The desired message is taken as W1, while W2 supplies the undesired-message symbols.
  • Specialization: The specialization uses a (16,8) MDS generator matrix on the first eight rows of the undesired-message random transform.This is plugged into the completed query structure, after which correctness and privacy follow from the construction’s prior reasoning.
  • Achieved Rate: 16 desired symbols are recovered from 24 downloaded symbols, giving rate 16/24 = 2/3, matching capacity.The result applies to the N=4, T=2, K=2 setting described in this section.

4.3 K = 2 Messages, N = 4 Databases, T = 3 Colluding Databases

For four databases with three colluding databases and two messages, the scheme uses one side-information symbol per database and an MDS-based specialization. It achieves the capacity rate 4/7.

  • Query Structure: The query structure starts with three desired symbols per first database and enforces symmetry across databases and messages.The construction builds the corresponding a- and b-symbol groups before adding combined queries.
  • Query Structure: Three external undesired-message symbols permit a budget of one exploited side-information symbol per database.The external symbols are b10, b11, and b12 for the first three databases.
  • Specialization: Each message is represented by 16 symbols and transformed using independent private full-rank 16 × 16 matrices.The desired message is W1 and the undesired message is W2.
  • Specialization: The specialization applies a (16,12) MDS generator matrix to the first 12 rows of the undesired-message transform.The resulting queries preserve correctness and privacy by the same reasoning used in the preceding examples.

4.4 K = 3 Messages, N = 3 Databases, T = 2 Colluding Databases

For three messages, three databases, and two colluding databases, the construction aligns undesired symbols so they occupy fewer effective dimensions while retaining privacy and correctness. It achieves the capacity rate 9/19.

  • Query Structure: The query structure iteratively enforces symmetry across databases and messages, then adds combinations involving undesired-message side information.The construction expands from desired-symbol groups to b- and c-symbol groups and combined queries.
  • Query Structure: For the first two colluding databases, external side information contains four b-symbols and four c-symbols, supporting two exploited symbols of each type per database.This side-information budget is distributed evenly between DB1 and DB2.
  • Specialization: Each of the three messages is represented by 27 symbols and transformed with an independent private full-rank 27 × 27 matrix.The desired message is W1, with W2 and W3 providing undesired-message symbols.
  • Specialization: The construction uses shared MDS generator matrices to align undesired symbols, allowing all nine elements of b[19:27] + c[19:27] to be recovered from any six.Interference alignment minimizes the effective number of resolvable undesired symbols by combining b19 and c19 into one symbol across downloaded equations.
  • Correctness and Privacy: Privacy follows because any two colluding databases observe randomized coded representations whose distributions are independent of the desired message index.The queried variable groups are characterized explicitly for a colluding pair of databases.

4.5 Arbitrary Number of Messages K, Arbitrary Number of Databases N, Arbitrary Number of Colluding Databases T

The construction achieves T-private PIR capacity for arbitrary K, N, and T through a layered, symmetric query scheme. Its correctness follows by recursively recovering interference, while privacy follows from identically distributed query views for any T colluding databases.

  • Query construction: The scheme uses an iterative five-step procedure that initializes desired symbols, applies database and message symmetry, allocates side information, and repeats the process K −1 times.Initialization downloads T K−1 desired symbols from the first T databases; later steps generate and distribute side information before repeating the symmetry steps.
  • Layered structure: The construction has K layers, with each layer downloading sums of j symbols and ensuring that most downloaded equations contain desired data symbols.At layer j, each database provides (N − T)j−1T K−j equations, of which (N−T)j−1T K−j−1 involve desired symbols.
  • Correctness: Interference in layer |Ki|+1 is recoverable from corresponding symbols in layer |Ki|, guaranteeing correctness.This recursive side-information structure enables the desired symbols to be separated from undesired-message interference.
  • Privacy: For any T colluding databases, the query variables from every message are arranged so their induced random maps are identically distributed, guaranteeing privacy.Full-rank MDS-generated variables and the independence of the relevant rows of the user’s random matrices establish the identical-distribution property.
  • Rate: The achieved PIR rate always matches the capacity.The construction’s desired-symbol count divided by its total download yields the capacity expression.

5 Proof of Theorem 1: Converse

The converse proves that no T-private PIR scheme can exceed the stated capacity. It establishes base cases for one and two messages, then uses entropy inequalities and induction over the number of messages.

  • Entropy bounds: Han’s inequality and the fact that dropping conditioning does not reduce entropy provide key entropy bounds in the converse.The proof explicitly invokes Han’s inequality for averaged subsets of databases and uses standard conditional-entropy monotonicity.
  • Inductive setup: The outer-bound proof proceeds by induction, first establishing the cases K = 1 and K = 2 for arbitrary N and T.These basis cases set up the inductive argument for arbitrary K.
  • Privacy constraint: T-privacy makes answer strings from any T databases independent of the desired message index, allowing the converse to treat their distributions uniformly across desired messages.The proof denotes these colluding-database answers as A_T and uses their message-index independence in the entropy argument.
  • Inductive reduction: Given answers from the colluding databases and the corresponding query information, the proof decodes successive messages and reduces the residual problem to PIR with K −2 messages.This reduction supplies the recursive step of the induction.
  • Conclusion: Mathematical induction proves the outer bound for all K, completing the converse proof.The basis cases and inductive step together establish the bound for every number of messages.

6 Proof of Theorem 2

The robust construction extends the capacity-achieving T-private scheme to M databases while tolerating any M −N nonresponding databases. Any N responses suffice for recovery and privacy, and the achieved rate remains unchanged.

  • Achievability strategy: Robust PIR cannot have higher capacity than T-private PIR, so the proof constructs a robust scheme that achieves the ordinary T-private capacity.The construction is based on the scheme introduced for the non-robust setting.
  • Query construction: Queries are distributed evenly across M databases using MDS-coded structures for desired symbols and side information.The user constructs query vectors over messages represented by N^K symbols and distributes their elements among all M databases.
  • Correctness: From any N responding databases, MDS decoding recovers the interference and then N^K desired symbols, guaranteeing correctness.The same decoding works regardless of which N databases respond because the relevant symbols are generated by MDS codes.
  • Privacy: The views of any T colluding databases are identically distributed across message indices, so T-privacy is preserved in the robust setting.Full-rank MDS-generated variables for desired and undesired messages imply the required independence and identical-distribution property.
  • Rate: The robust scheme achieves the same rate as the scheme without robustness, completing the proof.Thus robustness does not reduce the capacity expression, even though the scheme handles uncertain responding databases.

7 Conclusion

The paper characterizes robust T-private PIR capacity for arbitrary message, database, and privacy parameters, and discusses extensions and implementation trade-offs. It also notes that upload cost is not optimized and remains an avenue for improvement.

  • Scope of the result: The converse extends from zero-error to ε-error PIR, so both formulations have the same robust T-private capacity.The ε-error probability is only required to approach zero as message size increases.
  • Scheme properties: The achievable scheme remains capacity-optimal when projected onto a subset of messages.This preserves the message-subset optimality phenomenon observed in earlier PIR schemes.
  • Scheme properties: Unlike the earlier scheme, the present construction uses MDS-coded side information rather than each available side-information symbol individually.This distinction is identified as an important difference between the two achievable schemes.
  • Limitations and future work: Upload cost is not optimized, although grouping symbols can reduce the number of possible queries and the required field size.The refined example uses a (2, 3) MDS code over F2 instead of the original (6, 9) code, illustrating the potential savings.
Loading 1605.00635v1…