%0 Book Section
%B Applied Cryptography and Network Security
%D 2011
%T Secure Efficient Multiparty Computing of Multivariate Polynomials and Applications
%A Dana Dachman-Soled
%A Malkin, Tal
%A Raykova, Mariana
%A Yung, Moti
%E Lopez, Javier
%E Tsudik, Gene
%K additive homomorphic encryption
%K Algorithm Analysis and Problem Complexity
%K Computer Communication Networks
%K Data Encryption
%K Discrete Mathematics in Computer Science
%K Management of Computing and Information Systems
%K multiparty set intersection
%K multivariate polynomial evaluation
%K secret sharing
%K secure multiparty computation
%K Systems and Data Security
%K threshold cryptosystems
%X We present a robust secure methodology for computing functions that are represented as multivariate polynomials where parties hold different variables as private inputs. Our generic efficient protocols are fully black-box and employ threshold additive homomorphic encryption; they do not assume honest majority, yet are robust in detecting any misbehavior. We achieve solutions that take advantage of the algebraic structure of the polynomials, and are polynomial-time in all parameters (security parameter, polynomial size, polynomial degree, number of parties). We further exploit a “round table” communication paradigm to reduce the complexity in the number of parties. A large collection of problems are naturally and efficiently represented as multivariate polynomials over a field or a ring: problems from linear algebra, statistics, logic, as well as operations on sets represented as polynomials. In particular, we present a new efficient solution to the multi-party set intersection problem, and a solution to a multi-party variant of the polynomial reconstruction problem.
%B Applied Cryptography and Network Security
%S Lecture Notes in Computer Science
%I Springer Berlin Heidelberg
%P 130 - 146
%8 2011/01/01/
%@ 978-3-642-21553-7, 978-3-642-21554-4
%G eng
%U http://link.springer.com/chapter/10.1007/978-3-642-21554-4_8