MP-SPDZ FKOS15 `randomize_blocks`

FKOS15 is a binary MPC-with-preprocessing protocol used by MP-SPDZ’s Tinier backend. 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, and for a 1-bit T each copied byte carried only one fresh random bit (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}

Because masks are read back bit-by-bit but only one bit per byte was randomized, only 1 in every 8 sampled bits was actually random; the other 7 were always 0. The affected values are the party’s own authenticated random inputs (including sacrifice values), so an adversary can predict 7 of every 8 of those bits, far below the intended statistical-security margin.

The fix special-cases the 1-bit case to fill the byte buffer directly from the PRG, so bit-indexed reads see fresh randomness in every bit position (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}