One (Block) Size Fits All: PIR and SPIR with Variable-Length Records via Multi-Block Queries

Author(s): Ryan Henry, Yizhou Huang, and Ian Goldberg

Download: Paper (PDF)

Date: 23 Apr 2013

Document Type: Presentations

Additional Documents: Slides

Associated Event: NDSS Symposium 2013

Abstract:

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.