Mixing Additive and Multiplicative Masking for Probing Secure Polynomial Evaluation Methods

Masking is a sound countermeasure to protect implementations of block- cipher algorithms against Side Channel Analysis (SCA). Currently, the most efficient masking schemes use Lagrange’s Interpolation Theorem in order to represent any S- box by a polynomial function over a binary finite field. Masking the processing of an S-box is then achieved by masking every operation involved in the evaluation of its polynomial representation. While the common approach requires to use the well- known Ishai-Sahai-Wagner (ISW) scheme in order to secure this processing, there exist alternatives. In the particular case of power functions, Genelle, Prouff and Quisquater proposed an efficient masking scheme (GPQ). However, no generalization has been suggested for polynomial functions so far. In this paper, we solve the open problem of extending GPQ for polynomials, and we also solve the open problem of proving that both the original scheme and its variants for polynomials satisfy the t-SNI security definition. Our approach to extend GPQ is based on the cyclotomic method and results in an alternate cyclotomic method which is three times faster in practice than the original proposal in almost all scenarios we address. The best- known method for polynomial evaluation is currently CRV which requires to use the cyclotomic method for one of its step. We also show how to plug our alternate cyclo- tomic approach into CRV and again provide an alternate approach that outperforms the original in almost all scenarios. We consider the masking of n-bit S-boxes for n ∈ [4;8] and we get in practice 35% improvement of efficiency for S-boxes with dimension n ∈ {5,7,8} and 25% for 6-bit S-boxes