MiniTrix for MiniMacs

from The MPC Lounge

Sep 6, 2014, 3:35:48 PM

Following the talk on categorizing MPC protocols is the author formally known as Rasmus Lauritsen (currently known as Rasmus Zakarias) giving “An Empirical Study and Some Improvements of the MiniMac Protocol for Secure Computation”, a joint work with Ivan Damgård and Tomas Toft. The talk is about a continuation of work on the protocol known as MiniMac, introduced by Ivan Damgård and Sarah Zakarias in 2012. Quickly explained MiniMac is a maliciously secure MPC protocol for dishonest majority working where the plain values are elements of small fields (in particular characteristic 2, and thus Boolean circuits). The protocol is in the preprocessing model (meaning there is no need to know the input or the function specification during the offline phase) and has some similarity to the SPDZ protocol. More specifically elements are additively shared over a finite field and Beaver triples are used for multiplication. However, using additive shares will only yield semi-honest security, thus MACs are added to the shares. Unfortunately, this will only be secure if the MACs are from a large field, which is too inefficient. The solution is instead to concatenate many elements in a Same Instruction, Multiple Data (SIMD) manner and use an error correcting code on such a vector and then MAC the codeword.
Rasmus and his co-authors continue work on the MiniMac protocol, and in particular introduce the first implementation of the protocol. More specifically, they introduce concrete choices of parameters and error correcting code along with several optimizations increasing efficiency both in theory and practice. One such specific optimization involves realizing SIMD AND operations of individual bits in GF2^8 using Beaver style triplets. Another optimization makes the workload more symmetric when only two parties are running the protocol. Besides the more theoretical optimizations, Rasmus also explains that they have realized several implementation wise optimizations such as using the Fast Fourier Transform for encoding.
In order to make a fair benchmark of their optimizations of MiniMac the authors have implemented the protocol both with and without optimizations along with the protocol known as TinyLEGO [NNOB12]. What their implementation show is that with no optimizations TinyOT is a bit faster than MiniMac, but with the optimizations MiniMac becomes close to two order of magnitude faster than TinyOT (in the amortized sense) when doing the “standard” MPC benchmark of oblivious AES encryption. In particular down to a 4 ms online phase!