Paper 2009/459

Efficient Oblivious Polynomial Evaluation with Simulation-Based Security

Carmit Hazay and Yehuda Lindell

Abstract

The study of secure multiparty computation has yielded powerful feasibility results showing that any efficient functionality can be securely computed in the presence of malicious adversaries. Despite this, there are few problems of specific interest for which we have highly efficient protocols that are secure in the presence of malicious adversaries under full simulation based definitions (following the ideal/real model paradigm). Due to the difficulties of constructing such protocols, many researchers have resorted to weaker definitions of security and weaker adversary models. In this paper, we construct highly efficient protocols for the well-studied problem of oblivious polynomial evaluation. Our protocol is secure under standard cryptographic assumptions for the settings of malicious adversaries, and readily transform to protocols that are secure under universal composability and in the presence of covert adversaries. Our protocol is constant round and requires O(d \cdot s) exponentiations, where $d$ is the degree of the polynomial and s is a statistical security parameter (that should equal about 160 in practice).