Cryptology ePrint Archive: Report 2020/334

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

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:

[ Cryptology ePrint archive ]