On CCZ-Equivalence of the Inverse Function
Lukas Kölsch · IEEE Transactions on Information Theory · 2021
The inverse function x → x-1on \mathbb F2nis one of the most studied functions in cryptography due to its widespread use as an S-box in block ciphers like AES. In this paper, we show that, if n ≥ 5, every function that is CCZ-equivalent to the inverse function is already EA-equivalent to it. This confirms a conjecture by Budaghyan, Calderini and Villa. We also prove that every permutation that is CCZ-equivalent to the inverse function is already affine equivalent to it. The majority of the paper is devoted to proving that there is no permutation polynomial of the form L1(x-1)+L2(x) over \mathbb F2nif n ≥ 5, where L1,L2are nonzero linear functions. In the proof, we combine Kloosterman sums, quadratic forms and tools from additive combinatorics.