Plinko PIR Tutorial

Summary

Plinko PIR tutorial 2025 Nov 25 See all posts Plinko PIR tutorial Special thanks to Alex Hoover, Keewoo Lee and Ali for feedback and review One underrated form of privacy, that is not well satisfied by ZK-SNARKs, traditional versions of FHE or other commonly talked about methods, is private reads. Users want to learn things from a large database, without revealing what they're reading. Some use cases of this include: Privacy-preserving Wikipedia (so you can learn things without even the server knowing what you're reading) Privacy-preserving RAG or LLM search (so your local LLM can get data from the internet without revealing what you're querying) Blockchain data reads (so you can use a dapp that queries an external RPC node without the node learning what you're querying; see "private reads" here) There is a category of privacy protocols that are directly designed to solve this problem, called private information retrieval (PIR). A server has a database \(D\). A client has an index \(i\). The client sends the server a query, the server replies back with an answer that allows the client to reconstruct \(D[i]\), all without the server learning anything about \(i\). In this post I will describe some basics that underlies all PIR protocols, and then describe Plinko, a protocol that efficiently achieves this. Basics of PIR To understand more complicated PIR protocols, it's best to start with "classic two-server PIR". Classic two-server PIR assumes that a client is making queries to two servers, and it trusts that at least one of the two is honest. Here's how the protocol works: The client wants to know \(D[i]\), in the above example \(D[8]\). The client generates a random subset of indices in \(D\), on average about half full (in the above example, \([1, 5, 6, 10, 15]\)). The client sends that subset to one server, and then sends a modified subset, where the membership of \(D[i]\) is flipped (ie. added if it was not there, removed if it was there), to the other server. Ea...