Paper 2019/855

WIDESEAS: A lattice-based PIR scheme implemented in EncryptedQuery

Dominic Dams, Jeff Lataille, Rino Sanchez, and John Wade

Abstract

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.