Bandwidth Efficient PIR from NTRU

Abstract. 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 spe-cific 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 computa-tional 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