TY - JOUR
T1 - Information-theoretically secure oblivious polynomial evaluation in the commodity-based model
AU - Tonicelli, Rafael
AU - Nascimento, Anderson C.A.
AU - Dowsley, Rafael
AU - Müller-Quade, Jörn
AU - Imai, Hideki
AU - Hanaoka, Goichiro
AU - Otsuka, Akira
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Commodity-based model
KW - Cryptographic primitives
KW - Information-theoretic cryptography
KW - Oblivious polynomial evaluation
UR - http://www.scopus.com/inward/record.url?scp=84921067160&partnerID=8YFLogxK
U2 - 10.1007/s10207-014-0247-8
DO - 10.1007/s10207-014-0247-8
M3 - Article
AN - SCOPUS:84921067160
VL - 14
SP - 73
EP - 84
JO - International Journal of Information Security
JF - International Journal of Information Security
SN - 1615-5262
IS - 1
ER -