Plinko PIR Tutorial
15 days ago
- #database
- #privacy
- #cryptography
- Private Information Retrieval (PIR) allows clients to query a database without revealing what they are reading.
- Plinko is a PIR protocol that reduces communication and server-side compute overhead from O(N) to O(√N).
- Classic two-server PIR involves XOR operations on subsets of data, requiring trust in at least one server.
- Plinko uses a setup phase where clients generate hints and a query phase that leverages invertible PRFs for efficiency.
- Backup hints in Plinko ensure privacy by preventing hint reuse and allowing updates to the dataset.
- Concrete efficiency examples show Plinko's application in large datasets like Ethereum's state tree.
- TreePIR is an alternative to Plinko, using puncturable PRFs for logarithmic communication complexity.
- Lower bounds for PIR protocols suggest potential for further optimization, especially in server-side computation.