A Notion on S-Boxes for a Partial Resistance to Some Integral Attacks
摘要
Recently, the notion of kth-order sum-freedom of a vectorial function \(F:\mathbb F_2^n\rightarrow \mathbb F_2^m\) has been introduced, generalizing that of almost perfect nonlinearity (which corresponds to \(k=2\) ) and having some relation to resistance against integral attacks on block ciphers, by preventing the propagation of the division property of k-dimensional affine spaces. In the present paper, we show that this notion, which is rarely satisfied by vectorial functions, can be weakened while retaining the same behavior with respect to the division property. This leads us to the notion of kth-order t-degree-sum-freedom, whose strength decreases as t increases, and which coincides with kth-order sum-freedom when \(t=1\) : for every k-dimensional affine space A, there exists a non-negative integer j of 2-weight at most t such that \(\sum _{x\in A}(F(x))^j\ne 0\) . We show that t can always be taken smaller than or equal to \(\min (k,m)\) under some “reasonable” condition on F (satisfied in particular by all injective functions). This makes the new notion more interesting theoretically and practically than sum-freedom (which is an all-or-nothing notion and which in practice disqualifies almost all functions). The parameter t in the new notion quantifies more precisely the behavior of any “reasonable” function. A quality of this parameter is its simplicity. We also show that t is greater than or equal to \(\frac{k}{\deg (F)}\) , where \(\deg (F)\) is the algebraic degree of F, and we derive two other lower bounds. We study power functions, for which we prove upper bounds. Among them, we study the multiplicative inverse function (used as an S-box in the AES), for which we characterize the kth-order t-degree-sum-freedom by the coefficients of the subspace polynomials of k-dimensional vector subspaces (deducing the exact minimal value of t when k divides n) and we prove that its kth-order t-degree-sum-freedom is equivalent to its \((n-k)\) th-order t-degree-sum-freedom.