Secure Efficient Multiparty Computing of Multivariate Polynomials and Applications

TitleSecure Efficient Multiparty Computing of Multivariate Polynomials and Applications
Publication TypeBook Chapters
Year of Publication2011
AuthorsDachman-Soled D, Malkin T, Raykova M, Yung M
EditorLopez J, Tsudik G
Book TitleApplied Cryptography and Network Security
Series TitleLecture Notes in Computer Science
Pagination130 - 146
PublisherSpringer Berlin Heidelberg
ISBN Number978-3-642-21553-7, 978-3-642-21554-4
Keywordsadditive homomorphic encryption, Algorithm Analysis and Problem Complexity, Computer Communication Networks, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, multiparty set intersection, multivariate polynomial evaluation, secret sharing, secure multiparty computation, Systems and Data Security, threshold cryptosystems

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.