International Association
for Cryptologic Research

A single-database computationally-Private Information Retrieval (hereafter PIR) scheme is a protocol in which a user retrieves a record from a database while hiding which from the database administrators. Classic protocols require that the database server execute an algorithm over all the database content at very low speeds which impairs significantly their usability.

In [1], given certain assumptions, realistic at the time, Sion and Carbunar showed that PIR schemes were not practical and most likely would never be. To this day, this conclusion is widely accepted by researchers and practitioners. Using the paradigm shift introduced by lattice-based cryptography, we show that the conclusion of Sion and Carbunar is not valid anymore: PIR is of practical value. This is achieved without compromising security, using simple standard encryption schemes, and very conservative parameter choices.

In order to prove this, we provide a fast fully-usable PIR library and do a performance analysis, illustrated by use-cases, highlighting that this library is practical in a large span of situations. The PIR library allows a server to process its data at a throughput ranging from 1 Gbps on a single core of a commodity CPU to almost 10 Gbps on a high-end processor using its multi-core capabilities.

After replying to a first query (or through pre-computation), there is a x3 to x5 speedup for subsequent queries (if the database content is unchanged for those queries). The performance analysis shows for example that it is possible to privately receive an HD movie from a Netflix-like database (with 35K movies) with enough throughput to watch it in real time, or to build a sniffer over a Gbit link with an obfuscated code that hides what it is sniffing.

This library is modular, allowing alternative homomorphic encryption modules to be plugged-in. We provide a slow but compact crypto module with a number theoretic Paillier encryption, and a fast crypto module with Ring-LWE based encryption (based on standard lattice-based problems and conservative parameters). The library has an auto-optimizer that chooses the best protocol parameters (recursion level, aggregation) and crypto parameters (if the crypto module implements the necessary API) for a given setting.

This greatly increases the usability for non-specialists. Given the complexity of parameter settings in lattice-based homomorphic encryption and the fact that PIR adds a second layer of choices that interact with crypto parameter settings, we believe this auto-optimizer will also be useful to specialists.