Information-theoretically secure oblivious polynomial evaluation in the commodity-based model

• DOI: 10.1007/s10207-014-0247-8
• Publication Date: 2014-06-19T14:05:56Z
• Authors: Rafael Tonicelli; Anderson C. A. Na...; Rafael Dowsley; Jörn Müller-Quade; Hideki Imai; Goichiro Hanaoka; Akira Otsuka
• Keywords: Communication source; Value (mathematics)

Oblivious polynomial evaluation (OPE) consists of a two-party protocol where a sender inputs a polynomial $$p(x)$$ p ( x ) and a receiver inputs a single value $$x_{0}$$ x 0 . At the end of the protocol, the sender learns nothing and the receiver learns $$p(x_{0})$$ p ( x 0 ) . This paper deals with the problem of oblivious polynomial evaluation under an information-theoretic perspective, which is based on the definitions of unconditional security developed by Crepeau et al. (Information-theoretic conditions for two-party secure function evaluation. EUROCRYPT 2006, LNCS 4004. Springer, Berlin, Heidelberg, pp 538---554, 2006). In this paper, we propose an information-theoretic 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. We present a natural generalization to OPE called oblivious linear functional evaluation.