Algebraic Structure of the Iterates of χ
Bj¨orn Kriepke1 and Gohar Kyureghyan1
Institute of Mathematics, University of Rostock, Germany
{bjoern.kriepke, gohar.kyureghyan}@uni-rostock.de
Abstract. We consider the map χ : Fn
2 →Fn
2 for n odd given by
y = χ(x) with yi = xi + xi+2(1 + xi+1), where the indices are com-
puted modulo n. We suggest a generalization of the map χ which we call
generalized χ-maps. We show that these maps form an Abelian group
which is isomorphic to the group of units in F2[X]/(X(n+1)/2). Using
this isomorphism we easily obtain closed-form expressions for iterates of
χ and explain their properties.
1
Introduction
Consider the map χ : Fn
2 →Fn
2 given by y = χ(x) where yi = xi+xi+2(1+xi+1).
It is known that χ is a permutation if and only if n is odd [2]. Therefore, in this
paper we assume that n is odd.
The map χ is used in several cryptographic primitives, for example in SHA-3
[6] and Ascon [3]. A number of recent papers contributed to a better understand-
ing of cryptological properties of the map χ, see for example [5,7,8].
In this paper we study the iterates of χ, that is χj = χ ◦. . . ◦χ. We observe
that these iterates are linear combinations of special maps which we call γ2k
for k ≥0. Then we consider the set Γ of all linear combinations of the maps
γ2k for k ≥0 and show that these maps have strong arithmetic properties. We
show that a subset G ⊆Γ forms an Abelian group with respect to composition.
This group is isomorphic to the group of units of the ring F2[X]/(X(n+1)/2) in
a straightforward way. Furthermore the iterates of χ are elements of G. This
isomorphism explains in a direct way some properties of χ and its iterates.
We expect, that our results can be used to get more insights on security of
cryptological applications based on χ.
The paper is structured as follows: In Section 2 we start by computing the first
iterates of χ. This gives an insight into why the maps γ2k are important subjects
to study in this context. In Section 3 we consider the vector space Γ spanned
by γ2k for k ≥0 and study a certain subset G ⊆Γ consisting of bijective maps.
In Section 4 we apply the results of the previous section to describe properties
of some special maps from G, including χ.
© IACR 2024. This article is the final version submitted by the author(s) to the IACR
and to Springer-Verlag on May 23, 2024. The version published by Springer-Verlag
will be available later.
2
Warm-up: Iterates of χ
As a warm-up, we start by computing the first few iterates of χ. Let x ∈Fn
2 and
set x(j) = χj(x) for j ≥1. Then x(2) = χ1(x(1)) is given by
x(2)
i
= x(1)
i
+ x(1)
i+2 · (1 + x(1)
i+1)
= xi + xi+2 · (1 + xi+1)
+ (xi+2 + xi+4 · (1 + xi+3)) · (1 + (xi+1 + xi+3 · (1 + xi+2))),
using the definition of x(1) = χ(x). We pay special attention to the last summand.
Note that xi+2 ·(1+xi+2) = 0 because xi+2 ∈F2. Similarly, (1+xi+3)·xi+3 = 0.
We obtain
(xi+2 + xi+4 · (1 + xi+3)) · (1 + (xi+1 + xi+3 · (1 + xi+2)))
= (xi+2 + xi+4 · (1 + xi+3)) · ((1 + xi+1) + xi+3 · (1 + xi+2))
= xi+2 · (1 + xi+1) + xi+2 · xi+3 · (1 + xi+2)
|
{z
}
=0
+ xi+4 · (1 + xi+3) · (1 + xi+1) + xi+4 · (1 + xi+3) · xi+3 · (1 + xi+1)
|
{z
}
=0
= xi+2 · (1 + xi+1) + xi+4 · (1 + xi+3) · (1 + xi+1)
and hence
x(2)
i
= xi + xi+2 · (1 + xi+1) + xi+2 · (1 + xi+1) + xi+4 · (1 + xi+3) · (1 + xi+1)
= xi + xi+4 · (1 + xi+3) · (1 + xi+1).
In a similar manner we can compute x(3) and x(4) and obtain
x(3)
i
= xi + xi+2 · (1 + xi+1) + xi+4 · (1 + xi+3) · (1 + xi+1)
+ xi+6 · (1 + xi+5) · (1 + xi+3) · (1 + xi+1)
x(4)
i
= xi + xi+8 · (1 + xi+7) · (1 + xi+5) · (1 + xi+3) · (1 + xi+1).
For k ≥1 we define the map γ2k(x) with y = γ2k(x) given by
yi = xi+2k · (1 + xi+2k−1) · (1 + xi+2k−3) · · · (1 + xi+1)
for all indices i = 1, . . . , n. Then notice that we can write χj for j = 1, 2, 3, 4 in
the following form:
χ(x) = x + γ2(x)
χ2(x) = x
+ γ4(x)
χ3(x) = x + γ2(x) + γ4(x) + γ6(x)
χ4(x) = x
+ γ8(x).
2
If we put γ0 to denote the identity map, then the above calculations show that
the first iterates of χ are linear combinations of γ2k over F2. In the following
section we confirm this observation for all iterates of χ by showing the following
theorem. Let j = j0 +2j1 +22j2 +. . .+2sjs and k = k0 +2k1 +22k2 +. . .+2sks
be two integers, written in base 2. Write j ⪯k if for all i = 0, . . . , s it holds
that ji ≤ki. Equivalently, ji = 1 implies ki = 1. In such cases we say that j is
covered by k.
Theorem 1. Let k ≥1. Then
χk =
min{k,(n−1)/2}
X
j=0
ajγ2j
with aj = 1 if and only if j ⪯k. The algebraic degree of χk is j + 1 with the
largest j ≤(n −1)/2 such that j ⪯k.
3
Vector space Γ generated by maps γ2k
Motivated by the computations in the previous section we consider the linear
span of the maps γ2k for k ≥0. We start by defining some notation which was
partly introduced in [4].
We denote the vector (1, . . . , 1) ∈Fn
2 by 1l. Let S : Fn
2 →Fn
2 be the cyclic
left shift operator, i.e., S(x1, . . . , xn) = (x2, . . . , xn, x1). With the symbol ⊙we
denote the elementwise multiplication of two vectors x, y ∈Fn
2, which is also
called the Hadamard product. More precisely, z = x ⊙y denotes the vector with
zi = xi · yi for all i = 1, . . . , n. Note that S is linear. Furthermore, S(x ⊙y) =
S(x) ⊙S(y). The Hadamard product ⊙is commutative and distributive over
addition, that is, x ⊙y = y ⊙x and x ⊙(y + z) = x ⊙y + x ⊙z.
Note that for any y ∈Fn
2 we have y ⊙(1l + y) = 0. In particular also
Sj ⊙(1l + Sj) = 0
for every j ≥0.
Observe that for 2k ≥2 the previously defined maps γ2k : Fn
2 →Fn
2 are given
by
γ2k = S2k ⊙(1l + S2k−1) ⊙(1l + S2k−3) ⊙. . . ⊙(1l + S1),
and γ0 = S0 = id is the identity map. With this notation, we have
χ = id +S2 ⊙(1l + S) = γ0 + γ2.
3.1
Some basic observations on the maps γ2k
Remark 1. Let x ∈Fn
2 and y = γ2k(x) for k ≥1. Then the components of y are
given by
yi = xi+2k · (1 + xi+2k−1) · (1 + xi+2k−3) · . . . · (1 + xi+1).
Therefore yi = 1 if and only if (xi+1, . . . , xi+2k) = (0, ∗, 0, ∗, . . . , 0, ∗, 0, 1) where
we put ∗to denote an arbitrary element in F2.
3
The next two lemmas imply in particular that the set of the maps γ2k : Fn
2 →
Fn
2, k ≥0, contains exactly (n + 1)/2 nonzero functions.
Lemma 1. Let 2k > n. Then γ2k = 0.
Proof. Consider the function γ2k with 2k > n. Then S2k = S2k−n and 2k −n is
odd. Therefore
γ2k = S2k−n ⊙(1l + S2k−1) ⊙(1l + S2k−3) ⊙. . . ⊙(1l + S2k−n) ⊙. . . ⊙(1l + S)
= S2k−n ⊙(1l + S2k−n) ⊙(. . .) = 0.
⊓⊔
Recall that the algebraic degree of a map f : Fn
2 →Fn
2 is the maximal
multivariate degree of its component functions.
Lemma 2. Let 0 ≤2k < n. Then the algebraic degree of γ2k is k + 1. In
particular, the maps γ0, γ2, . . . , γn−1 are linear independent over F2.
Proof. If k = 0 then γ2k = γ0 = id and the claim is clear. The entries of
y = γ2k(x) for k = 1, . . . , (n −1)/2 are given by
yi = xi+2k · (1 + xi+2k−1) · (1 + xi+2k−3) · · · (1 + xi+1).
As all variables xj appearing in the product are distinct it follows that the
algebraic degree of γ2k is k + 1.
⊓⊔
Next we study the set of linear combinations of maps γ2k, k ≥0, which we
denote by Γ, i.e.
Γ =
( ℓ
X
k=0
akγ2k : ak ∈F2, ℓ∈N0
)
=



