**4-Uniform Permutations with Null Nonlinearity**

*Christof Beierle and Gregor Leander*

**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 \geq 5$ based on a construction in [1]. In this context, we also show that 4-uniform 2-1 functions obtained from admissible sequences, as defined by Idrisova in [8], exist in every dimension $n = 3$ and $n \geq 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$ to $\mathbb{F}_2^{n-1}$ which are not obtained from admissible sequences. This disproves a conjecture raised by Idrisova.

**Category / Keywords: **foundations / Boolean function, Cryptographic S-boxes, APN permutations, Gold functions

**Original Publication**** (in the same form): **Cryptography and Communications
**DOI: **10.1007/s12095-020-00434-2

**Date: **received 18 Mar 2020, last revised 20 Apr 2020

**Contact author: **christof beierle at rub de, gregor leander@rub de

**Available format(s): **PDF | BibTeX Citation

**Version: **20200420:060408 (All versions of this report)

**Short URL: **ia.cr/2020/334

[ Cryptology ePrint archive ]