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

Version: 20130228:002348 (All versions of this report)

Short URL: ia.cr/2009/270

Discussion forum: Show discussion | Start new discussion