PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Information Retrieval with Side Information

Swanand Kadhe, Brenden Garcia, Anoosheh Heidarzadeh, Salim El Rouayheb, Alex Sprintson

arXiv:1709.00112v1cs.ITcs.CR

TL;DR

The paper studies PIR with unknown prior side information, asking how users can retrieve a desired message privately while reducing downloads. It develops MDS- and partition-based schemes, connects the problem to index coding, and characterizes single-server costs while extending some results to replicated servers. With single-server side information of size M, the minimum download costs are K−M for joint demand-and-side-information privacy and ⌈K/(M+1)⌉ for demand-only privacy.

  • Problem

    The paper asks how to privately retrieve a desired database message when the user already knows M other messages whose identities are unknown to the servers, while minimizing downloaded data.

  • Method

    The paper designs information-theoretically private MDS and Partition and Code schemes, proves converses and achievability using index-coding connections, and extends selected constructions to replicated servers.

  • Results

    For one server, minimum download costs are K−M messages under joint privacy and ⌈K/(M+1)⌉ messages under demand-only privacy; some results extend to replicated servers.

  • Takeaways & Limitations

    Unknown side information can substantially reduce PIR download cost while preserving information-theoretic privacy, with the reduction depending on whether the side-information identity must also remain private.

Abstract

from arXiv · show

We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of $K$ independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of $M$ messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message without revealing its identity while minimizing the amount of data downloaded from the servers. We focus on achieving information-theoretic privacy in two scenarios: (i) the user wants to protect jointly its demand and side information; (ii) the user wants to protect only the information about its demand, but not the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is $K-M$ messages, and in the second scenario it is $\lceil \frac{K}{M+1}\rceil$ messages, which should be compared to $K$ messages, the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.

I. INTRODUCTION

The paper studies PIR when users possess unknown side information and designs information-theoretically private schemes that reduce downloads under two privacy requirements. It develops single-server constructions and extends selected results to replicated databases.

  • I. INTRODUCTION: Unknown side information can enable perfect information-theoretic privacy without downloading the entire database.The side information may be obtained opportunistically, overheard, or through previous PIR downloads.
  • I. INTRODUCTION: The MDS PIR scheme downloads K − 1 messages by coding the database with a systematic MDS code and returning parity symbols.The user decodes all messages using its one-message side information and the received coded symbols.
  • I. INTRODUCTION: The Partition and Code scheme downloads K/2 messages by randomly pairing messages and returning the XOR for each pair.The desired message is always paired with the side-information message, while the random partition preserves demand privacy.
  • I. INTRODUCTION: The paper distinguishes privacy for both demand and side-information indices from privacy for the demand index alone.The MDS PIR scheme protects both indices, whereas Partition and Code protects only the demand index.
  • I. INTRODUCTION: The two schemes are optimal for different privacy constraints, and the paper extends related side-information PIR results to multiple replicated servers.The multiple-server scheme combines ideas from the single-server construction with Sun and Jafar’s no-side-information scheme.

B. Related Work

The paper builds on PIR, index coding, and replicated-server models while formalizing side-information privacy and non-colluding PIR-SI schemes. Its setting uses unknown message subsets and distinguishes demand-only from joint privacy.

  • B. Related Work: Prior PIR work studied replicated databases and communication-efficient schemes, including information-theoretic download bounds and subpolynomial communication costs.The paper situates its contribution within both computationally efficient and information-theoretic PIR results.
  • B. Related Work: Existing work had paid little attention to how side information improves PIR, motivating this paper’s focus on side-information indices unknown to servers.The paper contrasts its model with cache-aided PIR, private broadcasting, and blind index coding.
  • B. Related Work: The PIR-SI model uses K independent messages, N non-colluding servers with identical copies, and a user-known subset of M messages excluding the demand.Queries may depend on the demand, side-information set, and side-information contents, while answers are deterministic functions of queries and messages.
  • B. Related Work: The servers know only the prior distributions of demand and side information, not the user’s realized side-information set.The user sends queries and decodes the desired message from server answers together with its side information.
  • B. Related Work: W-privacy hides the demand index, whereas (W, S)-privacy jointly hides the demand and side-information index set from each server.The rate is defined as message length divided by the total answer length, and capacity is the supremum over valid schemes.

III. MAIN RESULTS

