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

Rafael Tonicelli, Rafael Dowsley, Goichiro Hanaoka, Hideki Imai, Jörn Müller-Quade, 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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
rdowsley @ cs ucsd edu
History
2013-02-28: last of 3 revisions
See all versions
Short URL
https://ia.cr/2009/270

CC BY

BibTeX

@misc{cryptoeprint:2009/270,
author = {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},
title = {Information-Theoretically Secure Oblivious Polynomial Evaluation in the Commodity-Based Model},
howpublished = {Cryptology ePrint Archive, Paper 2009/270},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/270}},
url = {https://eprint.iacr.org/2009/270}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.