[Resource Topic] 2019/855: WIDESEAS: A lattice-based PIR scheme implemented in EncryptedQuery

Welcome to the resource topic for 2019/855

WIDESEAS: A lattice-based PIR scheme implemented in EncryptedQuery

Authors: Dominic Dams, Jeff Lataille, Rino Sanchez, John Wade


We introduce the WIDESEAS protocol for lattice-based Private Information Retrieval (PIR), and we give performance numbers for its recent implementation in the EncryptedQuery open-source PIR software. This protocol uses the fully homomorphic Brakerski–Fan–Vercauteren (BFV) encryption scheme, as opposed to the Paillier scheme, which is used in all earlier versions of EncryptedQuery. We show that the homomorphic capabilities of BFV result in smaller query sizes (due to a query-shrinking technique based on batching and ciphertext multiplication), higher response generation rates (due to using relinearization to keep ciphertexts small; due to caching certain products of query elements in the NTT domain; due to using the distributive law to achieve a quadratic reduction in the total number of ciphertext multiplications; due to using lazy reduction to speed up modular multiplies; and, due to exploiting properties of inverse NTTs over periodic data, and forward NTTs over sparse data, for the purpose of accelerating plain multiplications), and comparable response sizes (due to using modulus switching to discard redundant ciphertext information prior to transmitting the response). For instance, running a single thread (with Turbo Boost disabled) on a MacBook Pro equipped with a 2.8 GHz Intel core i7, and using a 20-bit hash and a 2^{15}-byte data chunk size (which allows us to search for a single targeted selector), our implementation can (i) generate a query of size 64\ \mathrm{MiB} in around 0.41\ {\rm seconds,} (ii) process a query against a 1\ \mathrm{TiB} database (comprised of 2^{20}-many 1\ \mathrm{MiB} records) at a rate of 23.67\ \mathrm{MiB/s} (which is at least two orders of magnitude faster than the Paillier-based version of EncryptedQuery), and (iii) generate a response of size 4\ \mathrm{MiB} in around 0.51\ \mathrm{days}{\rm .} We expect a speed up on server class machines. Our implementation uses the Microsoft SEAL library along with a small amount of custom code.

ePrint: https://eprint.iacr.org/2019/855

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .