Dishonest Majority Multi-Party Computation for Binary Circuits

Result by Enrique Larraia, Emmanuela Orsini, Nigel P. Smart

Enrique presented a new protocol for static and malicious secure MPC against a dishonest majority. The protocol is a joint work with Emmanuela Orsini and Nigel P. Smart and takes its departure in the TinyOT protocol from Crypto 2012 [NNOB12]. This means that the protocol consist of a relatively slow offline phase and a fast online phase. Specifically the protocol works on Boolean values and is based on additive secret sharing. Thus in the preprocessing phase the parties collaborate to constructs shares of authenticated bits (called aBits). These shares are additively constructed, so when XORing the bits held by all parties the true value is obtained. Besides a bit share, a MAC is also added to each bit share. This MAC is also additively shared and is used to ensure that parties do not try to negate the value of their share, and in turn the actual value shared. The additivity of the shares makes it possible to do XOR operations locally and thus are basically free. To do AND operations a similar approach to SPDZ and BeDoZa is used. In its basic shape it uses the idea of Beaver triples: Having three random aBits constrained to be a multiplication. However, in their paper they use quadruples which express an oblivious transfer (OT) of a bit. This can then be used to construct AND gates. The generation of the aBits, and in turn the quadruples, are done in a batching manner using OT. Even though OT is generally expensive, this is actually not the case for their protocol as it supports OT extensions, which makes it possible to use a few “real” OTs to construct a practically unlimited amount of OTs using only symmetric primitives.
In conclusion they manage to do a very nice and efficient generalization of TinyOT working for an arbitrary amount of players.


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s