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

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

Research output: Contribution to journalArticleResearchpeer-review

17 Citations (Scopus)


Oblivious polynomial evaluation (OPE) consists of a two-party protocol where a sender inputs a polynomial p(x) and a receiver inputs a single value x0. At the end of the protocol, the sender learns nothing and the receiver learns P(x0). 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 Crépeau 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.

Original languageEnglish
Pages (from-to)73-84
Number of pages12
JournalInternational Journal of Information Security
Issue number1
Publication statusPublished - 2015
Externally publishedYes


  • Commodity-based model
  • Cryptographic primitives
  • Information-theoretic cryptography
  • Oblivious polynomial evaluation

Cite this