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
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint. MINOR revision.
- Keywords
- Private Information RetrievalPIRApache PirkWIDESKIESMicrosoft SEAL PIRhomomorphic encryptionHEPaillier FHEMicrosoft SEALBFVFan-Vercauteren
- Contact author(s)
-
jeff lataille @ envieta com
john wade @ envieta com - History
- 2019-08-21: last of 4 revisions
- 2019-07-23: received
- See all versions
- Short URL
- https://ia.cr/2019/855
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/855, 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}, url = {https://eprint.iacr.org/2019/855} }