Communication-Efficient MPC for General Adversary Structures

It was a warm day in Amalfi, Italy. It was also the first day of SCN 2014 and a cold breeze from the air conditioning passed through the room and it was time for the first session of the conference about MPC. Joshua Lampkins was in front of the projector to talk about “Communication-Efficient MPC for General Adversary Structures”, a joint work with Rafail Ostrovsky. Joshua described a new protocol for MPC for general adversary structures. Before going into detail be aware that a general adversary structure considers a set of adversaries in a protocol which is not necessarily less than some threshold. That is, usually we consider either honest majority or honest minority and don’t care which specific players are corrupted. However, in some cases certain sets of players are very unlikely to be corrupted together and collude. An example could be if a protocol is run by several countries, then allied countries might be more likely to collude in corruption, than countries who are at war with each other. How to best describe which parties might be corrupted together, and thus which kind of adversary corruption structure a protocol allows is not trivial. In general two approaches exists; as a Monotone Span Program (MSP) or a tree structure. In his talk Joshua considers a special type of adversary structure which is called Q2. Q2 is the structure where no two possible sets of corruptions cover the entire set of players. More specifically Joshua describes the first unconditionally maliciously and adaptively secure MPC protocol that achieves linear communication complexity in the size of the MSP representing the adversary structure. This is an improvement over previous protocols which are cubic in the size of the MSP.
The protocol combines several techniques and in particular verifiable secret sharing. Specifically a type of secret sharing called Kudzu sharing is used to for dispute handling in case of corrupted parities. Verifiability comes from double sharings, which is not trivial to achieve with the required complexity. The paper contains the details of the protocol along with the tricks used.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s