A generalization of the map chi
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A generalization of the map chi".
Jane: Here's the gist of the paper. The mapping χn: Fn squared → Fn squared defined by y = χn(x) with yi = xi + xi+1xi+2 + xi+2, where the indices are computed modulo n, has been widely studied for its application in lightweight cryptography In this paper, we generalize this mapping and completely characterize all these shift-invariant permutations of algebraic degree 2.
Tom: Generalization of the Chi-map The authors introduce two new classes of nonlinear mappings, χn,v and χn,-2v, which induce permutations of Fn squared where n can be even.
Jane: The original mapping χn is a special case of χn,v when v = 1.
Tom: These new mappings have a latency lower than the recent generalization introduced by Lyu et al.
Title and authors: Jane: Now that we know the basics of the paper's focus, let’s talk about what they actually called this work: "A generalization of the map chi."
Tom: Yeah, it’s just a title, but it tells you immediately that they are taking something known—the original map chi n—and generalizing it.
Lu: The point is that the original map chi n is what we have been studying for a long time because of its use in things like Keccak-f and ASCON, which is what we started with.
Meng: So they’re taking that existing structure and exploring how much you can change it while keeping the algebraic degree low.
Jane: Right, and the generalization part is key here because they are looking for more flexibility in how we define these mappings, especially when n is even.
Tom: They specifically mention that their new classes of mappings induce permutations for even n, which is a major extension beyond the original work where it was known to be bijective only when n was odd.
Lu: That’s what they’re setting up, so they are opening the door to explore permutations in dimensions where we previously had trouble finding them.
Meng: So they are broadening the scope from just odd dimensions to even ones, and that sounds like a lot of new possibilities for cryptographic primitives.
Jane: And what makes it interesting is that they show these generalizations have a low algebraic degree, which is still just two, matching the original mapping.
Tom: That’s the takeaway for me; they aren't introducing something fundamentally new in terms of complexity class; they are just finding a different way to write and analyze existing structures.
The paper's summary: Jane: So what is this paper summarizing? Basically, it’s summarizing their process of studying all these shift-invariant mappings of algebraic degree two.
Lu: They studied every single mapping defined by chi n u v w, which is where you have that definition involving y being the sum over i from one to n of x+u + x+v(x+w + a) i equals zero.
Meng: That definition sounds complicated; they are looking at how every single coordinate of the resulting vector relates to the input coordinates.
Tom: They are essentially trying to find out exactly when this mapping P is a permutation by checking for solutions to an equation on x that starts with (x plus some delta) versus the original mapping.
Jane: So they reformulate it as checking if any non-zero difference delta has a solution to that equation, and this leads them to the simplified equation number three.
Lu: That simplification is where the real mathematical heavy lifting happens because it moves us from analyzing all n squared possibilities down to analyzing those specific linear subsystems E zero through E tau minus one <ref:2609.19548#pg1>.
Meng: So they are using this system of equations to filter out the non-permutations efficiently, which is smart for scaling.
Tom: And the summary points out that if you focus on just one subsystem E j, you can look at several cases, like when there are no zero entries in the difference vector.
Jane: That’s a practical way to handle the complexity; they aren't trying to solve every single equation simultaneously.
The paper's improvements: Tom: So what are the actual improvements they propose over what was there before? They focus on how they characterize permutations.
Lu: Their main improvement is stating that a mapping chi n u v w permutes F n squared if and only if those specific conditions involving v, w, and the differences between them hold, plus the parameter one condition.
Meng: So it moves from just being a complex definition to having a clear set of necessary and sufficient conditions for permutation.
Jane: That’s a big deal because it gives us a concrete rule—a checklist—to use when designing or verifying these functions.
Tom: And they also show that essentially all permutations they find are shift equivalent to either chi n v or chi n minus two v, which is a major simplification for classification.
Lu: That means instead of studying a huge space, we only need to study those two representative forms.
Meng: If we can confirm that our desired mapping belongs to one of those two categories, the verification becomes much faster than checking everything else.
Jane: It gives us a way to classify these low-latency permutations based on their algebraic degree and structure, which is really valuable for understanding the landscape.
Conclusion: Tom: So, to wrap up, this paper "A generalization of the map chi" shows that even though we generalized the mapping by adding parameters u, v, and w, it doesn't actually open up a whole new class of complex functions.
Jane: It confirms that the resulting permutations are highly constrained; they are essentially just variations of those two core forms, chi n v and chi n minus two v.
Lu: The real contribution is providing a complete characterization for these shift-invariant permutations, which is what gives us the theoretical foundation to study them fully.
Meng: From an engineering standpoint, it means we can build verification tools that are much more efficient because we know exactly what properties to test for.
Tom: Yeah, so the implication is that if you need a low-latency permutation of algebraic degree two, you should look at the constraints they established for v and w.
Jane: This paper gives us a clear framework for analyzing these mappings without having to check every single possibility.
Lu: It’s a nice way to connect the abstract algebra directly back to practical integer parameters.
Tom: We’ll see what happens when we try to build something using these specific rules, but this characterization is a strong starting point for designing those primitives.
Chinese Academy of Sciences · Carleton University
cs.IT, math.IT
Submitted: 2026-09-17
Updated: 2026-11-10
Comments: added a few remarks
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 78/100
The gist: The mapping χn: Fn squared → Fn squared defined by y = χn(x) with yi = xi + xi+1xi+2 + xi+2, where the indices are computed modulo n…
Key concepts
- $\chi_n$
- The original mapping studied, $\chi_n$, is a specific type of function used in cryptography. It maps vectors in $F_n^2$ to other vectors by performing additions and shifts based on indices modulo $n$. It is important because it forms the basis for many low-latency cryptographic primitives.
- Shift-invariant permutations
- These are specific types of functions that remain the same even if you shift the input vector by a fixed amount. The paper focuses on characterizing all such permutations of algebraic degree 2, which are important because they can be used to build new cryptographic systems.
- $P(x) = (x ext{ } lacktriangleright u) + (x ext{ } lacktriangleright v) \cdot (x + a)$
- This is a generalized form of the mapping being studied. It uses bitwise right shifts ($\gg$) and multiplication by another vector, combined with an addition term. Analyzing this specific structure allows researchers to determine exactly when it acts as a permutation over $F_n^2$.
- Algebraic Degree 2
- This refers to a mathematical property of the mapping's complexity. An algebraic degree of 2 is considered low, which makes these mappings attractive for lightweight cryptography because they offer good security properties while maintaining low computational latency.
Terminology
Summary
The mapping χn: Fn squared → Fn squared defined by y = χn(x) with yi = xi + xi+1xi+2 + xi+2, where the indices are computed modulo n, has been widely studied for its application in lightweight cryptography In this paper, we generalize this mapping and completely characterize all these shift-invariant permutations of algebraic degree 2. p. 0 The mapping χn : F
n
2 → F
n
2 defined by y = χn(x)
with yi = xi + xi+1xi+2 + xi+2, where the indices are computed
modulo n, has been widely studied for its application in lightweight cryptography. In this paper, we generalize this mapping
and completely characterize all these shift-invariant permutations
of algebraic degree 2.Where the paper says it
Generalization of the Chi-map
The authors introduce two new classes of nonlinear mappings, χn,v and χn,-2v, which induce permutations of Fn squared where n can be even. The original mapping χn is a special case of χn,v when v = 1. p. 2 A GENERALIZATION OF THE MAP χ 3
The original mapping χn is a special case of χn,v when v = 1. It
permutes F
n
2
if and only if n is odd. These two newly introduced
classes of nonlinear mappings induce permutations of F
n
2 where n can
be even. Moreover, their latency are lower than that of the recent
generalization introduced by Lyu et al. Moreover, their latency are lower than that of the recent
generalization introduced by Lyu et al. [9] because the algebraic degree
of our nonlinear mappings χn,v and χn,−2v is as small as 2, which equal
to the algebraic degree of the original χn. Moreover, their latency are lower than that of the recent
generalization introduced by Lyu et al. [9] because the algebraic degree
of our nonlinear mappings χn,v and χn,−2v is as small as 2, which equal
to the algebraic degree of the original χn.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Characterization of Permutations
The authors completely characterize when P(x) = χn,u,v,w(x) permutes Fn squared by stating that it permutes Fn squared if and only if 2k (v − w), u − w = 2(v − w) mod n or u − w = -(v − w) mod n, and a0 = · · · = an−1 = 1. Essentially all such permutations are shift equivalent to either χn,v or χn,-2v. p. 2 Namely, χn,u,v,w permutes F
n
2
if and only if 2k
| (v − w), u − w =
2(v − w) mod n or u − w = −(v − w) mod n, and a0 = · · · = an−1 = 1. Essentially all such permutations are shift equivalent to either χn,v or
χn,−2v.Where the paper says it
Low-latency Permutations Analysis
The authors rewrite the mapping (1) as y = P(x):= (x ≫ u) + (x ≫ v) · (x + a), where x, y, a ∈ Fn squared, and u, v, w are integers. A necessary condition for P(x) to be a permutation is that for any nonzero δ, the equation on x ((x+δ) ≫ u)+((x+δ) ≫ v)·(x+δ+a) = (x ≫ u)+(x ≫ v)·(x+a) has no solution in Fn squared. p. 2 Let 0 ̸= δ ∈ F
n
2
. Then y = P(x) is a permutation if and only if for
any nonzero δ, the equation on x
((x+δ) ≫ u)+((x+δ) ≫ v)·(x+δ+a) = (x ≫ u)+(x ≫ v)·(x+a)
has no solution in F
n
2
. Then y = P(x) is a permutation if and only if for
any nonzero δ, the equation on x
((x+δ) ≫ u)+((x+δ) ≫ v)·(x+δ+a) = (x ≫ u)+(x ≫ v)·(x+a)
has no solution in F
n
2
. The equation can be simplified to
(3) (δ ≫ v)· x + δ ·(x ≫ v) = (δ ≫ v)· δ + (δ ≫ v)· a + (δ ≫ u).Where the paper says it
Where the paper says it
Main Theorem and Conditions
Theorem 1 states that P(x) = (x ≫ u) + (x ≫ v) · (x + a) is a permutation over Fn squared if and only if the following three conditions hold: (1) 2k v; (2) u = 2v mod n or u = (n − 1)v mod n; and (3) a = 1. Corollary 3 further states that P(x) is a permutation if and only if the following three conditions hold: (1) 2k (v − w); (2) u − w = 2(v − w) mod n or u − w = -(v − w) mod n; and (3) a = 1. p. 8 Let n = 2kn0, k ≥ 0, n0 odd, and 1 ≤ u, v < n. Then
(13) P(x) = (x ≫ u) + (x ≫ v) · (x + a)
is a permutation over F
n
2
if and only if the following three conditions
holds:
(1) 2k
| v;
(2) u = 2v mod n or u = (n − 1)v mod n;
(3) a = 1.Where the paper says it
Corollary Results
Corollary 1 states that if n is even, the number of permutations P(x) of the form (13) is Nn = 2n0 − 4 if 3n0 and 2n0 − 2 if 3∤ n0. Corollary 2 concludes that if n is a power of two, then P(x) is not a permutation for any u, v and a. p. 9 □
Corollary 2. If n is a power of 2, then P(x) is not a permutation for
any u, v and a. Therefore the conclusion holds. □
Now we derive some necessary conditions on u, v, a, so that y = P(x)
is a permutation of F
n
2
.Where the paper says it
Where the paper says it
Lemma Summary
Lemma 3 proves that if P(x) = (x ≫ u) + (x ≫ v) · (x + a) is a permutation of Fn squared, then u ∈ C0. p. 5 Thus I ∩ (I + v) = ∅. □
Lemma 2. Let u ∈ C0. If P(x) = (x ≫ u) + (x ≫ v) · (x + a) is a
permutation of F
n
2
, then a = 1, the all one vector. Let u ∈ C0. If P(x) = (x ≫ u) + (x ≫ v) · (x + a) is a
permutation of F
n
2
, then a = 1, the all one vector. A GENERALIZATION OF THE MAP χ 9
Lemma 5. Let n = 2kn0, k ≥ 0, n0 odd, u ∈ C0 and a = 1.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
References
[1] S. Andreoli, G. p. 9 References
[1] S. Andreoli, G. References
[1] S. Andreoli, G. Andreoli, G. Leander, E. Andreoli, G. Leander, E. Leander, E. Piccione, L. Leander, E. Piccione, L. Piccione, L. Stenne, Generalizations of ChiChi:
Families of low-latency permutations in any even dimension, IACR Trans. Piccione, L. Stenne, Generalizations of ChiChi:
Families of low-latency permutations in any even dimension, IACR Trans. Stenne, Generalizations of ChiChi:
Families of low-latency permutations in any even dimension, IACR Trans. Symmetric Cryptol. Stenne, Generalizations of ChiChi:
Families of low-latency permutations in any even dimension, IACR Trans. Symmetric Cryptol. Stenne, Generalizations of ChiChi:
Families of low-latency permutations in any even dimension, IACR Trans. Symmetric Cryptol. Stenne, Generalizations of ChiChi:
Families of low-latency permutations in any even dimension, IACR Trans. Symmetric Cryptol. Symmetric Cryptol. , 2025, no. Symmetric Cryptol. , 2025, no.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[3] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, KECCAK specifications, National Institute of Standards and Technology, Federal Information Processing Standards Publication, 2008
[4] J. Daemen, Cipher and Hash Function Design Strategies based on linear and differential cryptanalysis, Katholieke Universiteit Leuven, PhD Dissertation, 1995
[5] A. Graner, B. Kriepke, L. p. 1 Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . 19548v1 [cs. IT] 17 Sep 2026 19548v1 [cs. IT] 17 Sep 2026Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[6] B. Kriepke and G. p. 1 Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, . Various variations and generalizations of χn have been studied in
[1, 2, 7, 6, 9, 12]. For example, for odd n, Kriepke and Kyureghyan [6]
showed that all iterates of χn can be expressed as linear combinations
of the mappings γ2k for k ≥ 1, where the i-th coordinate of γ2k is
yi = xi+2k(xi+2k−1 + 1)(xi+2k−3 + 1)· · ·(xi+1 + 1), i ∈ {0, .Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[7] B. Kriepke and G. Kyureghyan, There are siblings of χ which are permutations for n even, https://arxiv. p. 1 This
isomorphism enables both theoretical and algorithmic constructions of
a rich family of shift-invariant permutations and reduces the study of
their properties to corresponding binary polynomials. For even n, Kriepke and Kyureghyan [7] showed that the subset of
bijections in Γn forms an abelian group isomorphic to the unit group
of F2[X]/(Xn + Xn/2
). This
isomorphism enables both theoretical and algorithmic constructions of
a rich family of shift-invariant permutations and reduces the study of
their properties to corresponding binary polynomials. For even n, Kriepke and Kyureghyan [7] showed that the subset of
bijections in Γn forms an abelian group isomorphic to the unit group
of F2[X]/(Xn + Xn/2
).Where the paper says it
Where the paper says it
[8] F. Liu, S. Sarkar, W. Meier, T. Isobe, The inverse of χ and its applications to Rasta-like ciphers, J. p. 1 Their approach was further adapted by Lyu et
al. [9] to construct χ-like permutations. Their approach was further adapted by Lyu et
al. [9] to construct χ-like permutations. The mapping χn : F
n
2 → F
n
2 defined by y = χn(x)
with yi = xi + xi+1xi+2 + xi+2, where the indices are computed
modulo n, has been widely studied for its application in lightweight cryptography. In this paper, we generalize this mapping
and completely characterize all these shift-invariant permutations
of algebraic degree 2.Where the paper says it
Where the paper says it
Where the paper says it
[9] C. Lyu, M. Yuan, D. Zheng, S. Sun, Li, Shun, A generalized χn-function, IEEE Trans. p. 1 [9] to construct χ-like permutations. They introduced a generalized
class of mappings χn,m defined by y = χn,m(x), where
yi = xi + xi+m(xi+m−1 + 1)(xi+m−2 + 1)· · ·(xi+1 + 1). [9] to construct χ-like permutations. They introduced a generalized
class of mappings χn,m defined by y = χn,m(x), where
yi = xi + xi+m(xi+m−1 + 1)(xi+m−2 + 1)· · ·(xi+1 + 1). 19548v1 [cs. IT] 17 Sep 2026 19548v1 [cs. IT] 17 Sep 2026Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[10] NIST, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, National Institute of Standards and Technology, Federal Information Processing Standards Publication, FIPS PUB 202, 2015
[11] NIST, Ascon-Based Lightweight Cryptography Standards for Constrained Devices: Authenticated Encryption, Hash, and Extendable Output Functions, National Institute of Standards and Technology, Federal Information Processing Standards Publication, NIST SP 800-232, 2025
[12] S. Rasoolzadeh, Low-latency Boolean functions and bijective S-boxes, IACR Trans. p. 9 Piccione, L. Stenne, Generalizations of ChiChi:
Families of low-latency permutations in any even dimension, IACR Trans. Piccione, L. Stenne, Generalizations of ChiChi:
Families of low-latency permutations in any even dimension, IACR Trans.Where the paper says it
Where the paper says it
[13] J. Schoone, J. p. 0 [8]; for odd n > 0, it is given by
xi = yi +
(nX−1)/2
j=1
yi−2j+1
(nY−1)/2
k=j
(yi−2k + 1),
with indices computed modulo n. The order and cycle structure of χn are also known; see Schoone and
Daemen [13]. In this paper, we generalize this mapping
and completely characterize all these shift-invariant permutations
of algebraic degree 2. Introduction
In order to find a shift-invariant transformation over F
n
2
that is easy
to implement and has good cryptographic properties, Daemen [4] introduced a mapping χn : F
n
2 → F
n
2 defined by y = χn(x) with
yi = xi + xi+1xi+2 + xi+2, 1 ≤ i ≤ n,
where the indices are computed modulo n.Where the paper says it
Where the paper says it
[arXiv:2609.19548v1] [cs. p. 0 1
arXiv:2609. 19548v1 [cs. 1
arXiv:2609. 19548v1 [cs.Where the paper says it
Where the paper says it
--- Page 3 ---
The original mapping χn is a special case of χn,v when v = 1. It permutes Fn squared if and only if n is odd. p. 2 A GENERALIZATION OF THE MAP χ 3
The original mapping χn is a special case of χn,v when v = 1. It
permutes F
n
2
if and only if n is odd. It
permutes F
n
2
if and only if n is odd. These two newly introduced
classes of nonlinear mappings induce permutations of F
n
2 where n can
be even. These two newly introduced
classes of nonlinear mappings induce permutations of F
n
2 where n can
be even. Moreover, their latency are lower than that of the recent
generalization introduced by Lyu et al.Where the paper says it
Where the paper says it
Where the paper says it
How the training signal is built
The authors study all these shift-invariant mappings of algebraic degree 2. Let χn,u,v,w: Fn squared → Fn squared defined by y = χn,u,v,w(x) with (1) yi = xi+u + xi+v(xi+w + ai), 1 ≤ i ≤ n. p. 1 Let 1 ≤ u, v < n. Define χn,v : F
n
2 →
F
n
2
, defined by y = χn,v(x) with
yi = xi + xi+vxi+2v + xi+2v, 1 ≤ i ≤ n,
Then we will show that χn,v permutes F
n
2
if and only if 2k
| v. Let
χn,u,v,w : F
n
2 → F
n
2 defined by y = χn,u,v,w(x) with
(1) yi = xi+u + xi+v(xi+w + ai), 1 ≤ i ≤ n,
We completely characterize when P(x) = χn,u,v,w(x) permutes F
n
2
. Namely, χn,u,v,w permutes F
n
2
if and only if 2k
| (v − w), u − w =
2(v − w) mod n or u − w = −(v − w) mod n, and a0 = · · · = an−1 = 1.Where the paper says it
Where the paper says it
Where the gains come from
The analysis of the equation on x ((x+δ) ≫ u)+((x+δ) ≫ v)·(x+δ+a) = (x ≫ u)+(x ≫ v)·(x+a) leads to the simplification to (3): (δ ≫ v)· x + δ ·(x ≫ v) = (δ ≫ v)· δ + (δ ≫ v)· a + (δ ≫ u), which is rewritten in bit form using the following system of linear equations: (4): δi+vxi + δixi+v = δi+vδi + δi+vai + δi+u, i = 0, 1, · · ·, n − 1. The analysis of Eqn. p. 3 Denote
Tj =
[
i∈Dj
Ci
for 0 ≤ j < τ . Then we can divide Eqn. Then we can divide Eqn. (4) into τ independent
subsystems E0, · · · , Eτ−1, and for each subsystem Ej
, the subscripts of
its all parameters x, δ, a are in Tj
:
(5) Ej
: δi+vxi + δixi+v = δi+vδi + δi+vai + δi+u, i ∈ Tj
.Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The authors focus on one subsystem Ej for some j. They consider several cases so that Eqn. p. 3 We can further focus on the
subsystem
(6) δi,t+1xi,t + δi,txi,t+1 = δi,tδi,t+1 + δi,t+1ai,t + δj,s+t
,
where t = 0, 1 · · · , l − 1, j = i + u mod d and s = (i+u−j
d
)( v
d
)
−1 mod l. Below we consider the following cases so that Eqn. (6) has a solution. (a) If |Ci
| = 2, then it is easy to check that Eqn. (a) If |Ci
| = 2, then it is easy to check that Eqn. (6) always has
two solutions for any nonzero δCi
. (6) always has
two solutions for any nonzero δCi
. (b) If there is no zero entry in δCi
, i. (a) If |Ci
| = 2, then it is easy to check that Eqn. (6) always has
two solutions for any nonzero δCi
. , δCi = (11 · · · 1), then Eqn. (6) is written simply as
xi,t + xi,t+1 = 1 + ai,t + δj,s+t
, t = 0, 1 · · · , l − 1,
and it has at least one solutions if and only if
(7) X
l−1
t=0
ai,t ≡
X
l−1
t=0
δj,t + |Ci
| mod 2.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Lemma 1 proves that if gcd(v, n)∤ u, then there exists a nonempty set I ⊆ Zn such that (I + u) ⊆ I ∪ (I + v). Lemma 2 shows the existence of a cycle with specific properties under certain conditions. p. 0 The order and cycle structure of χn are also known; see Schoone and
Daemen [13]. They further studied algebraic properties of this map via
a univariate polynomial representation under the isomorphism F2n ∼=
F
n
2
. Let n = 2kn0, k ≥ 0, n0 odd, and 1 ≤ u, v < n. Then
(13) P(x) = (x ≫ u) + (x ≫ v) · (x + a)
is a permutation over F
n
2
if and only if the following three conditions
holds:
(1) 2k
| v;
(2) u = 2v mod n or u = (n − 1)v mod n;
(3) a = 1.Where the paper says it
Where the paper says it
[1] S. Andreoli, G. Leander, E. Piccione, L. Stenne, Generalizations of ChiChi: Families of low-latency permutations in any even dimension, IACR Trans. Symmetric Cryptol., 2025, no. 3, 800-826
[3] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, KECCAK specifications, National Institute of Standards and Technology, Federal Information Processing Standards Publication, 2008
[4] J. Daemen, Cipher and Hash Function Design Strategies based on linear and differential cryptanalysis, Katholieke Universiteit Leuven, PhD Dissertation, 1995
[5] A. Graner, B. Kriepke, L. Krompholz, G. Kyureghyan,, On the bijectivity of the map χ, Cryptogr. Commun. 18 (2026), no. 1, 97-105
[6] B. Kriepke and G. M. Kyureghyan, Algebraic structure of the iterates of χ, in Advances in cryptology—CRYPTO 2024. Part IV, 412–424, Lecture Notes in Comput. Sci., 14923, Springer, Cham
[7] B. Kriepke and G. Kyureghyan, There are siblings of χ which are permutations for n even, https://arxiv.org/pdf/2509.24839
[8] F. Liu, S. Sarkar, W. Meier, T. Isobe, The inverse of χ and its applications to Rasta-like ciphers, J. Cryptology 35 (2022), no. 4
[9] C. Lyu, M. Yuan, D. Zheng, S. Sun, Li, Shun, A generalized χn-function, IEEE Trans. Inform. Theory 72 (2026), no. 4
[10] NIST, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, National Institute of Standards and Technology, Federal Information Processing Standards Publication, FIPS PUB 202, 2015
[11] NIST, Ascon-Based Lightweight Cryptography Standards for Constrained Devices: Authenticated Encryption, Hash, and Extendable Output Functions, National Institute of Standards and Technology, Federal Information Processing Standards Publication, NIST SP 800-232, 2025
[12] S. Rasoolzadeh, Low-latency Boolean functions and bijective S-boxes, IACR Trans. Symmetric Cryptol., 2022, no. 3, 403-447
[arXiv:2609.19548v1] [cs.IT] 17 Sep 2026
--- Page 4 ---
Let d = gcd(v, n), τ = gcd(d, u) and n = dl. We define Ci =, i = 0, 1, · · ·, d − 1 and Dj = (j + tu)mod d t = 0, 1, …, d−1 j = 0,. p. 2 Let d = gcd(v, n), τ = gcd(d, u) and n = dl. We define
Ci = {(i + tv)mod n |t = 0, 1, · · · , l − 1} , i = 0, 1, · · · , d − 1Where the paper says it
--- Page 6 ---
The resulting closed walk W′ still contains j and has the same minimum length. However, the number of changes of step type in the walk W′ is four, whereas that of W is two. p. 5 The resulting closed walk W′
still contains j and has the same minimum
length. However, the number of changes of step type in the walk W′
is four, whereas that of W is two.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Generalized shift-invariant permutations can be used in lightweight cryptography by constructing mappings such as P(x) = (x >> u) + (x >> v) · (x + a). This allows for the creation of new cryptographic primitives whose security relies on the properties derived from Theorem 1, specifically when conditions like 2k v, u = 2v mod n or u = (n − 1)v mod n, and a = 1 are met.
-
The analysis provides a method to determine if a given polynomial map P(x) permutes F(n 2) by checking for solutions to linear equations derived from the mapping's definition. This allows AI systems to verify the permutation property of custom functions used in lightweight encryption schemes efficiently, as shown in Lemma 4 and Theorem 1.
-
The research establishes a relationship between the structure of a permutation P(x) and the parameters u, v, w, suggesting that
essentially all such permutations are shift equivalent to either chi(n,v) or chi(-2v)
. This insight can be used in AI to classify different types of low-latency permutations based on their algebraic degree and structure.
Abstract
The mapping χ n: F 2 n to F 2 n defined by y=χ n(x) with y i = x i + x i+1x i+2 + x i+2, where the indices are computed modulo n, has been widely studied for its application in lightweight cryptography. In this paper, we generalize this mapping and completely characterize all these shift-invariant permutations of the form y i=x i+u+x i+v(x i+w+a i), where 0 at most u, v, w<n and a i in F 2, 1 at most i at most n. We also determine their compositional inverses explicitly.
Sources
Related papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Electromagnetic Signal and Information Theory: A Continuous-Aperture Array Perspective
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound