Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension

summary

The gist

The gist The Main Theorem states that every quadratic almost perfect nonlinear permutation in odd dimension n ≥ 5 has an optimal linear equivalent, meaning there are invertible F2-linear maps L and

In short

The paper proves that every quadratic almost perfect nonlinear permutation Q in odd dimensions $n ext{ ≥ } 5$ has an optimal linear equivalent, meaning there exist invertible linear maps L and A such that the derivative of the reduced representative of L◦Q◦A has no zero and its non-empty fibers have exactly two elements. This result is significant because it shows a specific type of permutation exists that serves as a counterexample to conjectures regarding critical points.

Key concepts

Quadratic Almost Perfect Nonlinear Permutation (Q): This refers to a specific type of nonlinear function defined over the finite field $\mathbb{F}_{2^n}$. It is a polynomial whose structure is constrained by being quadratic and almost perfect, which are properties related to how the function behaves when viewed through its reduced representative in binary fields.
Optimal Linear Equivalent: This means finding invertible linear maps L and A that transform the permutation Q into a new form (L◦Q◦A) where its derivative has no zeros and all non-empty fibers have exactly two elements. This is considered an 'optimal' representative because it possesses these desirable properties related to differential uniformity.
Reduced Critical-Point Conjecture: This conjecture posits that for any APN permutation, its reduced representative must have a zero in the field. The paper shows that for odd $n \text{ ≥ } 5$, every quadratic APN permutation is linearly equivalent to a map that violates this conjecture, meaning it has no zero of its formal derivative.
Galois Ring (GR): A Galois ring is an algebraic structure used to study permutations over fields with specific characteristics. The paper connects the properties of these permutations to their behavior when lifted from the base field $\mathbb{F}_{2^n}$ to a Galois ring of characteristic $a^k$, which is crucial for understanding lifting theorems.

Terminology used across episodes

Reinforcement Learning (RL) — explained in 25 episodes
Sample Complexity — explained in 20 episodes
Retrieval-Augmented Generation (RAG) — explained in 19 episodes
Federated Learning — explained in 17 episodes
Flow Matching — explained in 17 episodes
Quantum Fisher Information (QFI) — explained in 16 episodes

This episode discusses

The paper

Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension · Read on arXiv

Hiroki Fukui

Research Institute of Criminal Psychiatry / Sex Offender Medical Center · Kyoto University

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension".

Elias: The gist The Main Theorem states that every quadratic almost perfect nonlinear permutation in odd dimension n ≥ 5 has an optimal linear equivalent,

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: We started by looking at the paper "Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension." The core thesis here is that for every quadratic almost perfect nonlinear permutation Q in an odd dimension n greater than or equal to five there exist invertible F2-linear maps L and A <ref:2610.21169#pg1,every quadratic almost perfect nonlinear permutation Q>.

Elias: And these maps L and A allow us to create a new permutation P, which is the result of L composed with Q composed with A. The crucial property they establish is that the derivative of the reduced polynomial representative of this new permutation P has no zero on F2n.

Priya: So, it's about finding a specific transformation—L and A—that makes the resulting permutation P have a nice derivative structure when we look at it over the field F2n. What is that structure supposed to mean for the overall behavior of this permutation?

Nadia: It means that this new representation P is optimal in some sense, which they call linear equivalence. They're not just finding *a* permutation; they are finding a specific form of it that satisfies these derivative conditions.

Elias: And they specify what optimality means here: the EA class of every quadratic APN permutation in odd dimension n greater than or equal to five contains an optimal representative <ref:2610.21169#pg1>. This is stronger than just saying one exists; it says *every* class has one with these properties.

Priya: That sounds like a very strong statement about the space of these permutations. Does this mean we can't have a whole family of permutations that all avoid having this nice derivative property?

Nadia: It suggests that for odd dimensions n greater than or equal to five you can always find at least one representative in any given class that has this optimal structure <ref:2610.21169#pg1>. That’s a huge structural guarantee for these specific nonlinear functions.

Elias: And they specify the condition on the derivative itself. They say that if there is some non-zero element r, then the derivative of red(P) evaluated at x equals the derivative evaluated at y if and only if y is x plus r. This pins down exactly what kind of structure that derivative has.

Priya: So, it's not just that the derivative isn't zero; it has to be very specific, tied to a single non-zero difference between inputs. That specificity is what makes this representation "optimal."

Nadia: Right. It’s about moving from a general quadratic almost perfect nonlinear permutation Q to this highly structured form P through these linear maps L and A. This paper shows that the structure isn't entirely arbitrary for dimensions five and up.

Elias: And they also address the edge cases they found earlier: for n equals three this statement fails, and for even n, there are no such permutations to consider at all because the class is empty <ref:2610.21169#pg1,and for even n, there are no such permutations>.

Conclusion: Priya: So if we wrap up what we've heard about "Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension," what's the big picture? What does it mean for someone just listening who doesn't know all the math jargon?

Nadia: Basically, this paper guarantees that if you take a quadratic almost perfect nonlinear permutation Q in an odd dimension five or higher, there is always a way to transform it using linear maps L and A into a version P where its formal derivative has no zero and has exactly two elements in its non-empty fibers.

Elias: And this means for those dimensions, we don't have to settle for any random representative; we can always find one that is structurally optimal according to these criteria. It’s about finding the best possible way to represent these functions within a certain mathematical framework.

Priya: So from a practical standpoint, it means there's this specific set of functions that are guaranteed to have this desirable derivative property for odd dimensions five and up, which is useful when we are trying to build systems or analyze their behavior over those finite fields.

Nadia: It gives us a definitive statement about the structure of these permutations in those dimensions. For n greater than or equal to nine they've even used formal verification tools to prove this existence claim holds rigorously in Lean four.

Elias: And the implication is that we have a very solid foundation for studying these functions when we consider lifting them to more complex rings, because we know the structure isn't arbitrary for these cases.

Priya: So, it boils down to confirming that for odd n greater than or equal to five there’s a specific type of representative that is optimal in terms of its derivative properties <ref:2610.21169#pg1>. That seems like a solid summary of what this paper achieves.

More episodes

← Home