International Association
for Cryptologic Research

Threshold implementation is a method based on secret sharing to secure cryptographic ciphers (and in particular S-boxes) against differential power analysis. Until now, threshold implementations were only constructed for specific types of functions and some small S-boxes, but no general construction for all S-boxes was ever presented. The lower bound for the number of shares of threshold implementation is $t+1$, where $t$ is the algebraic degree of the S-box. Since the smallest number of shares $t+1$ is not possible for all S-Boxes, as proven by Bilgin et al. in 2015, then there does not exist a universal construction with $t+1$ shares. Hence, if there is a universal construction working for all permutations then it should work with at least $t+2$ shares. In this paper, we present the first optimal universal construction with $t+2$ shares. This construction enables low latency hardware implementations without the need for randomness. In particular, we apply this result to find the first two uniform sharings of the AES S-box. Area and performance figures for hardware implementations are provided.