Common MPC Pitfalls

MP-SPDZ FKOS15 `randomize_blocks`

FKOS15 is the MPC-with-preprocessing protocol underlying MASCOT and SPDZ2k. Party inputs are masked with preprocessed correlated randomness; the security argument requires that mask to carry the full claimed statistical-security parameter of entropy.

In MP-SPDZ pre-fix, Tools/BitVector.h::randomize_blocks produced under-randomized masks for single-bit input types: the loop drove tmp.randomize(G) once per T-sized block, but for a 1-bit T that path did not place fresh PRG output across every byte of the underlying buffer (source):

 1// Tools/BitVector.h — data61/MP-SPDZ (vulnerable, pre-99c5efc)
 2template<class T>
 3inline void BitVector::randomize_blocks(PRNG& G)
 4{
 5    T tmp;
 6    for (size_t i = 0; i < (nbytes / T::size()); i++)
 7    {
 8        tmp.randomize(G);                            // biased for 1-bit T
 9        memcpy(bytes + i * T::size(), tmp.get_ptr(), T::size());
10    }
11}

A malicious party who observes the masked input transcript can narrow the search space for the honest party’s bit-input by exploiting the mask’s reduced effective entropy: the soundness of FKOS15’s input authentication assumed the mask hid the input information-theoretically up to $2^{-s}$, but the under-randomized mask collapsed that guarantee to a smaller margin.

The fix special-cases the 1-bit case to fill the buffer directly from the PRG, so the mask gets full per-bit entropy rather than the under-populated bits the original loop produced (source):

 1// Tools/BitVector.h — data61/MP-SPDZ (fixed, 99c5efc)
 2template<class T>
 3inline void BitVector::randomize_blocks(PRNG& G)
 4{
 5    if (T::size_in_bits() == 1)
 6    {
 7        G.get_octets(bytes, nbytes);                 // raw PRG output
 8    }
 9    else
10    {
11        T tmp;
12        for (size_t i = 0; i < (nbytes / T::size()); i++)
13        {
14            tmp.randomize(G);
15            memcpy(bytes + i * T::size(), tmp.get_ptr(), T::size());
16        }
17    }
18}