Skip to main content
Article
Information-Theoretically Secure Oblivious Polynomial Evaluation in the Commodity-Based Model
International Journal of Information Security
  • Rafael Tonicelli
  • Anderson C. Nascimento, University of Washington Tacoma
  • Rafael Dowsley
  • Jörn Müller-Quade
  • Hideki Imai
  • Goichiro Hanaoka
  • Akira Otsuka
Publication Date
6-15-2014
Document Type
Article
Abstract

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

DOI
10.1007/s10207-014-0247-8
Publisher Policy
pre-print, post-print
Citation Information
Rafael Tonicelli, Anderson C. Nascimento, Rafael Dowsley, Jörn Müller-Quade, et al.. "Information-Theoretically Secure Oblivious Polynomial Evaluation in the Commodity-Based Model" International Journal of Information Security Vol. 14 Iss. 1 (2014) p. 73 - 84
Available at: http://works.bepress.com/anderson-nascimento/13/