1. PIR with compressed queries and amortized query processing 2018 Oakland PIR
    Sebastian Angel and Hao Chen and K Laine and S Setty
    [View PDF on ieeexplore.ieee.org]
    [Show BibTex Citation]

    @INPROCEEDINGS{8418648,
    author={Sebastian Angel and Hao Chen and K Laine and S Setty},
    booktitle={2018 IEEE Symposium on Security and Privacy (SP)},
    title={PIR with Compressed Queries and Amortized Query Processing},
    year={2018},
    volume={},
    number={},
    pages={962-979},
    keywords={cryptographic protocols;data privacy;query processing;compressed queries;amortized query processing;private information retrieval;privacy-preserving systems;CPU-efficient CPIR protocols;data encoding;probabilistic batch codes;PBCs;multiquery PIR scheme;related encodings;Pung private communication system;custom multiquery CPIR protocol;privacy guarantees;Servers;Databases;Protocols;Encoding;Cryptography;Privacy;Information retrieval;private information retrieval;batch codes;PIR;FHE;multi query PIR},
    doi={10.1109/SP.2018.00062},
    ISSN={2375-1207},
    month={May},}

Private information retrieval (PIR) is a key building block in many privacy-preserving systems. Unfortunately, existing constructions remain very expensive. This paper introduces two techniques that make the computational variant of PIR (CPIR) more efficient in practice. The first technique targets a recent class of CPU-efficient CPIR protocols where the query sent by the client contains a number of ciphertexts proportional to the size of the database. We show how to compresses this query, achieving size reductions of up to 274X. The second technique is a new data encoding called probabilistic batch codes (PBCs). We use PBCs to build a multi query PIR scheme that allows the server to amortize its computational cost when processing a batch of requests from the same client. This technique achieves up to 40× speedup over processing queries one at a time, and is significantly more efficient than related encodings. We apply our techniques to the Pung private communication system, which relies on a custom multi-query CPIR protocol for its privacy guarantees. By porting our techniques to Pung, we find that we can simultaneously reduce network costs by 36× and increase throughput by 3X.

  1.