## Cryptology ePrint Archive: Report 2009/270

Information-Theoretically Secure Oblivious Polynomial Evaluation in the Commodity-Based Model

Rafael Tonicelli and Rafael Dowsley and Goichiro Hanaoka and Hideki Imai and Jörn Müller-Quade and Akira Otsuka and Anderson C. A. Nascimento

Abstract: Oblivious polynomial evaluation (OPE) consists of a two-party protocol where a sender inputs a polynomial $P$, and a receiver inputs a single value $i$. At the end of the protocol, the sender learns nothing and the receiver learns $P(i)$. This paper deals with the problem of oblivious polynomial evaluation under an information-theoretical perspective, which is based on recent definitions of Unconditional Security developed by Crépeau et al. (EUROCRYPT 2006). In this paper, we propose an information-theoretical model for oblivious polynomial evaluation relying on pre-distributed data, and prove very general lower bounds on the size of the pre-distributed data, as well as the size of the communications in any protocol. It is demonstrated that these bounds are tight by obtaining a round-optimal OPE protocol, which meets the lower bounds simultaneously. Some applications of the proposed model are provided, such as solutions for the Millionaire Problem'' and the Oblivious Equality Testing Problem''. We also present a natural generalization to OPE called oblivious linear functional evaluation.

Category / Keywords:

Date: received 8 Jun 2009, last revised 27 Feb 2013

Contact author: rdowsley at cs ucsd edu

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2009/270

[ Cryptology ePrint archive ]