Paper 2026/1651

Single-Server Verifiable PIR with Updates and Universally Composable Security

Abstract

Private information retrieval (PIR) is a fundamental cryptographic primitive that allows a client to retrieve an entry of a database from a server without revealing which entry was retrieved. PIR security is traditionally defined with a distinguishing game that ensures the clients' access patterns are kept private from a semi-honest server. Verifiable PIR (VPIR) adds another game-based property that holds against a malicious server: the server is bound to a particular database and cannot cause a client to retrieve a database entry that is inconsistent with this database. Recent work by Alon and Beimel [ITC 2025] deviated from the traditional game-based PIR definitions and contributed a definition of standalone simulation-based security for multi-server PIR. Their techniques, however, do not readily extend to single-server VPIR and do not consider concurrent protocol composition when PIR is used as a building block within a larger application. In this work, we further the study of simulation-based VPIR security. We are the first to formalize a universally composable (UC) definition of VPIR in the single-server setting by giving an ideal VPIR functionality. We motivate the need for UC security by showing how game-based VPIR properties fail under sequential and concurrent protocol composition. We also demonstrate the generality of our UC VPIR functionality by providing two realizations based on a trivial PIR and VeriSimplePIR [de Castro and Lee, USENIX Security 2024]. Additionally, we introduce a new kind of VPIR, called Updatable VPIR (UVPIR), which guarantees to clients that (1) database updates are authorized by permissioned clients and (2) responses to their queries are consistent with a specific version of the PIR database. We show that UVPIR can be constructed in a black-box manner on top of any VPIR protocol.