Private Information Retrieval (PIR) with Alex Hoover

Private Information Retrieval, or PIR, protects which entry a client retrieves from a public database rather than the contents of that entry. It is distinct from encryption and authentication primitives and was introduced in 1995. Since then, variants have emerged targeting efficiency or specialized features, including keyword PIR, batch PIR, and symmetric PIR. Alex Hoover argues PIR is on the cusp of being practically efficient for real-world applications, particularly in blockchain contexts where light clients querying Ethereum state must otherwise reveal their queries to a server, creating both privacy and censorship risks. PIR addresses read privacy and complements ZK proofs, which provide write privacy, and combining the two to authenticate retrieved data is an active research area.

The original 1995 formulation is information-theoretically secure and requires the database to be replicated across multiple non-colluding servers. Each server's view is secure even against unbounded computation, but the non-collusion assumption is a critical weakness: in many schemes, two colluding servers immediately learn the query. It is mathematically impossible to achieve non-trivial information-theoretic PIR in the single-server setting. Single-server computational PIR requires at least public-key-type operations and cannot be built from one-way functions alone. A recent result showed that traditional single-server PIR requires public-key operations linear in database size.

Offline-online PIR, developed concurrently in a 2018 Google paper and by Corrigan-Gibbs and Kogan at Eurocrypt 2020, addresses this by moving expensive work to an offline phase so the online phase requires only XOR operations and no public-key operations. In client-side preprocessing PIR, the client streams the entire database offline and stores roughly square-root-n hints, each a set paired with the XOR of its entries. Online, the client finds a hint containing the desired index, sends the remaining set to the server, and XORs two parities so all entries cancel except the one of interest. This reduces server computation and amortized communication per query from linear-n to square-root-n. Hints must eventually be refreshed by re-downloading the database, but this cost is amortized over many queries.

A security issue arises because sending a subset without index i can allow the server to infer i is not among the sent indices. Corrigan-Gibbs and Kogan addressed this by sometimes including i in the sent subset with a probability that makes the distribution indistinguishable, accepting occasional wrong answers and using a majority vote over roughly ten repetitions. Most modern schemes fix this differently by structuring hints so the issue does not arise. Storing sets directly would require n bits of client storage, so schemes like Piano and the Lingren-Moogies-Sun paper compress hints using a pseudo-random function key per hint, allowing the client to store one key and derive offsets on demand. The Lingren-Moogies-Sun paper achieved better concrete efficiency and reduced server response size compared to Piano.

Plinko, Hoover's paper building on Piano and Lingren-Moogies-Sun, introduces an invertible pseudo-random function to replace the linear hint scan with a faster asymptotic lookup. An invertible PRF lets the keyholder find an input matching a given output, a property acceptable for the client holding the key but not for outside parties. Plinko uses one PRF key per chunk shared across all hints rather than one key per hint, enabling fast search over the entire hint collection. Storing more hints, up to n-to-the-two-thirds, reduces server query time and response size to n-to-the-one-third, compared to the default square-root-n. Plinko's speedup is asymptotic rather than black-box and requires scheme-specific adaptation.

Keyword PIR treats the database as a dictionary mapping keywords to values, analogous to private DNS lookups. General transformations from point PIR to keyword PIR commonly use cuckoo hashing, though building client-side preprocessing specifically for keyword PIR remains an open research question. Batch PIR is well-suited to private Merkle proof generation, where the querier already knows all needed indices, specifically the log-depth intermediate nodes used in identity and private transfer proofs placed inside SNARKs. Roughly a thousand queries can be batched with server computation increasing by only a factor of two or three rather than a factor of a thousand.

Doubly efficient PIR, which achieves sub-linear communication and computation online after a one-time server preprocessing phase, was shown in 2023 by Lin, Mooks, and Wix to be buildable from ring LWE with polylogarithmic online query time, but server encoding size blows up to roughly terabytes for a gigabyte-sized database, making it far from practical. Signal chose not to use PIR for private contact discovery due to efficiency constraints and instead used ORAM combined with a secure enclave. Apple uses PIR for a caller ID application, and Google uses PIR as a sub-protocol of private set membership to check for reused passwords without revealing the password to Google. Hoover predicts that as PIR becomes more efficient it will appear in many more applications beyond these current niche deployments.