Show simple item record

dc.contributor.authorMohassel, Paymaneng
dc.description.abstractIn 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.eng
dc.rightsAttribution Non-Commercial No Derivatives 3.0 Unported*
dc.subjectInformation Securityeng
dc.subject.otherSecure computationeng
dc.subject.otherComputing on Encrypted Dataeng
dc.subject.otherSecure Set Intersectioneng
dc.titleFast Computation on Encrypted Polynomials and Applicationseng
dc.typetechnical reporteng
dc.publisher.corporateUniversity of Calgaryeng
dc.identifier.doi Scienceeng

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution Non-Commercial No Derivatives 3.0 Unported
Attribution Non-Commercial No Derivatives 3.0 Unported