Paper 2026/2416

New Constructions of Quadratic and Cubic Permutations Admitting Optimal Threshold Implementations

Abstract

Side-channel attacks can uncover sensitive data by analyzing information leakages of cryptographic hardware devices caused by the power consumption, timing, electromagnetic, glitches, etc. Threshold implementation (TI), introduced by Nikova et al. in 2006, was proposed to resist differential power analysis side-channel attack on hardware implementations of block ciphers and eliminate information leakage due to glitches. For a function of algebraic degree $t\ge 2$, a TI requires at least $t+1$ shares. However, achieving this bound without fresh randomness is challenging, and we refer to such TIs as optimal. While a universal construction using $t+2$ shares is available, attaining the $t+1$ lower bound depends on the target permutation. In this paper, we present four constructions for optimal TIs of bijective S-boxes. We first demonstrate how adjoining identity coordinate functions enables optimal TIs, and then prove that $\mathcal{Q}_{30}^5$ admits optimal TIs. Second, we derive a matrix criterion for a class of quadratic permutations with optimal TIs, which covers all known examples, and can yield new $6$-bit quadratic classes with optimal TIs. Third, we introduce a weighted interpolation construction, which yields power permutations admitting optimal TIs, thereby providing counterexamples to the conjecture by Piccione et al. in 2023 that nonlinear power permutations cannot meet the $t+1$ lower bound. Finally, we present a derivative-uniform framework. Although this construction is not algebraic-degree-preserving for TIs and comes at a high cost of implementation, it is of significant theoretical interest and enables us to prove that every $4$-bit cubic permutation admits optimal TIs.

Note: The optimal TIs of 5-bit quadratic permutations can be found in https://github.com/gggaaarrryyyabs/3-share-TIs-of-5-bit-quadratic-permuations. This repo also contains optimal TIs of 4-bit cubic permutations, PRESENT S-box and inversion in GF(16).