Source-linked AI summary
Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost
Chao Tian, Hua Sun, Jun Chen
TL;DR
PIR asks how to retrieve a message without revealing its identity to any server, while keeping communication efficient. This paper constructs an asymmetric capacity-achieving code and analyzes capacity converses and PIR symmetries. The code attains optimal message size and upload cost within the stated classes, including capacity-achieving linear codes.
Problem
Earlier capacity-achieving PIR constructions generally assume message lengths can grow without bound, whereas shorter messages and small query sets matter for versatility and implementation cost.
Source: §1 · p. 2Method
The paper constructs an asymmetric capacity-achieving code, derives converse bounds from critical properties of the capacity proof, and analyzes symmetries that can produce symmetric codes.
Source: §1 · p. 2Results
The code uses N−1-bit messages and an upload cost of N(K−1) log2 N bits, matching converse bounds within the considered classes, including capacity-achieving linear codes.
Source: §1 · p. 2Takeaways & Limitations
The symmetry analysis provides a bridge from the proposed asymmetric code to more symmetric PIR codes.
Source: §1 · p. 2The work focuses on the canonical PIR setting; extending the construction to settings such as MDS-coded databases is left for future work.
Source: §6 · p. 21
Abstract
from arXiv · showhide
We propose a new capacity-achieving code for the private information retrieval (PIR) problem, and show that it has the minimum message size (being one less than the number of servers) and the minimum upload cost (being roughly linear in the number of messages) among a general class of capacity-achieving codes, and in particular, among all capacity-achieving linear codes. Different from existing code constructions, the proposed code is asymmetric, and this asymmetry appears to be the key factor leading to the optimal message size and the optimal upload cost. The converse results on the message size and the upload cost are obtained by a strategic analysis of the information theoretic proof of the PIR capacity, from which a set of critical properties of any capacity-achieving code in the code class of interest is extracted. The symmetry structure of the PIR problem is then analyzed, which allows us to construct symmetric codes from asymmetric ones, yielding a meaningful bridge between the proposed code and existing ones in the literature.
1 Introduction
PIR seeks to retrieve a message without revealing its identity to any server, and capacity measures the maximum retrieval rate. The introduction motivates capacity-achieving codes that also reduce message size and upload cost.
1 Introduction
- Earlier capacity-focused constructions generally assume message length can grow without bound, while shorter messages can improve versatility and reduce implementation constraints.Small query sets also reduce upload and the functions servers need to compute.Source: §1 · p. 2
- The proposed capacity-achieving code uses N−1-bit messages and an upload cost of N(K−1) log2 N bits.Its alphabet can be any finite group or field, including the binary field, which yields a binary linear code.Source: §1 · p. 2
- Converse bounds match the proposed code’s message size and upload cost, establishing optimality within the stated code classes, including capacity-achieving linear codes.The bounds follow from critical properties identified by analyzing the PIR-capacity converse for decomposable codes on abelian groups.Source: §1 · p. 2
- The paper analyzes server-index, file-index, and answer symmetry, then uses these relations to build more symmetric PIR codes from asymmetric codes.The authors describe this as a bridge between their construction and existing code constructions.Source: §1 · p. 2
- At the extreme point where download cost is minimized, the work claims to precisely determine the relation among message size, upload cost, and download cost.The introduction contrasts this with order-wise bounds studied in the small, fixed-message-length formulation.Source: §1 · p. 3
2 Model and Preliminaries
The section formalizes the PIR model and code classes, then states the performance measures and the proposed construction’s optimality within specified capacity-achieving classes.
2 Model and Preliminaries
- The paper indexes from 0 rather than 1, simplifying the new construction’s notation without changing the problem or solution.Source: §2 · p. 3
2.1 System Model
- The user sends one query per server and reconstructs the requested message from the answers, while each server’s query distribution is identical across requested messages.Messages are independent and uniform, and answer vectors may have variable length.Source: §2.1 · p. 3
2.2 Two General Code Classes
- Decomposable codes express answers as sums of per-message functions over finite abelian groups; uniformly decomposable codes preserve uniformity unless the induced variable is deterministic.The class includes linear codes and some nonlinear codes; the paper’s information-theoretic converse framework applies beyond linear codes.Source: §2.2 · pp. 5–6
2.3 Performance Metrics
- Smaller message size supports more versatile designs, while lower upload cost reduces user-to-server communication and can simplify server functions.Retrieval rate measures desired message information per downloaded bit.Source: §2.3 · pp. 6–7
- The construction achieves PIR capacity and is optimal in message size among capacity-achieving uniformly decomposable codes and in upload cost among capacity-achieving decomposable codes.Source: §2.3 · p. 7
3 A New Capacity-Achieving PIR Code
The section presents the N-ary-indexed PIR code and its capacity and optimal-cost guarantees, then illustrates the construction with small parameter examples.
3.1 A Motivating Example (N, K) = (2, 2)
- For (N,K)=(2,2), the new code uses one symbol per message and has expected download cost 1.5 symbols and retrieval rate 2/3; the code in uses four symbols per message.The new code allows answer lengths to vary across queries, unlike the construction in.Source: §3.1 · pp. 7–8
3.2 The New PIR Code
- Queries are length-K vectors over {0,...,N−1}, partitioned among servers by their coordinate sum modulo N; each message prepends a dummy zero to its payload.The query set for server n consists of vectors whose entries sum to n modulo N.Source: §3.2 · p. 8
- The N-ary-indexed code is correct, private, and capacity-achieving, with minimum message size N−1 among capacity-achieving uniformly decomposable codes and minimum upload cost N(K−1)log2N among capacity-achieving decomposable codes.These guarantees are stated in Theorem 1.Source: §3.2 · p. 10
3.3 An Example for (N, K) = (3, 3)
- For (N,K)=(3,3), the example recovers the requested message and is private, and its retrieval rate matches capacity.With F=(0,2) and W1 requested, the answers permit recovery of b1 and b2.Source: §3.3 · pp. 10–11
4 Lower Bounding the Message Size and the Upload Cost
The section derives lower bounds by analyzing conditions forced by capacity-achieving decomposable codes, establishing matching floors for message size and upload cost.
4.1 Properties of Capacity-Achieving Decomposable Codes
- Any capacity-achieving decomposable PIR code must satisfy P1–P3: independence of retrieved data, deterministic dependence among residuals, and independence of requested-message signals.The properties follow from equality conditions in the capacity converse.Source: §4.1 · pp. 12–13
4.2 Minimum Message Size
- Any uniformly decomposable capacity-achieving code requires message size at least (N−1)log2|Y|, and therefore at least N−1; the same floor applies to standard finite-field linear codes.The stated bound depends on the coded-symbol alphabet Y, not the message alphabet X.Source: §4.2 · p. 13
4.3 Minimum Upload Cost
- Any capacity-achieving decomposable PIR code requires total upload cost of at least N(K−1)log N, or at least (K−1)log N at each server.The per-server lower bound is established in the proof of Theorem 4.Source: §4.3 · pp. 14, 16
5 Symmetry and Symmetrized Codes
The section analyzes server, message, and answer-variety symmetries, then uses space-sharing to construct more symmetric codes from asymmetric ones. These symmetrizations preserve retrieval rate but can increase message size and upload cost.
5.1 Server-symmetry
- Space-sharing over server permutations equalizes upload costs and expected retrieval rates across servers, though not necessarily for each query combination.Achieving query-by-query invariance requires variety-symmetry.Source: §5.1 · p. 18
5.2 Message-symmetry
- Space-sharing over message permutations preserves correctness and privacy but yields subset-entropy invariants, not explicit symmetry in individual coding rates, query distributions, or answer varieties.The construction applies permuted base-code strategies across message blocks.Source: §5.2 · p. 19
5.3 Variety-symmetry
- Variety-symmetry makes answer varieties equally long at each server and permits uniform requests among varieties without reducing retrieval rate.It is constructed by using a permutation of the base code’s random-key values across message blocks.Source: §5 · p. 17, §5.3 · p. 20
5.4 Applying the Symmetrization Techniques
- Variety-symmetrizing the proposed code increases message size to N^(K−1)(N−1), slightly above N^(K−1), the minimum when every query combination retrieves the same total symbols.For (N, K) = (2, 2), the resulting code has equal answer lengths at each server; all three symmetrizations can preserve retrieval rate at the expense of message size and upload cost.Source: §5.4 · pp. 20–21
6 Conclusion
The paper concludes that its capacity-achieving PIR code has optimal message size and upload cost, and identifies asymmetry as the apparent key to those reductions. The analysis focuses on the canonical PIR setting, with extension to MDS-coded databases deferred.
6 Conclusion
- The proposed capacity-achieving PIR code has optimal message size and upload cost, with asymmetry appearing to be the key to both reductions.The paper derives converse bounds by extracting critical structures from the PIR-capacity converse proof.Source: §6 · p. 21
- The analyzed symmetry structure can be used to symmetrize any PIR code into a symmetric version.The conclusion presents the symmetry analysis as an independent contribution.Source: §6 · p. 21
- The work focuses on the canonical PIR setting; extension of the asymmetric construction to MDS-coded databases is left for future work.Source: §6 · p. 21
A Proof of Technical Lemmas
The technical proofs derive necessary conditions for decomposable capacity-achieving codes by tracking equality in the information inequalities used in the capacity argument.
A Proof of Technical Lemmas
- Equality in the capacity-proof inequalities yields independence condition P1 across requested messages and query sets of nonzero probability.The proof uses correctness, answer determinism, and the retrieval-rate definition, then applies message permutations to extend the condition to every requested message.Source: A Proof of Technical Lemmas · p. 22
- Equality conditions in the information inequalities also imply deterministic property P2 for decomposable codes.The proof uses the ability to subtract message components in the abelian group and vary the message permutation.Source: A Proof of Technical Lemmas · pp. 23–24
- Equality in the final inequality chain establishes independence property P3 for decomposable codes.The argument allows any requested-message index and any order of summation.Source: A Proof of Technical Lemmas · p. 24