The paper characterizes single-server PIR with side information under two privacy constraints and gives a multiple-server achievability lower bound for W-privacy.

  • The single-server results characterize the capacities of W-privacy and joint (W, S)-privacy PIR with side information.The proofs combine converse arguments with achievability schemes; the W-privacy scheme is extended to multiple servers in a restricted setting.
  • The paper also states a single-server W-privacy capacity characterization, with its proof split into converse and achievability parts.The supplied theorem passage introduces the capacity result, while the proof description identifies the two components.
  • The (W, S)-privacy capacity is (K − M)^−1 for arbitrary joint distributions with side information size M.An MDS-code scheme achieves the converse bound for any such distribution.
  • The multiple-server W-privacy result provides a capacity lower bound when (M + 1) divides K and the demand and side information follow the specified distribution.The construction builds on a no-side-information PIR scheme.

IV. W -PRIVACY PROBLEM

The converse begins by extracting structural consequences of W-privacy and decodability, then relates every valid PIR answer to an index-coding instance.

  • W-privacy implies that every message can serve as a possible demand with an associated M-message side-information set and decoding function.The condition holds for each message under a demand distribution assigning positive probability to every index.
  • Decodability supplies the decoding condition needed for the associated side-information sets.The paper explicitly separates this implication from the privacy-based condition.
  • These structural conditions enable a reduction from PIR with side information to an index-coding problem.The resulting index-coding instance is used in the converse argument.

A. Index Coding problem

The paper models index coding through clients, encoding, and decoding functions, and represents equal-demand side-information structures with a directed graph.

  • An index-coding instance has clients that each request one message while knowing a subset of the other messages.The client side-information sets are denoted X_Si and the requested message by X_f(i).
  • An index code consists of an encoding function and decoding functions that recover every requested message using the broadcast codeword and client side information.The code must decode correctly for all message assignments.
  • When each of K clients requests a distinct message, a directed graph records side information by placing an arc (i, j) when client i knows X_j.The out-neighbors of vertex i represent its known messages.
  • The broadcast rate is defined from the minimum encoding length as a function of message length.The paper denotes the minimum encoding length by β_t before defining the broadcast rate.

B. Converse for Theorem 1

The converse maps a W-private PIR answer to an index code whose graph has out-degree M, then lower-bounds its broadcast rate using an acyclic induced subgraph.

  • The answer of any W-private PIR scheme must solve an index-coding instance with K distinct-message clients and M-message side information for each client.The requested client uses the actual side-information set, while other clients receive arbitrary M-message sets.
  • The associated side-information graph has out-degree M at every vertex, allowing the index-coding lower bound to be applied.The graph representation follows from assigning each client’s side-information set to outgoing neighbors.
  • A greedy procedure repeatedly selects a vertex and removes it together with its out-neighbors, producing an acyclic induced subgraph.Ordering selected vertices by insertion ensures that the induced subgraph contains no directed cycle.
  • Because each removal eliminates at most M + 1 vertices, the procedure selects at least ⌈K/(M + 1)⌉ vertices.The selected set therefore yields the corresponding MAIS-based broadcast-rate lower bound.
  • The converse transfers the index-coding lower bound into a lower bound on the PIR answer length and hence the capacity.The proof states that the answer length is at least t times the relevant bound.

C. Achievability for Theorem 1

The Partition and Code scheme randomly partitions message indices, places the demand and side-information indices together according to the construction, and returns one inner product per partition set. The user decodes the demanded message by subtracting its known side-information contributions, while the scheme satisfies demand privacy.

  • Partition and Code PIR Scheme: The scheme partitions the K messages into g sets, with sets of size M+1 except possibly a final smaller set.For the divisible case, the demand and M side-information indices form one set, while the remaining indices are randomly partitioned.
  • Partition and Code PIR Scheme: The user selects a partition set according to its size and fills it with the demand index and side-information indices when applicable.The remaining sets are filled by uniformly choosing among unplaced message indices.
  • Partition and Code PIR Scheme: The server returns one inner product for each partition set, and the user recovers the demanded message by subtracting known side-information contributions.The partition is sent in a uniformly random order before the server computes the set-wise inner products.
  • Privacy and achievability: The construction is designed to satisfy W-privacy under the specified demand and side-information distributions.Its achievability is stated for one server, one demanded message, and side-information size M.
  • Rate: The Partition and Code scheme has a rate determined by the number of independently and uniformly distributed partition answers.The supplied passages state that the rate follows from the independent uniform distribution of the messages and answers.

V. (W, S)-PRIVACY PROBLEM

