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

Download Now
Provided by: University of Washington School of Public Health & Community Medicine
Topic: Security
Format: PDF
The authors propose a new, communication-efficient way for users to fetch multiple blocks simultaneously in Goldberg's robust Information-Theoretic Private Information Retrieval (IT-PIR) scheme. Their new multi-block IT-PIR trades off some Byzantine robustness to improve throughput without affecting user privacy. By taking advantage of the recent Cohn-Heninger multi-polynomial list decoding algorithm, they show how realistic parameter choices enable the user to retrieve several blocks without increasing the communication or computation costs beyond what is required to retrieve a single block, and argue that the resulting scheme still maintains essentially optimal Byzantine robustness in practice.
Download Now

Find By Topic