Paper 2019/855

WIDESEAS: A lattice-based PIR scheme implemented in EncryptedQuery

Dominic Dams, Jeff Lataille, Rino Sanchez, and 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Private Information RetrievalPIRApache PirkWIDESKIESMicrosoft SEAL PIRhomomorphic encryptionHEPaillier FHEMicrosoft SEALBFVFan-Vercauteren
Contact author(s)
jeff lataille @ envieta com
john wade @ envieta com
2019-08-21: last of 4 revisions
2019-07-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dominic Dams and Jeff Lataille and Rino Sanchez and John Wade},
      title = {WIDESEAS: A lattice-based PIR scheme implemented in EncryptedQuery},
      howpublished = {Cryptology ePrint Archive, Paper 2019/855},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.