Source-linked AI summary
A Highly Nonlinear Differentially 4 Uniform Power Mapping That Permutes Fields of Even Degree
Carl Bracken, Gregor Leander
TL;DR
Even-degree fields have no known APN permutations, while cryptographic S-boxes need to be permutations with high nonlinearity and low differential uniformity. The paper analyzes a highly nonlinear Dobbertin power mapping and proves it has differential uniformity four, matching the inverse function’s stated resistance to linear and differential attacks.
Problem
Cryptographic S-boxes need to be permutations with high nonlinearity and low differential uniformity, but no APN permutation on an even-degree field is known.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
When k is odd, the mapping permutes the field and could be used in a cryptosystem acting on 12 bits.
Source: §4 · p. 9
Abstract
from arXiv · showhide
Functions with low differential uniformity can be used as the s-boxes of symmetric cryptosystems as they have good resistance to differential attacks. The AES (Advanced Encryption Standard) uses a differentially-4 uniform function called the inverse function. Any function used in a symmetric cryptosystem should be a permutation. Also, it is required that the function is highly nonlinear so that it is resistant to Matsui's linear attack. In this article we demonstrate that a highly nonlinear permutation discovered by Hans Dobbertin has differential uniformity of four and hence, with respect to differential and linear cryptanalysis, is just as suitable for use in a symmetric cryptosystem as the inverse function.
1 Introduction
The introduction motivates low differential uniformity and high nonlinearity for cryptographic S-boxes, then presents a Dobbertin power mapping whose differential uniformity is four and whose nonlinearity matches the inverse function’s.
1 Introduction
- Even-degree APN permutations are unknown despite APN’s optimal differential uniformity of 2; S-boxes also need to be permutations and highly nonlinear.The AES uses the inverse function, which has differential uniformity 4.Source: §1 · pp. 1–2
- Dobbertin’s list includes the highly nonlinear power mapping f(x) = x22k+2k+1 on F24k for odd k, and he conjectured the list was complete.The conjecture had been verified for n ≤ 22.Source: §1 · p. 2
- The paper proves this mapping has differential uniformity 4 and re-proves its nonlinearity, giving it the inverse function’s stated resistance to linear and differential attacks.Source: §1 · p. 2
2 Differential Uniformity of f(x) = x22k+2k+1
The paper proves that f(x) = x22k+2k+1 on F24k has differential uniformity four. Its case analysis bounds the derivative equation’s solutions, and odd k is required for the mapping to be a permutation, not for the differential-uniformity proof.
2 Differential Uniformity of f(x) = x22k+2k+1
- Differential uniformity is 4 for f(x) = x22k+2k+1 on F24k, the next-best and best-known level stated for these even-degree fields.The section notes that no even-degree permutation with differential uniformity 2 is known.Source: §2 · p. 3
- The case analysis bounds the derivative equation by at most four solutions, completing the proof of differential uniformity four.The proof reduces cases to equations with at most two solutions and combines the resulting bounds.Source: §2 · pp. 4–6
- Odd k makes the mapping a permutation; the proof of differential uniformity four does not require k to be odd.Source: §2 · p. 6
3 Nonlinearity of f(x) = x22k+2k+1
The section gives a different proof of the mapping’s nonlinearity, including when k is even and the mapping is not a permutation. The proof uses field representations and fiber-size analysis to control the relevant Fourier coefficients.
3 Nonlinearity of f(x) = x22k+2k+1
- The alternative nonlinearity proof also covers even k, when the mapping is not a permutation.Source: §3 · p. 6
- The proof switches from an F_2k basis to an F_2^2k basis, making some lengthy routine computations easier.Source: §3 · p. 6
- Restricting the Fourier-coefficient analysis to b in F_2k with Tr_k(b)=1 reduces the cases that must be studied.The proof first distinguishes odd k, when f is a bijection, from even k, when it considers b=1 and non-cubes up to equivalence.Source: §3 · p. 6
- Representing field elements as y+ωa makes the relevant expression linear in y, placing the function in generalized Maiorana–McFarland type.The construction uses α to form the extension representation.Source: §3 · pp. 6–7
- The fiber analysis gives |M| in {0, 1, 2, 4}; only the four-element case needs handling for the stated bound.Source: §3 · p. 8
4 Closing Remarks and Open Problems
The authors conclude that the mapping matches the inverse function’s resistance to differential and linear attacks and could be used in a 12-bit cryptosystem when k is odd. They leave open whether the list of power mappings is complete and whether higher-nonlinearity functions exist.
4 Closing Remarks and Open Problems
- For odd k, the mapping can permute the field and is described as having the inverse function’s resistance to differential and linear attacks, with potential 12-bit cryptosystem use.Source: §4 · p. 9
- The authors conjecture that their list of known highly nonlinear permutations with differential uniformity four is complete for power mappings.Source: §4 · p. 9
- The paper poses finding more highly nonlinear permutations of even-degree fields with differential uniformity four as an open problem.Source: §4 · p. 10
- The paper asks whether even-degree fields admit functions with nonlinearity above the stated bound, or whether such functions can be ruled out.Source: §4 · p. 10