(n−1)/2
X
k=0
akγ2k : ak ∈F2



where the second equality follows directly from Lemma 1. Recall that N0 =
{0, 1, 2, 3, . . .} is the set of natural numbers including 0.
Lemma 3. Γ is a vector space over F2 of dimension (n + 1)/2 with basis
{γ0, γ2, . . . , γn−1}.
Proof. It is clear that Γ is a subspace of the space V of all functions on Fn
2.
Lemma 2 immediately implies that {γ0, γ2, . . . , γn−1} is a basis of Γ. The di-
mension of Γ follows.
⊓⊔
3.2
Composition of maps in Γ
Later we show that the composition of certain elements in Γ remains in Γ. For
this we need some preliminary results which are stated in the next several lem-
mas. We start with the following observation which is crucial for having nice
closed formulas for these compositions.
We write Smγ2k to denote the composition Sm ◦γ2k.
4
Lemma 4. Let k ≥0 and j, m ≥1. Then it holds that
Smγ2k ⊙Sm−1γ2j = 0.
Proof. First assume k ≥1. Let us write out what Smγ2k and Sm−1γ2j are. We
have
Smγ2k = S2k+m ⊙(1l + S2k+m−1) ⊙. . . ⊙(1l + Sm+3) ⊙(1l + Sm+1)
Sm−1γ2j = S2j+m−1 ⊙(1l + S2j+m−2) ⊙. . . ⊙(1l + Sm+2) ⊙(1l + Sm).
Note that 2k + m and 2j + m −1 have a different parity. Further note that
2j + m −1 ≥m + 1 and 2k + m ≥m because j ≥1 and k ≥0, respectively.
If 2j −1 < 2k, then m + 1 ≤2j + m −1 < 2k + m and the term 1l + S2j+m−1
appears in Smγ2k. Using the commutativity of ⊙and that y ⊙(1l + y) = 0 for
all y ∈Fn
2 it follows that
Smγ2k ⊙Sm−1γ2j = S2j+m−1 ⊙(1l + S2j+m−1) ⊙(. . .) = 0.
Similarly, if 2k < 2j −1, then m ≤2k +m < 2j +m−1 and the term 1l+S2k+m
appears in Sm−1γ2j and they cancel out by the same argument.
For k = 0 we have Smγ2k = Smγ0 = Sm and the term 1l + Sm appears in
Sm−1γ2j. Again by the same argument as above we get Smγ2k ⊙Sm−1γ2j = 0.
⊓⊔
Lemma 5. Let m ≥2 be even and k ≥1. Then we have
Smγ2k ⊙(1l + Sm−1) = Sm−2γ2k+2.
Proof. Remember that S(1l) = 1l and that S(x ⊙y) = S(x) ⊙S(y). It follows
that
Smγ2k = Sm  S2k ⊙(1l + S2k−1) ⊙(1l + S2k−3) ⊙. . . ⊙(1l + S)

