Querying Twice: How to Ensure We Obtain the Correct File in a Private Information Retrieval Protocol

Jan 15, 2025

Abstract

Private Information Retrieval (PIR) is a cryptographic primitive that enables aclient to retrieve a record from a database hosted by one or more untrustedservers without revealing which record was accessed. It has a wide range ofapplications, including private web search, private DNS, lightweightcryptocurrency clients, and more. While many existing PIR protocols assume thatservers are honest but curious, we explore the scenario where dishonest serversprovide incorrect answers to mislead clients into retrieving the wrong results.

We begin by presenting a unified classification of protocols that addressincorrect server behavior, focusing on the lowest level ofresistance—verifiability—which allows the client to detect if the retrievedfile is incorrect. Despite this relaxed security notion, verifiability issufficient for several practical applications, such as private media browsing.

Later on, we propose a unified framework for polynomial PIR protocols,encompassing various existing protocols that optimize download rate or totalcommunication cost. We introduce a method to transform a polynomial PIR into averifiable one without increasing the number of servers. This is achieved bydoubling the queries and linking the responses using a secret parameter held bythe client.