2026-07-22T06:50:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24355 2025-12-12T14:53:38Z ddc:004 open_access

Information-Theoretic Random-Index PIR Kolby, Sebastian Roy, Lawrence Sternad, Jure Yakoubov, Sophia Private information retrieval Multi-server Lower bounds A Private Information Retrieval (PIR) protocol allows a client to learn the ith row of a database held by one or more servers, without revealing i to the servers. A Random-Index PIR (RPIR) protocol, introduced by Gentry et al. (TCC 2021), is a PIR protocol where, instead of being chosen by the client, i is random. This has applications in e.g. anonymous committee selection. Both PIR and RPIR protocols are interesting only if the communication complexity is smaller than the database size; otherwise, the trivial solution where the servers send the entire database suffices. Unlike PIR, where the client must send at least one message (to encode information about i), RPIR can be executed in a single round of server-to-client communication. In this paper, we study such one-round, information-theoretic RPIR protocols. The only known construction in this setting is SimpleMSRPIR (Gentry et al.), which requires the servers to communicate approximately N/2 bits, N being the database size. We show an Ω(√N) lower bound on communication complexity for one-round two-server information-theoretic RPIR, and a sublinear upper bound. Finally, we show how to use a sublinear amount of database-independent correlated randomness among multiple servers to get near-optimal online communication complexity (the size of one row plus the size of one index description per server). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Kolby and Lawrence Roy and Jure Sternad and Sophia Yakoubov 2025 Is Part Of LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2025.5 urn:nbn:de:0030-drops-243559 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode