Bandwidth Efficient PIR from NTRU

Yarkın Doröz; Berk Sunar; Ghaith Hammouri

Paper 2014/232

Bandwidth Efficient PIR from NTRU

Yarkın Doröz, Berk Sunar, and Ghaith Hammouri

Abstract

We present a private information retrieval (PIR) scheme based on a somewhat homomorphic encryption (SWHE). In particular, we customize an NTRU-based SWHE scheme in order to evaluate a specific class of fixed depth circuits relevant for PIR implementation, thus achieving a more practical implementation. In practice, a SWHE that can evaluate a depth 5 circuit is sufficient to construct a PIR capable of retrieving data from a database containing 4 billion rows. We leverage this property in order to produce a more practical PIR scheme. Com- pared to previous results, our implementation achieves a significantly lower bandwidth cost (more than 1000 times smaller). The computational cost of our implementation is higher than previous proposals for databases containing a small number of bits in each row. However, this cost is amortized as database rows become wider.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. 2nd Workshop on Applied Homomorphic Cryptography and Encrypted Computing - WAHC'14
Keywords: Private information retrieval homomorphic encryption NTRU
Contact author(s): sunar @ wpi edu
History: 2014-04-01: received
Short URL: https://ia.cr/2014/232
License: CC BY

BibTeX

@misc{cryptoeprint:2014/232,
      author = {Yarkın Doröz and Berk Sunar and Ghaith Hammouri},
      title = {Bandwidth Efficient {PIR} from {NTRU}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/232},
      year = {2014},
      url = {https://eprint.iacr.org/2014/232}
}