4-uniform permutations with null nonlinearity
- PDF / 249,443 Bytes
- 9 Pages / 439.642 x 666.49 pts Page_size
- 15 Downloads / 209 Views
4-uniform permutations with null nonlinearity Christof Beierle1 · Gregor Leander1 Received: 23 August 2019 / Accepted: 27 March 2020 / © The Author(s) 2020
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 Fn2 to F2n−1 which are not obtained from admissible sequences. This disproves a conjecture raised by Idrisova. Keywords Boolean function · Cryptographic S-boxes · APN permutations · Gold functions Mathematics Subject Classification (2010) 06E30 · 94A60
1 Introduction It is well known that an APN function, i.e., a differentially 2-uniform function, must have non-trivial nonlinearity (see, e.g., [3, Prop. 13]). For functions with slightly worse differential properties, this does not necessarily need to hold. In particular, there exist differentially 4-uniform permutations with trivial nonlinearity of 0. Although this is not a new result of ours, we think that it is worth highlighting and studying such functions in more detail. For example, one possible application would be to construct other 4-uniform permutations, but
Christof Beierle
[email protected] Gregor Leander [email protected] 1
Horst G¨ortz Institute for IT Security, Ruhr-Universit¨at Bochum, Universit¨atsstraße 150, Bochum, 44801, Germany
Cryptography and Communications
with higher nonlinearity. In particular, one can reduce any permutation with trivial nonlinearity to a 2-1 function of the same uniformity and extend it back to a permutation in many possible ways. Having a function with differential uniformity d, replacing one component by a linear function trivially yields a function with differential uniformity at most 2d and null nonlinearity. However, the crucial part is that the function constructed in that way is again a permutation. We were therefore interested in the following question: Can we find APN permutations for which one component can be replaced by a linear function such that it still remains a permutation? In the first part of this work, we show that the inverses of Gold functions (see [7, 9]), i i.e., the inverses of power permutations x → x 2 +1 in F2n with gcd(i, n) = 1, have such a property. Thus, they yield a construction of 4-uniform permutations with n
Data Loading...
