Paper 2019/1165

High-order private multiplication in characteristic two revisited

Nicolas Bordes and Pierre Karpman

Abstract

We revisit the high-order masking schemes for private multiplication introduced by Belaïd et al. at EUROCRYPT 2016, and the matrix model for non-interference (NI) security that they develop in their follow-up work of CRYPTO 2017. This leads to two main results. 1) We generalise the theorems of CRYPTO 2017 so as to be able to apply them to masking schemes over any finite field --- in particular GF(2) --- and to be able to analyse the strong non-interference (SNI) security notion. This leads to an efficient algorithm that allows us to computationally check the (S)NI security of binary schemes up to order d=11. 2) We propose new SNI and NI masking gadgets for multiplication over GF(2) (and any extension thereof) up to order 9 and 11 that improve the randomness complexity of the schemes of EUROCRYPT 2016 and of Ishai, Sahai and Wagner (CRYPTO 2003) respectively. A natural generalisation of the NI schemes is also conjectured to be secure at any order.