= Sm+2k ⊙(1l + Sm+2k−1) ⊙(1l + Sm+2k−3) ⊙. . . ⊙(1l + Sm+1)
and then
Smγ2k ⊙(1l + Sm−1)
= Sm+2k ⊙(1l + Sm+2k−1) ⊙(1l + Sm+2k−3) ⊙. . . ⊙(1l + Sm+1) ⊙(1l + Sm−1)
= Sm−2  S2k+2 ⊙(1l + S2k+1) ⊙(1l + S2k−1) ⊙. . . ⊙(1l + S3) ⊙(1l + S)

= Sm−2γ2k+2.
⊓⊔
Lemma 6. Let m be even, f = Pk
i=0 aiγ2i ∈Γ and g = γ0 + Ps
j=1 bjγ2j ∈Γ.
Then
Sm(f) ⊙(1l + Sm−1(g)) = Sm−2
 k
X
i=0
aiγ2i+2
!
with ˜f = Pk
i=0 aiγ2i+2 ∈Γ.
5
Proof. We have
Sm(f) ⊙(1l + Sm−1(g))
= Sm
 k
X
i=0
aiγ2i
!
⊙

1l + Sm−1

γ0 +
s
X
j=1
bjγ2j




= Sm
 k
X
i=0
aiγ2i
!
⊙(1l + Sm−1γ0) + Sm
 k
