A Unified Framework for Constructing Information-Theoretic Private Information Retrieval
Liang Feng Zhang · 2025
Read A Unified Framework for Constructing Information-Theoretic Private Information Retrieval by Liang Feng Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00480.txt.
Introduction
Fetching a record from a public database can reveal exactly what you were looking for. Liang Feng Zhang presents a unified framework for information-theoretic private information retrieval in 2025. These protocols let a user retrieve any entry without revealing which entry it was.
Private retrieval protects readers of sensitive material, from medical guidance to legal records, against profiling by servers. A unified construction aims to organize many known protocols under one design logic. Such frameworks help engineers choose protocols with proven privacy rather than ad hoc promises, as these tools move from theory into real services. Information-theoretic privacy means security that holds even against unlimited computing power.
Catalog record
| CREATOR | Liang Feng Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-00480
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Unified Framework for Constructing Information-Theoretic Private Information Retrieval Liang Feng Zhang Abstract Retrieving up-to-date information from a publicly accessible database poses significant threats to the user’s privacy. Private information retrieval (PIR) protocols allow a user to retrieve any entry from a database, without revealing the identity of the entry being retrieved to the server(s). Such protocols have found numerous applications in both theoretical studies and real-life scenarios. The existing PIR constructions mainly give multi-server information-theoretic PIR (IT-PIR) protocols or single-server computational PIR (CPIR) protocols. Compared with CPIR, IT-PIR protocols are computationally more efficient and secure in the presence of unbounded servers. The most classical and challenging problem in the realm of IT-PIR is constructing protocols with lower communication complexity . In this review, we introduce a new discrete structure called families of orthogonal arrays with span capability (FOASC) and propose a unified framework for constructing IT-PIR protocols. We show how the most influential IT-PIR protocols in the literature can be captured by the framework. We also put forward several interesting open problems concerning FOASC, whose solutions may result in innovative IT-PIR protocols. Keywords: private information retrieval; families of orthogonal arrays with span capability 1 Introduction Publicly accessible databases are indispensable resources for retrieving up-to-date information. Access to such databases poses significant risks to the privacy of the user, since the database server(s) may monitor the user’s queries and infer what the user is after. Usually the user’s retrieval intent is highly valuable and needs careful protection. For example, for a stock-market database an investor’s retrieval intent may influence the stock’s price; for a patent database a company’s retrieval intent may attract unexpected pursuer of the patent; for a Merkle proof database on which a blockchain system such as Ethereum is based, a user’s retrieval intent may link the user to the account being read and eventually lead to deanonymization. Private information retrieval (PIR) protocols [ 1 ] are cryptographic protocols that are specifically designed to ensure the users’ privacy. Such protocols allow a user to retrieve an entry x_{i} from a database {\bm{x}}=x_{1}\cdots x_{n}\in\{0,1\}^{n} , without revealing the retrieval index i\in[n] to the server. At first glance, the requirements posed by PIR seem quite absurd. However, there does exist a trivial solution that perfectly hides i from the server, where the user simply downloads the entire database {\bm{x}} from the server and then locally extracts x_{i} . In particular, the perfect privacy is information-theoretic and means that the server learns absolutely no information about i , even if it has unlimited computing power. This trivial solution incurs a communication cost of O(n) , which could be prohibitive if the database consists of millions or billions of entries. Unfortunately, in their pioneer work [ 1 ] , Chor, Goldreich, Kushilevitz and Sudan showed that the O(n) communication cost of the trivial solution is asymptotically optimal, if there is only one server and perfect privacy is needed. Therefore, to have a PIR solution of communication cost o(n) , the user must consider two possible relaxations: (1) resort to multiple servers; (2) give up the perfect privacy. Two flavors of PIR. Under the first relaxation, the user may communicate with k\penalty\ (k>1) servers, send a query to every server, receive an answer from the server, and finally reconstruct x_{i} from the k answers. Specifically, each of the servers should store a copy of the same database \bm{x} and answer the user’s query with \bm{x} . To differentiate from single-server solutions, the k servers must not collude with each other. If the user’s retrieval index i is perfectly (i.e., information-theoretically) hidden from the collusion of any t\penalty\ (t<k) out of the k servers, then the protocol is said to be a t - private k -server information-theoretic PIR (IT-PIR) [ 1 ] , or (t,k) -PIR for short. Under the second relaxation, the user may properly encode its retrieval index i as a query, which essentially leaks no information about i to any computationally bounded server that runs polynomial-time algorithms, such that the server remains able to compute an encoded form of x_{i} to the user. In particular, the privacy of i must be built on various number-theoretic problems (e.g., the quadratic residuosity problem, the composite residuosity problem), which are hard to solve in feasible time by the computationally bounded server. Protocols in this category have been called single-server computational PIR [ 2 ] , or CPIR for short. Practical influence of PIR. Both CPIR and IT-PIR are important cryptographic primitives that have practical influences. Today PIR protocols have found numerous applications in real-life scenarios, e.g., private database search [ 3 ] , metadata hiding messaging [ 4 , 5 ] , private media consumption [ 6 ] , private contact discovery [ 7 ] , private blocklist lookups [ 8 ] , privacy-friendly advertising [ 9 , 10 ] , certificate transparency [ 11 ] , private web search [ 12 ] , private electronic commerce [ 13 ] , and private location based services [ 14 ] , among others. Recently, commercial systems such as Microsoft’s Password Monitor [ 15 ] , Google’s Device Enrollment [ 16 ] , Blyss’s Spiral [ 17 ] , and Brave’s FrodoPIR [ 18 ] have integrated the functionality of PIR and signed the real world deployment of PIR. Theoretical influence of PIR. On the theoretical side, both IT-PIR and CPIR are fundamental building blocks of many other cryptographic primitives and have their featured applications. IT-PIR protocols may give locally decodable codes (LDCs) [ 19 , 20 , 21 ] , error-correcting codes that can recover any bit of the message by reading a few bits of the codeword and guarantee correct recovery even if a constant fraction of the codeword have been adversarially corrupted. IT-PIR protocols can also be used to construct multi-party information-theoretically private protocols [ 22 , 23 ] . CPIR protocols imply many important cryptographic primitives such as unconditionally hiding commitment [ 24 ] , oblivious transfer [ 25 , 26 ] , collision-resistant hash functions [ 27 ] , and efficient zero-knowledge arguments [ 28 ] . Communication cost. The efficiency of PIR protocols is mainly measured by communication complexity [ 1 ] , the total number of bits that have to be exchanged between the user and the server(s) in order to retrieve one bit from the database. The most classical and challenging problem in the realm of PIR is constructing protocols with lower communication complexity for a given number of servers. While there are O(\log n) -server PIR protocols with polylogrithmic (in n ) communication complexity, the main focus has been protocols that use a constant number of servers. For IT-PIR, after a long line of arduous explorations [ 1 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 ] , today the most efficient protocols that use a constant number of servers have reached a communication complexity that is subpolynomial in n . For CPIR, protocols [ 2 , 43 , 44 , 45 , 46 , 47 , 48 , 49 , 50 , 51 , 52