Cohort: Decentralized PIR

Abstract

Private Information Retrieval (PIR) underpins privacy-preserving applications such as private content delivery, contact discovery, and anonymous advertising, where users need to discreetly query a database. However, PIR usually relies on expensive fully homomorphic encryption and scales poorly with the database size, making it difficult to deploy at scale. As a result, most PIR-based systems are expected to have a single provider, or a few, bearing the operational costs of running a limited number of servers. Such deployments are susceptible to provider takedowns, churn, DoS, and censorship, making availability fragile. We present Cohort, a decentralized PIR protocol that distributes the database across multiple servers, eliminating vulnerabilities stemming from the provider bottleneck and sharing operational costs across many parties. Cohort integrates error correction directly into the BGV homomorphic encryption scheme, enabling clients to partition encrypted queries and read correct data even when up to 25% of servers return adversarial responses. Cohort also enables clients to generate publicly verifiable proofs of misbehavior without compromising query privacy, allowing the system to evict malicious servers. We implement Cohort in Go and show that asymptotic performance scales similarly to centralized PIR schemes with the database size, and the load on each Cohort server reduces proportionally to the number of servers in the system. Concretely, we measure that retrieving 16 KB from a 2 GB database takes under 170 ms. We demonstrate that this performance is sufficient to support a private news radio streaming service, illustrating that Cohort is practical for latency-sensitive applications.