Paper 2025/2016 Original: eprint.iacr.org/2025/2016 ↗

Constructions of a Family of Nonlinear Permutations of Any Possible Algebraic Degrees with the 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. An attack exploiting these leakages is the differential power analysis (DPA). Threshold Implementation (TI), introduced by Nikova et al. [JoC 24(2):292-321, 2011], was proposed to resist DPA on hardware implementations of block ciphers and eliminate information leakage due to glitches. TI is based on secret sharing and multi-party computation. Since the cost of implementing a TI is directly proportional to the number of shares, minimizing the number of shares is of importance. Note that Nikova et al. proved that, for a target function of algebraic degree $t\geq 2$, the lower bound on the number of shares to implement a TI is $t+1$. And we call a TI with $t+1$ shares an optimal TI. However, achieving this bound is challenging. To date, the only universal construction for any bijective function of algebraic degree $t\geq 2$ achieves a TI with $t+2$ shares, which was proposed by Piccione et al. [IEEE TIT 69(10):6700-6710, 2023]. Only two studies managed to implement optimal TIs. They either concentrated on the Feistel structure or were based on Shannon's expansion. It should be noted that adding randomness can meet the $t+1$ bound, but generating randomness is expensive in practice. Consequently, this paper endeavors to fill this gap by systematically investigating the substitution-boxes (S-boxes to be brief) that can achieve optimal TIs without additional randomness. In this paper, inspired by the Feistel structure in the design of S-boxes, we present two constructions of bijective S-boxes with optimal TIs. Of particular interest is the S-boxes constructed from two permutations exhibiting nonzero nonlinearity, making them potential candidates for S-boxes with desirable properties. For applications, our constructions can interpret the existence of $3$-share or $4$-share TIs for certain functions in $3$, $4$ and $5$ variables, as previously reported by Bilgin et al. [CHES 7428:76-91, 2012] and Božilov et al. [ToSC 2017(1):398-404, 2017], including $\mathcal{Q}_5^{25}$, which cannot be interpreted by the previous works. We also give the bijective S-boxes, which are Examples 4 to 11, that possess the optimal TIs by our results.