Source-linked AI summary
The Capacity of Symmetric Private Information Retrieval
Hua Sun, Syed A. Jafar
TL;DR
The paper asks how efficiently a user can retrieve one replicated message while hiding both the requested index from each database and all undesired messages from the user. It characterizes SPIR capacity and its dependence on database-shared randomness, extending the results to capacity regions and finite message lengths. The capacity is 1 − 1/N when common randomness is at least 1/(N−1) bits per desired message bit, and SPIR is infeasible below that threshold.
Problem
SPIR must protect the requested message index from each database while preventing the user from learning any undesired messages.
Method
The paper characterizes SPIR capacity as a function of the number of databases, messages, and database-shared common randomness, with extensions to capacity regions and finite message lengths.
Results
The capacity is 1 − 1/N for K messages and N databases, while common randomness below 1/(N−1) makes SPIR infeasible and at least that amount suffices for capacity.
Takeaways & Limitations
The minimum common randomness needed for any positive SPIR rate is already sufficient to achieve the maximum capacity.
Takeaways & Limitations
The stated main capacity theorem restricts the setting to K ≥ 2 messages and N ≥ 2 databases; cases with K = 1 or N = 1 are trivial.
Abstract
from arXiv · showhide
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. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other $K-1$ messages. The information theoretic capacity of SPIR (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. We show that the capacity of SPIR is $1-1/N$ regardless of the number of messages $K$, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least $1/(N-1)$ bits per desired message bit, and zero otherwise. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.
1 Introduction
The paper distinguishes PIR, which protects the user’s request, from SPIR, which also protects undesired messages from the user. It characterizes SPIR’s efficiency and connects the problem to cryptography, coding theory, and complexity theory.
- PIR: PIR retrieves a desired message from replicated databases without revealing its index to any individual database.Its capacity is the maximum desired information privately downloaded per downloaded bit, given by (1 + 1/N + · · · + 1/N^(K−1))^−1 for K messages and N databases.
- SPIR: SPIR adds database privacy, requiring the user to learn nothing beyond the chosen message.Thus, downloading all messages is no longer acceptable, because it reveals undesired messages.
- Contributions: For K messages and N databases, the paper characterizes SPIR capacity as 1 − 1/N.The work also extends the characterization to the capacity region and finite message lengths.
- Significance: SPIR inherits connections to oblivious transfer, cryptography, coding theory, and complexity theory.In particular, SPIR is described as a distributed form of oblivious transfer, where the receiver obtains only the desired message.
2 Problem Statement
The SPIR model uses replicated messages, private user randomness, database-shared randomness, and queries and answers that enable decoding while enforcing user and database privacy.
- Model: N databases each store all K messages, modeled as independent random variables over a finite field.The messages have entropies determined by their lengths and are jointly independent.
- Queries: The user privately chooses an index θ and generates queries for retrieving Wθ.The queries are generated using private randomness unavailable to the databases.
- Queries and answers: Each database computes an answer from its query, all messages, and common randomness, then returns that answer to the user.The user decodes the desired message from the collected queries, answers, and field information.
- Privacy constraints: User privacy requires each database to see identically distributed query strategies for every desired message index.Database privacy separately requires the undesired messages to be independent of the user’s available information.
- Rate: The SPIR rate is desired information retrieved per downloaded symbol, with total download cost D defined across all databases.Achievable rates require vanishing decoding error as message length grows, and the capacity region is the closure of achievable rate tuples.
3 Results
For K≥2 messages and N≥2 databases, SPIR has a threshold dependence on common randomness and capacity 1−1/N once feasible. The paper also characterizes unequal-message and finite-length extensions, including exact-zero-error and integer-download effects.
- 3.1 Capacity of SPIR: ρ < 1/(N−1) makes SPIR infeasible, whereas ρ ≥ 1/(N−1) immediately achieves the maximum capacity.The minimum common randomness needed for any positive rate is already sufficient for capacity.
- 3.1 Capacity of SPIR: The capacity of SPIR is independent of the number of messages K.This statement applies to the K≥2, N≥2 setting of the capacity theorem.
- 3.1 Capacity of SPIR: SPIR capacity is strictly below PIR capacity for finite K, but the gap vanishes as K approaches infinity.The additional database-privacy requirement creates the finite-K penalty.
- 3.2 Capacity Region of SPIR: For unequal message sizes, the capacity region bounds each Rk by lk/max_i li, with the normalized minimum download cost equal across messages.The capacity region is zero otherwise, and the normalized common randomness is measured relative to the largest message.
- 3.3 Capacity of Finite Length SPIR: Finite-length SPIR is formulated for arbitrary L with zero error; capacity-achieving schemes use message blocks of N−1 symbols, while other lengths incur a ceiling penalty.The converse also holds for arbitrary message size under exactly zero error, and the finite-length theorem covers K≥2 and N≥2.
4.1 Proof of Theorem 1
The proof constructs an exact, private SPIR scheme at the threshold common-randomness ratio, achieving rate 1 − 1/N. Random queries hide the desired index, while shared randomness enables database privacy and decoding.
- Achievability: The scheme uses messages of N − 1 bits, one shared random bit, and one-bit answering strings from each database.The common randomness is independent of the messages and has ratio ρ = 1/(N −1).
- User privacy: Random query vectors are generated independently of the desired index, so each database learns nothing about which message is requested.The queries use uniformly random binary coefficients, with the desired message encoded through a database-specific coefficient change.
- Answer construction: Each database forms a linear combination of message bits and adds the common random variable to its answer.The shared random bit masks information about undesired messages while preserving the structure needed for decoding.
- Correctness: The user subtracts paired answers to recover every desired message bit, satisfying correctness.The decoding obtains x_k,i for i ∈ [1 : N −1].
- Rate and randomness: The achieved rate is (N −1)/N = 1 −1/N, exactly matching capacity while using the minimum randomness threshold.The construction has zero error for the stated message length.
Lemma 1
Lemma 1 begins the converse analysis by deriving entropy relations for answers under the privacy constraints.
- Proof: The proof derives the lemma from the user-privacy constraint applied across all messages and databases.The supplied passage introduces the relevant mutual-information condition but truncates the displayed derivation.
- Proof: Combining the preceding entropy relations yields the lemma’s stated bound.The supplied text does not include the complete bound or its interpretation.
Lemma 2
Lemma 2 supports the converse by combining database privacy, decodability, and answer-entropy inequalities to constrain feasible SPIR schemes.
- Database privacy: Database privacy requires that undesired messages reveal no information through the answers, queries, and shared randomness.The proof applies this condition for every undesired message index and database.
- Rate converse: The converse considers any feasible SPIR scheme and proves that its rate cannot exceed C_SPIR.This establishes the rate upper bound used in the theorem.
- Entropy analysis: The converse analyzes answering strings from which the desired message can be decoded, then bounds their entropy using the privacy constraints.The derivation invokes the answering strings, the desired message, and common randomness.
- Randomness converse: Any feasible nonzero-rate SPIR scheme requires common randomness at least 1/(N −1) times the message size.Thus the randomness threshold is necessary, not merely sufficient.
4.2 Proof for Theorem 2
The capacity-region proof constructs rates for unequal message sizes by concatenating independent SPIR schemes, then proves matching converse bounds.
- Achievability: For unequal message lengths, the construction achieves rate (1 −1/N)l_k/l_K for message W_k at ρ = 1/(N −1).Messages are ordered so l_1 ≤ l_2 ≤ ··· ≤ l_K, and the largest message length normalizes the region.
- Achievability: Each message is divided into sub-messages, and independent copies of the basic SPIR scheme are applied according to successive length differences.The construction sets L = N −1 and uses zero vectors for sub-messages beyond the relevant index.
- Achievability: Concatenating independent correct and private schemes preserves overall correctness and privacy.The proof treats the concatenated construction as a composition of valid SPIR schemes.
- Achievability: The resulting rates and common-randomness usage establish achievability of Theorem 2.The construction’s final parameters are summarized after concatenation.
4.3 Proof for Theorem 3
The finite-length SPIR construction decomposes the message into full blocks and a remainder, combining capacity-achieving schemes to obtain an integer download cost and common-randomness requirement.
- Achievability: L = G1(N − 1) + L1 partitions the message into G1 full blocks and a remainder of L1 bits.Here G1 = floor(L/(N − 1)) and L1 ∈ [0 : N − 2].
- Achievability: The construction uses the N-database scheme G1 times, then uses L1 + 1 databases for a nonzero remainder.The remainder scheme has rate 1 − 1/(L1 + 1) and common-randomness ratio 1/L1.
- Rate optimality: The achieved download cost is D = G1N + L1 + 1, matching the finite-length rate expression L/⌈L/(1 − 1/N)⌉.When L1 = 0, L is an integer multiple of N − 1 and the match follows directly.
- Converse: Every finite-length SPIR scheme satisfies D ≥ ⌈L/(1 − 1/N)⌉ ≥ L/(1 − 1/N), using the converse bound and integer-valued downloads.The zero-error setting and same-field symbol downloads make D an integer.
- Common randomness: The common randomness amount ρL is integer-valued and must satisfy ρL ≥ ⌈L/(N − 1)⌉.This is the finite-length common-randomness lower bound for unit message-symbol size.
5 Conclusion
SPIR has capacity 1 − 1/N, with common randomness both necessary and sufficient at 1/(N − 1) bits per message bit; the results extend to unequal and finite-length messages.
- 1 − 1/N is the capacity of SPIR for K messages and N databases.
- 1/(N − 1) bits of common randomness per message bit is necessary for any positive SPIR rate and sufficient for capacity.
- The paper extends these insights to unequal message sizes and finite-length messages.