TY - CHAP
T1 - Secure Efficient Multiparty Computing of Multivariate Polynomials and Applications
T2 - Applied Cryptography and Network Security
Y1 - 2011
A1 - Dana Dachman-Soled
A1 - Malkin, Tal
A1 - Raykova, Mariana
A1 - Yung, Moti
ED - Lopez, Javier
ED - Tsudik, Gene
KW - additive homomorphic encryption
KW - Algorithm Analysis and Problem Complexity
KW - Computer Communication Networks
KW - Data Encryption
KW - Discrete Mathematics in Computer Science
KW - Management of Computing and Information Systems
KW - multiparty set intersection
KW - multivariate polynomial evaluation
KW - secret sharing
KW - secure multiparty computation
KW - Systems and Data Security
KW - threshold cryptosystems
AB - 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.
JA - Applied Cryptography and Network Security
T3 - Lecture Notes in Computer Science
PB - Springer Berlin Heidelberg
SN - 978-3-642-21553-7, 978-3-642-21554-4
UR - http://link.springer.com/chapter/10.1007/978-3-642-21554-4_8
ER -