Fast Computation on Encrypted Polynomials and Applications

Abstract

In this paper we design fast algorithms for computing on encrypted polynomials. More specifically, we design efficient algorithms for encrypted FFT, polynomial multiplication, division, and multipoint evaluation. The encryption scheme we need only has to be additively homomorphic.

The above set of algorithms are useful building blocks for many applications in secure computation. We explore a few of them in this paper. First, we use the new algorithms to design a protocol for batch oblivious polynomial evaluation (OPE). Batch OPE can be seen as a generalization of k-out-n oblivious transfer and batch private keyword search. The computational complexity of our protocol is nearly linear in the degree of the polynomial and does not grow with the number of points evaluated at the polynomial. Second, we design two different protocols for the private set intersection problem both of which roughly require linear computation and communication. One is based on the batch OPE protocol we design, and the other is an adaptation of the ideas of [Kissner and Song, CRYPTO 2005] using the more efficient encrypted polynomial multiplication we introduce in this paper.

While we mostly focus on security against semi-honest adversaries, our algorithmic ideas, in essence, yield nearly linear size arithmetic circuits for the set intersection and the batch OPE problems. Implementing these circuits via the new and efficient compiler of [Damgard and Orlandi, CRYPTO 2010] leads to protocols with linear complexity for the private set intersection and batch OPE with security against malicious adversaries based on standard and general assumptions.