[Resource Topic] 2009/270: Information-Theoretically Secure Oblivious Polynomial Evaluation in the Commodity-Based Model

Welcome to the resource topic for 2009/270

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

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


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.

ePrint: https://eprint.iacr.org/2009/270

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .