Bandwidth efficient PIR from NTRU

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations


We present a private information retrieval (PIR) scheme based on 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. Compared 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.

Original languageEnglish (US)
Title of host publicationFinancial Cryptography and Data Security - FC 2014 Workshops, BITCOIN and WAHC 2014, Revised Selected Papers
EditorsMichael Brenner, Matthew Smith, Rainer Böhme, Tyler Moore
PublisherSpringer Verlag
Number of pages13
ISBN (Electronic)9783662447734
StatePublished - 2014
Externally publishedYes
Event18th International Conference on Financial Cryptography and Data Security - Christ Church, Barbados
Duration: Mar 7 2014Mar 7 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other18th International Conference on Financial Cryptography and Data Security
CityChrist Church

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Homomorphic encryption
  • NTRU
  • Private information retrieval


Dive into the research topics of 'Bandwidth efficient PIR from NTRU'. Together they form a unique fingerprint.

Cite this