Cryptology ePrint Archive: Report 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.

Category / Keywords: Private information retrieval, homomorphic encryption, NTRU

Original Publication (in the same form): 2nd Workshop on Applied Homomorphic Cryptography and Encrypted Computing - WAHC'14

Date: received 31 Mar 2014

Contact author: sunar at wpi edu

Available format(s): PDF | BibTeX Citation

Version: 20140401:064831 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]