Efficient and Secure Evaluation of Multivariate Polynomials and Applications

摘要

In this work, we design two-party and multiparty protocols for evaluating multivariate polynomials at participants' inputs with security against a malicious adversary who may corrupt all but one of the parties. Our protocols are round and communication efficient, and use the underlying cryptographic primitives in a black-box way. Our construction achieves optimal communication complexity for degree 2 and 3 polynomials. Our constructions can be used to securely and efficiently realize a wide range of functionalities. For instance, we demonstrate how our techniques lead to efficient protocols for secure linear algebra with security against malicious adversaries. Other applications include secure evaluation of DNF/CNF formulas, and conditional secret reconstruction (or conditional oblivious transfer) for a large family of condition functions.