One (Block) Size Fits All: PIR and SPIR with Variable-Length Records via Multi-Block Queries
Download: Paper (PDF)
Date: 23 Apr 2013
Document Type: Presentations
Additional Documents: Slides
Associated Event: NDSS Symposium 2013
We propose a communication-efficient method for users to fetch multiple blocks in Goldberg’s information-theoretic private information retrieval (PIR) scheme. Our approach trades off some Byzantine robustness to improve throughput without affecting privacy. We leverage our multi-block queries to construct four symmetric PIR (SPIR) protocols for databases with variable-length records. Three of our protocols support pricing and are therefore well suited to privacy-friendly sales of digital goods.