Cryptology ePrint Archive: Report 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).

Category / Keywords: cryptographic protocols / secure two-party computation, efficient protocols, full simulation-based security, oblivious polynomial evaluation

Date: received 17 Sep 2009

Contact author: harelc at cs biu ac il

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20090920:173115 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]