X
i=0
aiγ2i
!
⊙

Sm−1


s
X
j=1
bjγ2j




=
k
X
i=0
ai Smγ2i ⊙(1l + Sm−1)
|
{z
}
=Sm−2γ2i+2
+
k
X
i=0
s
X
j=1
aibj Smγ2i ⊙Sm−1γ2j
|
{z
}
=0
= Sm−2
 k
X
i=0
aiγ2i+2
!
where we use Lemma 4 and Lemma 5.
⊓⊔
Let C be the subspace
C = ⟨γ2, γ4, . . . , γn−1⟩
and G be the coset
G = γ0 + C.
Observe that Lemma 6 only holds for maps g ∈G and not for all g ∈Γ.
Since χ = γ0 + γ2 we have χ ∈G. Therefore we call the maps g ∈G
generalized χ-maps. The next lemma gives a closed formula for the composition
of the maps γ2k with elements in G.
Lemma 7. Let m ≥2 be even and f = γ0 + Pk
i=1 aiγ2i ∈G. Then
γm ◦f =
k
X
i=0
aiγ2i+m ∈C.
Proof. We use Lemma 6 repeatedly. More precisely,
γm ◦f = [Sm ⊙(1l + Sm−1) ⊙(1l + Sm−3) ⊙. . . ⊙(1l + S)] ◦f
= Smf ⊙(1l + Sm−1f) ⊙(1l + Sm−3f) ⊙. . . ⊙(1l + Sf)
= Sm−2
 k
X
i=0
aiγ2i+2
!
⊙(1l + Sm−3f) ⊙(1l + Sm−5f) ⊙. . . ⊙(1l + Sf)
= Sm−4
 k
X
i=0
aiγ2i+4
!
⊙(1l + Sm−5f) ⊙. . . ⊙(1l + Sf) = . . . =
=
k
X
i=0
aiγ2i+m.
⊓⊔
6
Remember that a monoid (M, ∗) is a set together with an associative oper-
ation ∗: M × M →M such that there exists a neutral element e ∈M with
respect to ∗.
Theorem 2. Let f, g ∈G. Then f ◦g ∈G. In particular G is a monoid with
respect to composition.
Proof. Write f = γ0 + Pk
i=1 aiγ2i and g = γ0 + Ps
j=1 bjγ2j. Then
f ◦g =
 
γ0 +
k
X
i=1
aiγ2i
!
◦g
= γ0 ◦g
| {z }
=g
+
 k
