Nonlinear Computation¶
While the computation of addition and multiplication varies from protocol, nonlinear computation such as comparison in arithmetic domains (modulus other than two) only comes in three flavors throughout MPSPDZ:
 Unknown prime modulus
This approach goes back to Catrina and de Hoogh. It crucially relies on the use of secret random bits in the arithmetic domain. Enough such bits allow to mask a secret value so that it is secure to reveal the masked value. This can then be split in bits as it is public. The public bits and the secret mask bits are then used to compute a number of nonlinear functions. The same idea has been used to implement fixedpoint and floatingpoint computation. We call this method “unknown prime modulus” because it only mandates a minimum modulus size for a given cleartext range, which is roughly the cleartext bit length plus a statistical security parameter. It has the downside that there is implicit enforcement of the cleartext range.
 Known prime modulus
Damgård et al. have proposed nonlinear computation that involves an exact prime modulus. We have implemented the refined bit decomposition by Nishide and Ohta, which enables further nonlinear computation. Our assumption with this method is that the cleartext space is slightly smaller the full range modulo the prime. This allows for comparison by taking a difference and extracting the most significant bit, which is different than the above works that implement comparison between two positive numbers modulo the prime. We also used an idea by Makri et al., namely that a random \(k\)bit number is indistinguishable from a random number modulo \(p\) if the latter is close enough to \(2^k\).
 Poweroftwo modulus
In the context of nonlinear computation, there are two important differences to prime modulus setting:
Multiplication with a power of two effectively erases some of the most significant bits.
There is no right shift using multiplication. Modulo a prime, multiplying with a power of the inverse of two allows to rightshift numbers with enough zeros as least significant bits.
Taking this differences into account, Dalskov et al. have adapted the maskandreveal approach above to the setting of computation modulo a power of two.
See also this slide deck for an introduction to nonlinear computation in arithmetic MPC.
MixedCircuit Computation¶
Another approach to nonlinear computation is switching to binary computation for parts of the computation. MPSPDZ implements protocols proposed for particular security models by a number of works: Demmler et al., Mohassel and Rindal, and Dalskov et al. MPSPDZ also implements more general methods such as daBits and edaBits.
See also this slide deck for an introduction to mixedcircuit computation.
Protocol Pairs¶
The following table lists the matching arithmetic and binary protocols.
Arithmetic 
Binary 

MASCOT, SPDZ2k, LowGear, HighGear, CowGear, ChaiGear 
Tinier with improved cutandchoose analysis by Furukawa et al. 
Semi, Hemi, Temi, Soho, Semi2k 
SemiBin (Beaver triples modulo 2 using OT) 
Malicious Shamir over \(GF(2^{40})\) for secure sacrificing 

Malicious Rep3, PostSacrifice, SPDZwise replicated 

Rep4 modulo 2 

Shamir over \(GF(2^8)\) 

ATLAS over \(GF(2^8)\) 

Rep3 