Rafail Ostrovsky - Publications

Communication−Efficient MPC for General Adversary Structures

Jashua Lampkins, Rafail Ostrovsky


A multiparty computation(MPC) protocol allows a set of players to compute a function of their inputs while keeping the inputs private and the same time securing the correctness of the output. Most MPC protocols assume that the adversary can corrupt up to a fixed fraction of the number of players. Hirt and Maurer initiated the study of MPC under more general corruption patterns, in which the adversary is allowed to corrupt any set of players in some pre−defined collection of sets[1:]. In this paper we consider this important direction and present improved communication complexity of MPC protocols for general adversary structures. More specifically, ours is the first unconditionally secure protocol that achieves liner communication in the size of Montone Span program representing the adversary structure in the malicious setting against any Q2 adversary structure, where all previous protocols were at least cubic.

comment: SCN 2014 PP: 155−174

Fetch PDF file of the paper

Back to Publications List