X
i=1
aiγ2i
!
◦g
= γ0 +
s
X
j=1
bjγ2j
|
{z
}
∈C
+
k
X
i=1
ai γ2i ◦g
| {z }
∈C
∈γ0 + C = G
where we use Lemma 7 to conclude that γ2i ◦g ∈C for i = 1, . . . , k.
Note that G contains the identity γ0 which is a neutral element with re-
gards to composition. Furthermore composition is associative. Hence (G, ◦) is a
monoid.
⊓⊔
Remark 2. Note that Γ is not closed under composition.
If f ∈C = Γ \ G and g ∈G then f ◦g ∈C. For example, γ2 ◦(γ0 + γ2) =
γ2 + γ4 ∈C by Lemma 7. The general case f = Pk
i=1 aiγ2i follows by left-
distributivity of ◦, i.e. (f + g) ◦h = f ◦h + g ◦h, and C being a vector space.
However, if g ∈C, then it can happen that f ◦g /∈Γ. For example, if
f = γ2 ∈C, then
γ2 ◦γ2 = (S2 ⊙(1l + S)) ◦(S2 ⊙(1l + S))
= S4 ⊙(1l + S3) ⊙(1l + S3 ⊙(1l + S2))
= S4 ⊙(1l + S3) + S4 ⊙(1l + S3) ⊙S3 ⊙(1l + S2)
= S4 ⊙(1l + S3) /∈Γ
and also for f = γ0 + γ2 ∈G it follows that
(γ0 + γ2) ◦γ2 = γ2 + S4 ⊙(1l + S3) /∈Γ.
3.3
A connection between Γ and a quotient ring of F2[X]
Next we show that the monoid (G, ◦) is in fact an Abelian group. We achieve this
by showing that it is isomorphic as a monoid to an Abelian group. In particular
this implies that all maps in G are permutations of Fn
2. Note that from Lemma 7
7
the composition of maps in G is reminiscent of polynomial multiplication, hence
we could hope that there is a correspondence Γ →F2[X] of the form
k
X
i=0
aiγ2i 7→
k
X
i=0
aiXi.
However, by Lemma 1 we have γ2k = 0 for 2k > n and therefore such a map
would not be well-defined. However, if we take the right-hand side polynomial
modulo X(n+1)/2, then we have a map. More precisely, we consider the ideal
(X(n+1)/2) generated by X(n+1)/2 in F2[X]. We denote by R the factor ring
R = F2[X]/(X(n+1)/2) and the coset of f by f + (X(n+1)/2) = [f]. Now we let
φ : Γ →R be the map with
φ
 k
X
i=0
aiγ2i
!
=
" k
X
i=0
aiXi
#
.
This map φ is well-defined.
Lemma 8. Let f ∈Γ, g ∈G. Then φ(f ◦g) = φ(f) · φ(g). In particular, the
restriction of φ to G is a monoid homomorphism.
Proof. Let first f = γ2k and g = γ0 + Ps
i=1 aiγ2i ∈G. Then with Lemma 7 we
have
φ(γ2k◦g) = φ
 s
X
i=0
aiγ2i+2k
!
=
" s
X
i=0
aiXi+k
#
=

Xk
·
" s
X
i=0
aiXi
#
= φ(γ2k)·φ(g).
The general case follows by linearity of φ. Let f = Pk
i=0 aiγ2i. Then
φ(f ◦g) = φ
 k
X
i=0
aiγ2i ◦g
!
=
k
X
i=0
aiφ(γ2i ◦g)
=
k
X
i=0
aiφ(γ2i) · φ(g) = φ
 k
X
i=0
aiγ2i
!
· φ(g) = φ(f) · φ(g).
Note that φ(γ0) = [1] ∈F2[X] which is the neutral element with respect to
multiplication.
⊓⊔
We recall the next well-known lemma.
Lemma 9. Let f ∈F2[X]. Then [f] is a unit in R if and only if the constant
term of f is 1. The unit group R∗of R has 2(n−1)/2 elements.
Proof. The element [f] is a unit in R if and only if gcd(f, X(n+1)/2) = 1, equiv-
alently, f does not have 0 as a root and therefore f(0) = 1. Each element in R
has a unique representative with degree at most (n −1)/2. There are 2(n+1)/2
polynomials in F2[X] with degree at most (n −1)/2 and half of them have con-
stant term 1, therefore |R∗| = 2(n−1)/2.
⊓⊔
8
Theorem 3. G = γ0+⟨γ2, γ4, . . . , γn−1⟩is an Abelian group which is isomorphic
to R∗=
 F2[X]/(X(n+1)/2)
