Non-linear Computation¶

While the computation of addition and multiplication varies from protocol, non-linear computation such as comparison in arithmetic domains (modulus other than two) only comes in three flavors throughout MP-SPDZ:

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 non-linear functions. The same idea has been used to implement fixed-point and floating-point 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.

If you want to use this approach with a given prime, do not specify the prime during compilation but during execution.

Known prime modulus

Damgård et al. have proposed non-linear computation that involves an exact prime modulus. We have implemented the refined bit decomposition by Nishide and Ohta, which enables further non-linear 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\).

This approach is used if you specify a prime during compilation.

Power-of-two modulus

In the context of non-linear 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 right-shift numbers with enough zeros as least significant bits.

Taking this differences into account, Dalskov et al. have adapted the mask-and-reveal approach above to the setting of computation modulo a power of two.

See also this slide deck for an introduction to non-linear computation in arithmetic MPC.

Mixed-Circuit Computation¶

Another approach to non-linear computation is switching to binary computation for parts of the computation. MP-SPDZ implements protocols proposed for particular security models by a number of works: Demmler et al., Mohassel and Rindal, and Dalskov et al. MP-SPDZ also implements more general methods such as daBits and edaBits.

See also this slide deck for an introduction to mixed-circuit computation.

Protocol Pairs¶

The following table lists the matching arithmetic and binary protocols.

Arithmetic	Binary
MASCOT, SPDZ2k, LowGear, HighGear, CowGear, ChaiGear	Tinier with improved cut-and-choose analysis by Furukawa et al.
Semi, Hemi, Temi, Soho, Semi2k	SemiBin (Beaver triples modulo 2 using OT)
Malicious Shamir	Malicious Shamir over \(GF(2^{40})\) for secure sacrificing
Malicious Rep3, Post-Sacrifice, SPDZ-wise replicated	Malicious Rep3 modulo 2
Rep4	Rep4 modulo 2
Shamir	Shamir over \(GF(2^8)\)
ATLAS	ATLAS over \(GF(2^8)\)
Rep3	Rep3