TY - JOUR

T1 - Fast evaluation of polynomials over binary finite fields and application to side-channel countermeasures

AU - Coron, Jean-Sébastien

AU - Roy, Arnab

AU - Vivek, Srinivas

PY - 2015

Y1 - 2015

N2 - We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite field. For n-bit S-boxes, our new technique has heuristic complexity O(2n/2/√n) instead of O(2n/2) proven complexity for the Parity-Split method. We also prove a lower bound of Ω(2n/2/√n) on the complexity of any method to evaluate n-bit S-boxes; this shows that our method is asymptotically optimal. Here, complexity refers to the number of non-linear multiplications required to evaluate the polynomial corresponding to an S-box. In practice, we can evaluate any 8-bit S-box in 10 non-linear multiplications instead of 16 in the Roy–Vivek paper from CHES 2013, and the DES S-boxes in 4 non-linear multiplications instead of 7. We also evaluate any 4-bit S-box in 2 non-linear multiplications instead of 3. Hence our method achieves optimal complexity for the PRESENT S-box

AB - We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite field. For n-bit S-boxes, our new technique has heuristic complexity O(2n/2/√n) instead of O(2n/2) proven complexity for the Parity-Split method. We also prove a lower bound of Ω(2n/2/√n) on the complexity of any method to evaluate n-bit S-boxes; this shows that our method is asymptotically optimal. Here, complexity refers to the number of non-linear multiplications required to evaluate the polynomial corresponding to an S-box. In practice, we can evaluate any 8-bit S-box in 10 non-linear multiplications instead of 16 in the Roy–Vivek paper from CHES 2013, and the DES S-boxes in 4 non-linear multiplications instead of 7. We also evaluate any 4-bit S-box in 2 non-linear multiplications instead of 3. Hence our method achieves optimal complexity for the PRESENT S-box

U2 - 10.1007/s13389-015-0099-9

DO - 10.1007/s13389-015-0099-9

M3 - Journal article

SN - 2190-8508

VL - 5

SP - 73

EP - 83

JO - Journal of Cryptographic Engineering

JF - Journal of Cryptographic Engineering

IS - 2

ER -