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 ]