4-uniform permutations with null nonlinearity

Abstract

Abstract We consider n -bit permutations with differential uniformity of 4 and null nonlinearity. We first show that the inverses of Gold functions have the interesting property that one component can be replaced by a linear function such that it still remains a permutation. This directly yields a construction of 4-uniform permutations with trivial nonlinearity in odd dimension. We further show their existence for all n = 3 and n ≥ 5 based on a construction in Alsalami (Cryptogr. Commun. 10 (4): 611–628, 2018). In this context, we also show that 4-uniform 2-1 functions obtained from admissible sequences , as defined by Idrisova in (Cryptogr. Commun. 11 (1): 21–39, 2019), exist in every dimension n = 3 and n ≥ 5. Such functions fulfill some necessary properties for being subfunctions of APN permutations. Finally, we use the 4-uniform permutations with null nonlinearity to construct some 4-uniform 2-1 functions from $\mathbb {F}_{2}^{n}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mrow> <mml:mi>F</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:msubsup> </mml:math> to $\mathbb {F}_{2}^{n-1}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mrow> <mml:mi>F</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msubsup> </mml:math> which are not obtained from admissible sequences. This disproves a conjecture raised by Idrisova.

Topics & Concepts