2025/11/29 by Zhang, Liang Feng
#11T71 #Cryptography and Security (cs.CR) #E.4 #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2512.00480
Retrieving up-to-date information from a publicly accessible database poses significant threats to the user's privacy. \em 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 \em 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 \em communication complexity. In this review, we introduce a new discrete structure called \em 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.