∗.
Proof. Note that the map φ : G →R∗is a monoid homomorphism by Lemma 8.
Let f =
h
1 + Pk
i=1 aiXii
∈R∗. Then f = φ(γ0 + Pk
i=1 aiγ2i) with γ0 +
Pk
i=1 aiγ2i ∈G and hence φ is surjective. It holds that |G| = |R∗| = 2(n−1)/2
which then implies that φ is also bijective. Therefore G and R∗are isomorphic as
monoids. As R∗is in fact an Abelian group, it also follows that G is an Abelian
group.
⊓⊔
Remark 3. Every map f ∈G = γ0 + ⟨γ2, γ4, . . . , γn−1⟩is a permutation f :
Fn
2 →Fn
2. To find the inverse of f we just need to find the inverse of φ(f) ∈R,
which can be effectively computed by using the Extended Euclidean Algorithm
for polynomials.
4
Applications
In this section we present some applications of the tools developed in the pre-
vious section. We start by discussing the order of the elements in G. Then we
obtain precise results on the order, algebraic degree and inverse of maps of the
form γ0 + γ2k, generalizing the results on χ = γ0 + γ2. Further we prove The-
orem 1 on the expression for the iterates of χ, which allows us to describe the
fixed points of χj and consequently the cycle structure of χ. Finally we illustrate
a method similar to Horner’s scheme to compute the maps in G more efficiently.
The following lemma gives the orders of the elements of R∗, hence by isomor-
phism also the order of all elements of G.
Lemma 10. Let f = [1+Xj +Pk
i=j+1 aiXi] ∈R∗. Then the order of f is given
by ord(f) = 2m with 2m < n+1
j
≤2m+1. In particular all elements of R∗have
an order of at most 2⌊log2(n)⌋.
Proof. By Lemma 9 the group R∗has 2(n−1)/2 elements. Hence by Lagrange’s
theorem the order of every element is a power of 2. For m arbitrary we then
obtain
f 2m = [1 + Xj +
k
X
i=j+1
aiXi]2m = [1 + X2mj +
k
X
i=j+1
aiX2mi]
which equals [1] if and only if 2mj ≥(n + 1)/2, or equivalently, n+1
j
≤2m+1. As
we are interested in the smallest such m we obtain the claim.
⊓⊔
An interesting class of polynomials to study are binomials. The only binomi-
als in R∗are of the form [1 + Xk] which correspond to the maps γ0 + γ2k in G.
For these maps we can determine their order, inverse and algebraic degree.
9
Theorem 4. Let k ≥1 and sk = max{tk : tk ≤(n −1)/2, t ∈N} be the largest
multiple of k which does not exceed (n −1)/2. Consider f = γ0 + γ2k ∈G.
Then the order of f is given by 2m with 2m < n+1
k
≤2m+1. The inverse of f
is f −1 = γ0 + γ2k + γ4k + . . . + γ2sk. The algebraic degree of f is k + 1 and the
algebraic degree of f −1 is sk + 1.
Proof. Note that φ(f) = [1 + Xk]. The order of f then follows immediately by
Lemma 10.
The inverse of [1 + Xk] in R is given by
[1 + Xk]2m−1 = [1 + Xk]2m
[1 + Xk]
=
h
1 +
 Xk2mi
[1 + Xk]
=
h
1 + Xk + X2k + X3k + . . . + X(2m−1)ki
=

1 + Xk + X2k + . . . + Xsk
and hence
f −1 = φ−1  
1 + Xk + X2k + . . . + Xsk
= γ0 + γ2k + . . . + γ2sk.
As the map γ2j has algebraic degree j + 1 by Lemma 2 the claim follows.
⊓⊔
If we let k = 1 in the previous theorem then we have f = γ0 + γ2 = χ.
Hence as a corollary we obtain the order of χ and a formula for its inverse χ−1.
The order of χ was previously proved in [8] using combinatorial considerations.
A formula for the inverse of χ which was found in [5] by considering an affine
variety associated to χ. Observe that the methods in [5,8] cannot be generalized
in a straightforward manner to the general case which we consider in Theorem 4.
Corollary 1 ([5,8]). The map χ = γ0 + γ2 has order 2m with m given by
2m < n < 2m+1, i.e., m = ⌊log2(n)⌋. The inverse of χ is given by χ−1 =
γ0 + γ2 + . . . + γn−1. The inverse χ−1 has algebraic degree (n + 1)/2.
It has been noted before in [8] that χ behaves like the polynomial 1 + X
in a ring F2[X]/(Xd) for some d ≤(n + 1)/2, however in a different context.
More precisely, for a given y ∈Fn
2, call yi a dynamic bit if the distance to the
next bit yj with yj = 1 is even, otherwise call it static. If yi is a static bit with
yi = 1, then it is called an anchor. It can be shown that χ preserves static bits
and anchors. For a given anchor yi we can define a so-called anchor polynomial
a(i)(X). Then if a(i)(X) is the anchor polynomial of yi and b(i)(X) is the anchor
polynomial of χ(y)i, then b(i) = (1 + X)a(i) mod Xdi where di depends on the
distance to the previous anchor. It is unclear to us how (and if at all) this and
our perspective are related.
Although the next results could be formulated for general binomials, we
present them only for the map χ due to its significance in cryptography.
Next we use that φ(χ) = [1+X] to prove Theorem 1 and thus obtain explicit
formulas for the iterates of χ.
10
Proof (of Theorem 1). It is known from Lucas’s theorem, that
 k
