Oblivious Polynomial Evaluation and Secure Set-Intersection from Algebraic PRFs

In this paper we study the two fundamental functionalities oblivious polynomial evaluation in the exponent and set-intersection, and introduce a new technique for designing efficient secure protocols for these problems (and others). Our starting point is the BenabbasGV11] technique (CRYPTO 2011) for verifiable delegation of polynomial evaluations, using algebraic PRFs. We use this tool, that is useful to achieve verifiability] in the outsourced setting, in order to achieve privacy in the standard two-party setting. Our results imply new simple and efficient oblivious polynomial evaluation (OPE) protocols. We further show that our OPE protocols are readily used for secure set-intersection, implying much simpler protocols in the plain model. As a side result, we demonstrate the usefulness of algebraic PRFs for various search functionalities, such as keyword search and oblivious transfer with adaptive queries. Our protocols are secure under full simulation-based definitions in the presence of malicious adversaries.
 
* This talk is aimed for the general audience.