Paper 2015/004

Oblivious Polynomial Evaluation and Secure Set-Intersection from Algebraic PRFs

Carmit Hazay


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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2015
Efficient Secure ComputationOblivious Polynomial EvaluationSecure Set-IntersectionCommitted Oblivious PRF
Contact author(s)
carmit hazay @ biu ac il
2017-07-24: revised
2015-01-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carmit Hazay},
      title = {Oblivious Polynomial Evaluation and Secure Set-Intersection from Algebraic PRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2015/004},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.