For (W, S)-privacy, the paper proves both converse and achievability results by reducing the PIR problem to index coding and using an MDS coding scheme.

  • V. (W, S)-PRIVACY PROBLEM: The (W, S)-privacy section reduces the converse to index coding and uses MDS coding for achievability.The reduction and coding scheme are presented as the proof techniques for Theorem 2.

A. Converse for Theorem 2

The converse for joint demand-and-side-information privacy maps every PIR answer to a constrained index-coding instance. A broadcast-rate lower bound then yields a capacity upper bound of (K − M)^−1.

  • Converse: The converse establishes a necessary privacy condition and a class of index-coding instances requiring at least K − M transmissions.The associated clients cover demands with side-information sets of size M, including the actual demand and side information.
  • Converse: For every demand and side-information pair, decodability and privacy imply decoding functions that make the PIR answer a feasible index code.The constructed instance includes a client for each relevant demand and side-information configuration.
  • Converse: The index-coding broadcast rate is at least K − M for instances satisfying the required conditions.This lower bound follows by comparing with an instance having K − M clients and independent messages.
  • Converse: The resulting capacity upper bound for the single-server (W, S)-PIR-SI problem is (K − M)^−1.The answer length is at least (K − M)t for any demand and side-information pair.

B. Achievability for Theorem 2

The achievability scheme uses a systematic MDS code to send K − M parity symbols while allowing recovery from the user’s M side-information messages. The resulting rate is (K − M)^−1 and the query-answer distribution is independent of the specific demand and side-information indices.

  • Achievability: The MDS scheme sends K − M parity symbols from a systematic (2K − M, K) MDS code over F2^t.The field size is chosen so that t ≥ log2(2K − M).
  • Achievability: The user can decode all remaining messages, including the demanded message, from the parity symbols and any M side-information messages.This is the MDS property used for decodability.
  • Achievability: The scheme achieves rate (K − M)^−1 while satisfying both decodability and (W, S)-privacy.The query and answer depend on the side-information size M but not on the particular demand or side-information indices.
  • Achievability: The K − M parity symbols are independent and uniformly distributed, supporting the stated answer entropy and rate calculation.Each parity symbol is a linear combination of independent uniformly distributed messages.

VI. W -PRIVACY FOR MULTIPLE SERVERS

The paper extends demand-private PIR with side information to multiple replicated servers by grouping messages into super-messages and applying the Sun–Jafar protocol. The resulting construction preserves demand privacy and can improve rate over downloading without side information.

  • Rate: A two-server example downloads 6 bits at rate 2/3, exceeding the 8/15 capacity obtained by ignoring one message of side information.The comparison uses the no-side-information multi-server PIR capacity for N = 2 and K = 4.
  • Rate: For N servers with (M + 1) dividing K, the construction achieves the Sun-Jafar rate for K/(M + 1) super-messages.The stated rate is (1 + 1/N + · · · + 1/N^(K/(M+1)−1))^−1.
  • Multi-Server W-PIR-SI Scheme: The scheme partitions messages into groups of M + 1, forms super-messages by summing each group, and applies the Sun-Jafar protocol to retrieve the demand-containing super-message.The demand and side-information messages form one group; the remaining messages are randomly partitioned into groups of size M + 1, and the partition is randomly permuted before querying the servers.
  • Privacy: Demand privacy follows because Sun-Jafar hides which super-message is requested, while random grouping leaves every message equally likely to be the demand within a super-message.The construction therefore protects the demand index even though the user decodes the desired message using its side information.

VII. CONCLUSION

The paper establishes PIR capacity results with prior side information for single-server privacy settings and extends the W-privacy scheme to replicated databases. Its multi-server construction combines the single-server idea with the Sun–Jafar protocol.

  • VII. CONCLUSION: The paper studies W-privacy and joint (W, S)-privacy when users possess a subset of database messages obtained from other sources.The side-information subset excludes the desired message and is unknown to the servers.
  • VII. CONCLUSION: For a single server, the paper establishes capacity for joint privacy under arbitrary demand and side-information distributions and for W-privacy under a uniform distribution.The conclusion distinguishes the two privacy requirements and their distributional assumptions.
  • VII. CONCLUSION: For multiple replicated servers, the paper extends its W-privacy scheme using ideas from the single-server construction and Sun–Jafar’s no-side-information protocol.The conclusion states that the resulting multi-server capacities are addressed in the paper’s extensions.
Loading 1709.00112v1…