j

is odd if and
only if j ⪯k. Hence, by the Binomial Theorem and Lucas’s Theorem, we have
[1 + X]k =


k
X
j=0
k
j

Xj

=


k
X
j=0
ajXj

=


min{k,(n−1)/2}
X
j=0
ajXj

.
Now we simply apply φ−1.
⊓⊔
Remark 4. Note that the algebraic degree of χk+1 can be smaller than the al-
gebraic degree of χk, even if χk+1 ̸= id. As an example, for n = 11 we have
χ5 = γ0 + γ2 + γ8 + γ10 with algebraic degree 6 and χ6 = γ0 + γ4 + γ8 with
algebraic degree 5.
Another application of our technique is a description of the fixed points of
the iterates χj. We call x ∈Fn
2 a fixed point of χj if χj(x) = x. For j = 1 it
is well-known that the only fixed points of χ are x = 0, 1l. In particular it then
follows that χj(0) = 0 and χj(1l) = 1l for all j ≥1. Therefore we call x = 0, 1l
trivial fixed points. Note, that a fixed point of χj lies in a cycle of length dividing
j in the cycle decomposition of the map χ. Hence the study of the fixed points of
iterates of χ is equivalent to the study of the cycle structure of χ, which appeared
in Theorem 2 and its proof in [8]. The methods used in [8] are different from
ours and apply also to the cases of χ : Fn
2 →Fn
2 with n even or χ : FZ
2 →FZ
2. We
would like to emphasize again that our methods can also be applied for other
maps in G.
Lemma 11. The map χj has a nontrivial fixed point if and only if j = 2k for
some 1 ≤k ≤m. The vector x ∈Fn
2 is a fixed point of χ2k if and only if x does
not contain a substring of the form (0, ∗, 0, ∗, . . . , 0, ∗, 0, 1) of length 2k+1, where
∗denotes an arbitrary element of F2. More precisely, if there exists no integer
i = 1, . . . , n with (xi+1, . . . , xi+2k+1) = (0, ∗, 0, ∗, . . . , 0, ∗, 0, 1) and the indices
are computed modulo n.
Proof. As the order of χ is 2m with 2m < n < 2m+1, any cycle of χ has length
2k for some 0 ≤k ≤m. In particular χj does not have a nontrivial fixed point
if j is not a power of 2. Therefore we consider χ2k. By Theorem 1 we obtain
χ2k = γ0 + γ2k+1.
A vector x ∈Fn
2 is a fixed point of χ2k if and only if x = χ2k(x), or equiv-
alently, γ2k+1(x) = 0. By Remark 1 we have that γ2k+1(x)i = 1 if and only if
(xi+1, . . . , xi+2k+1) = (0, ∗, 0, ∗, . . . , 0, ∗, 0, 1). As x by assumption does not con-
tain such a substring, we have γ2k+1(x) = 0 and x is a fixed point of χ2k.
⊓⊔
We call x ∈Fn
2 a proper fixed point of χj if x is a fixed point of χj and x is
not a fixed point of χℓfor any ℓ< j. A proper fixed point of χj lies in a cycle of
length equal to j in the cycle decomposition of χ.
Theorem 5. Let x ∈Fn
2 \ {0, 1l} and
2s = max{2k : ∃i = 1, . . . , n with (xi+1, . . . , xi+2k) = (0, ∗, 0, ∗, . . . , 0, ∗, 0, 1)}.
Then x is a proper fixed point of χ2s.
11
Proof. Note that 2s is well-defined, because any vector x ∈Fn
2 \ {0, 1l} con-
tains the substring (0, 1). From the definition of 2s and Lemma 11 it follows
that x is not a fixed point of χ2s−1. However, x does not contain a substring
(0, ∗, 0, ∗, . . . , 0, ∗, 0, 1) of length 2s+1 by maximality of 2s and therefore x is a
fixed point of χ2s, again by Lemma 11.
⊓⊔
We conclude the paper by observing, that the maps f ∈G can be evaluated
by factoring them in a special way. The idea of this process is similar to Horner’s
scheme for polynomials. For ease of notation we only demonstrate this for an
example. If f = γ0 + γ2 + γ4 + γ6 + γ8, then
f = id +S2 ⊙(1 + S) + S4 ⊙(1 + S3) ⊙(1 + S)
+ S6 ⊙(1 + S5) ⊙(1 + S3) ⊙(1 + S)
+ S8 ⊙(1 + S7) ⊙(1 + S5) ⊙(1 + S3) ⊙(1 + S)
(1)
= id +(S2 + S4 ⊙(1 + S3) + S6 ⊙(1 + S5) ⊙(1 + S3)
+ S8 ⊙(1 + S7) ⊙(1 + S5) ⊙(1 + S3)) ⊙(1 + S)
= id +(S2 + (S4 + S6 ⊙(1 + S5) + S8 ⊙(1 + S7) ⊙(1 + S5)) ⊙(1 + S3)) ⊙(1 + S)
and hence
f = id +(S2 + (S4 + (S6 + S8 ⊙(1 + S7)) ⊙(1 + S5)) ⊙(1 + S3)) ⊙(1 + S) (2)
or equivalently,
f(x)i = xi+(xi+2+(xi+4+(xi+6+xi+8(1+xi+7))(1+xi+5))(1+xi+3))(1+xi+1).
Note that for the choice n = 9 we have f = χ7 = χ−1, for which a similar
formula already appeared in [1, Appendix D].
Formula (2) has only 4 Hadamard products ⊙, while the original (1) has 10
such multiplications. Observe that f has algebraic degree 5, so 4 applications of
⊙is optimal. In general, if f ∈G has algebraic degree k, by using this process
the number of applications of ⊙can be reduced to k −1 which is again optimal.
Acknowledgments. The authors thank the reviewers for their comments and
suggestions which allowed to improve the presentation of this paper. We thank Lucas
Krompholz for many interesting discussions and in particular for his idea to use the
Hadamard product during our work on [4].
References
1. Biryukov, A., Bouillaguet, C., Khovratovich, D.: Cryptographic schemes based on
the ASASA structure: Black-box, white-box, and public-key. Cryptology ePrint
Archive, Report 2014/474 (2014), https://eprint.iacr.org/2014/474
2. Daemen, J.: Cipher and hash function design strategies based on linear and differ-
ential cryptanalysis. Ph.D. thesis, Doctoral Dissertation, March 1995, KU Leuven
(1995)
12
3. Dobraunig, C., Eichlseder, M., Mendel, F., Schl¨affer, M.: Ascon v1.2: Lightweight
authenticated encryption and hashing. Journal of Cryptology 34(3), 33 (Jul 2021).
https://doi.org/10.1007/s00145-021-09398-9
4. Graner, A.M., Kriepke, B., Krompholz, L., Kyureghyan, G.M.: On the bijectivity of
the map χ. Cryptology ePrint Archive, Paper 2024/187 (2024), https://eprint.
iacr.org/2024/187
5. Liu, F., Sarkar, S., Meier, W., Isobe, T.: The inverse of χ and its applications to
Rasta-like ciphers. Journal of Cryptology 35(4), 28 (Oct 2022). https://doi.org/
10.1007/s00145-022-09439-x
6. NIST: SHA-3 standard: Permutation-based hash and extendable-output functions.
Tech. Rep. Federal Information Processing Standard (FIPS) 202, U.S. Department
of Commerce (Aug 2015). https://doi.org/10.6028/NIST.FIPS.202
7. Schoone, J., Daemen, J.: Algebraic properties of the maps χn. Designs, Codes and
Cryptography (2024). https://doi.org/10.1007/s10623-024-01395-w
8. Schoone, J., Daemen, J.: The state diagram of χ. Designs, Codes and Cryptography
92, 1393–1421 (2024). https://doi.org/10.1007/s10623-023-01349-8
13
