Christina Boura
email: christina.boura@uvsq.fr

Margot Funk
email: margot.funk@uvsq.fr

Yann Rotella
email: yann.rotella@uvsq.fr

Differential analysis of the ternary hash function Troika

Keywords: differential cryptanalysis, Troika, ternary design

Troika is a sponge-based hash function designed by Kölbl, Tischhauser, Bogdanov and Derbez in 2019. Its specificity is that it is defined over F3 in order to be used inside IOTA's distributed ledger but could also serve in all settings requiring the generation of ternary randomness. To be used in practice, Troika needs to be proven secure against state-of-the-art cryptanalysis. However, there are today almost no analysis tools for ternary designs. In this article we take a step in this direction by analyzing the propagation of differential trails of Troika and by providing bounds on the weight of its trails. For this, we adapt a well-known framework for trail search designed for Keccak and provide new advanced techniques to handle the search on F3. Our work demonstrates that providing analysis tools for non-binary designs is a highly non-trivial research direction that needs to be enhanced in order to better understand the real security offered by such non-conventional primitives.

Introduction

Almost all symmetric-key cryptographic schemes known today are defined over the binary field F 2 . However, recent advances in cryptology imply that ternary symmetric constructions could fit better in some particular contexts. A first notable example is a cryptocurrency and distributed ledger technology called IOTA. This platform is based on a ternary architecture and its security relied, among others, on the security of a ternary hash function. For this purpose, a hash function called Curl-P was designed for IOTA, but was soon after found to have devastating security issues [START_REF] Heilman | Cryptanalysis of Curl-P and other attacks on the IOTA cryptocurrency[END_REF]. Curl-P was then replaced by Kerl, another ternary hash function that could be seen as an adaptation of SHA-3 to F 3 . This adaptation was however not natural and led to a particularly inefficient design. For this reason, Kölbl, Tischhauser, Bogdanov and Derbez proposed in 2019 Troika [START_REF] Kölbl | Troika: a ternary cryptographic hash function[END_REF], a ternary hash function claimed to be secure and efficient at the same time.

Even if the advantage of a ternary construction is not completely clear in the IOTA paradigm, ternary symmetric designs could be very meaningful in other settings. For example, in a completely different context, Debris-Alazard, Sendrier and Tillich designed in 2019 Wave, a ternary code-based signature scheme [START_REF] Debris-Alazard | Wave: A new family of trapdoor oneway preimage sampleable functions based on codes[END_REF]. While this scheme is asymmetric, it needs the generation of good quality ternary randomness. Troika would then be a natural candidate for this purpose, as hash functions are regularly used as random number generators.

In the last 30 years, cryptanalysis of traditional binary schemes has been extremely developed. On the other hand, almost nothing is known about the security of ternary symmetric schemes, starting from their resistance against very basic attacks as the differential one. In this article we propose to take a step into this direction by providing an enhanced analysis of the hash function Troika against differential cryptanalysis. The goal of our work is two-fold. First, we aim to provide the first third-party differential analysis against this function by giving concrete upper bounds on the probability of its differential trails. Second, we develop non-trivial techniques for searching differential bounds for ternary designs. We believe that our work can serve as a starting point for the analysis against differential cryptanalysis of ternary designs to come.

Our contributions

Troika is a sponge-based construction whose round function has a design very similar to Keccak. Searching for good differential trails for Keccak is a very complex task due mainly to its large state and its weakly aligned inner components. Dedicated algorithms for generating all trails for Keccak below a given weight, leading to upper bounds on the probability of differential trails for a certain number of rounds were developed in [START_REF] Daemen | Differential propagation analysis of Keccak[END_REF][START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF]. These articles were the starting point of our work. We adapted and extended them for the ternary case and applied them to Troika. This adaptation was not straightforward and we needed to develop advanced techniques to be able to compute on trits (i.e. elements of F 3 ) in a reasonable time. Most of our improvements concern the tree traversal used to generate out-kernel 2-round trail cores. This applies to the computation of the so-called runs, a way to organize the differential patterns of a state. More precisely, we defined an equivalence class notion on the runs that permitted us to treat less trail cores and we improved a specific order relation such that fewer collisions between runs occur, leading to more efficient tree pruning. This permitted us to scan all trail cores up to weight 41 and to prove that there do not exist 6-round trails with weight lower than 82. In comparison, the designers of Troika were only able to provide results on smaller versions of Troika by using a MILP-based approach. Their approach could not apply to the original version of the function because of its large state.

Eventually, we show that adapting the existing tool from Keccak to Troika is a highly nontrivial problem, even if the design strategy of both primitives is similar. This is mainly due to the fact that, contrary to the binary case, active trits can take two values (1 or 2), leading to a huge number of trails to treat. Thus, providing interesting bounds for Troika is not possible without introducing new ideas to prune the search tree efficiently. More generally, our work highlights that adapting existing tools and methods from F 2 to F 3 is a challenging task and indicates that more research efforts are needed towards this direction.

The rest of the article is organized as follows. In Section 2 we recall classical notions regarding differential trail search on symmetric primitives. Section 3 presents the specifications of Troika while Section 4 describes the general strategy used to scan all trail cores of a certain weight. Our algorithms for generating 2-round trail cores for Troika are described in Section 5. These 2-round trail cores can then be extended to 6-round trail cores with the techniques described in Section 6.2. Section 6.1 is dedicated to the direct search of 3-round trail cores of a particular profile, called in-kernel that can be generated relatively easier without the techniques of Section 5. Finally, Section 7 presents some statistics on the trails we managed to scan.

Differential cryptanalysis

Differential cryptanalysis is a powerful attack against symmetric primitives that exploits input differences that propagate through the primitive to some output difference with high probability. We recall in this section basic definitions regarding differential properties.

Notation Let K be a finite field. We want to study a substitution-permutation primitive f from K n to K n . Typically for Troika, K is the field F 3 . We write + for the usual coordinate-wise addition in K n and use the operatorin the usual way. We call state the value of the variable of K n which is progressively updated through the substitution permutation network. We denote by R 0 , . . . , R r-1 the r round functions that are iteratively applied to the state i.e.

f = R r-1 • • • • • R 1 • R 0 . For k ∈ [0, r -1]
, the round function R k is the composition of a nonlinear map χ, a linear map λ and a round constant addition ι k , that is to say R k = ι k • λ • χ. The state is divided for the nonlinear layer into disjoint parts of equal size, called boxes. A nonlinear map, called S-box and supposed here to be bijective, is applied to each box of the state.

Differentials Let f : K n → K n be a permutation. A differential over f is a couple (∆ in , ∆ out ) ∈ (K n ) 2 . The difference ∆ in is said to be an input difference while the difference ∆ out is called an output difference. The differential probability of a differential (∆ in , ∆ out ) over f is defined as DP f (∆ in , ∆ out ) := #{x ∈ K n : f (x + ∆ in ) -f (x) = ∆ out } #K n .
If DP f (∆ in , ∆ out ) > 0, we say that the input difference ∆ in is compatible with the output difference ∆ out through f and call (∆ in , ∆ out ) a valid differential over f . The weight of a valid differential (∆ in , ∆ out ) over f is

w f (∆ in , ∆ out ) := -log #K (DP f (∆ in , ∆ out )) .
Differential trails When the dimension n of the domain of the iterated function f is large, it is in general not possible to compute the exact differential probability of a differential over f . Thus, we try to approximate this probability by studying sequences of differences, called differential trails. In the following, we denote by

f = R r-1 • • • • •R 0 an iterated function from K n to K n . For k ∈ [1, r], a k-round differential trail over f is a sequence Q = (q (0) , q (1) , . . . , q (k) ) ∈ (K n ) k+1
where for 0

≤ i ≤ k-1, (q (i) , q (i+1) ) is a valid differential over R i . The differential probability of Q is defined as DP f (Q) := #{(x, x ′ ) ∈ (K n ) 2 : ∀i ∈ [0, k], f [i](x) -f [i](x ′ ) = q (i) } #K n ,
where f [0] is the identity function and

for i ∈ [1, k], f [i] = R i-1 • . . . • R 0 . If we write DT f (∆ in , ∆ out )
for the set composed of all trails over f of the form (∆ in , q (1) , . . . , q

(k-1) , ∆ out ), then DP f (∆ in , ∆ out ) = Q∈DT f (∆in,∆out) DP f (Q).
Computing the exact probability of a differential trail is in general out of reach. Instead, we try to approximate it, looking locally at the differentials that form the trail. The weight of a differential trail Q = (q (0) , q (1) , . . . , q (k) ) over f , defined as

w f (Q) := k-1 i=0 w Ri (q (i) , q (i+1) ),
is a value used to approximate the differential probability of the trail. We expect to have DP f (Q) ≃ (#K) -w f (Q) . The weight of the trail Q is easy to calculate as for all i ∈ [0, k -1], w Ri q (i) , q (i+1) = w χ q (i) , λ -1 q (i+1) . This last quantity can be computed as the sum of the weights of the differentials given by the restriction of q (i) , λ -1 q (i+1) to the domain and co-domain of the Sboxes. To estimate the security of a primitive against differential attacks, it is essential to ensure that there do not exist differential trails with low weight.

Trail cores [START_REF] Daemen | Differential propagation analysis of Keccak[END_REF] A k-round differential trail over f will be represented as follows:

b 0 χ --→ a 1 λ --→ b 1 χ --→ a 2 λ --→ • • • λ --→ b k-1 χ --→ a k λ --→ b k , where for i ∈ [1, k], b i = λ(a i ) and DP χ (b i-1 , a i ) > 0.
Since the S-boxes are bijective, if a differential (b, a) is valid over χ, then the nonzero boxes of the difference a are located at the same positions as those of b. These boxes and their corresponding S-boxes are said to be active.

The choice of the difference b 0 and the choice of the difference a k of the kround trail do not affect the number of active S-boxes. For this reason it is convenient to specify only the central part of the trail, namely (a 1 , . . . , b k-1 ). This defines a set of differential trails

⟨a 1 , . . . , b k-1 ⟩ := {Q = (b ′ 0 , a 1 , . . . , b k-1 , a ′ k , b ′ k ) : Q is a k-round trail over f } called a k-round trail core of f . The weight of a k-round trail core ⟨a 1 , . . . , b k-1 ⟩, written w⟨a 1 , . . . , b k-1 ⟩
, is the minimum of the weights of the trails that belong to the trail core. To make this explicit, the notions of minimum direct and reverse weight of a difference are introduced. The minimum reverse weight of a difference ∆ ∈ K n is given by

w rev (∆) = min b {w χ (b, ∆)},
where the minimum is taken over the differences b ∈ K n such that (b, ∆) is a valid differential over χ. The minimum direct weight of

∆ ∈ K n is w dir (∆) = min a {w χ (∆, a)},
where the minimum is taken over the differences a ∈ K n such that (∆, a) is a valid differential over χ. The weight of a 2-round trail core ⟨a, b⟩ is then w⟨a, b⟩ = w rev (a

) + w dir (b). If k ≥ 2, the weight of a k-round trail core ⟨a 1 , . . . , b k-1 ⟩ is w rev (a 1 ) + k-2 i=1 w χ (b i , a i+1 ) + w dir (b k-1 ).
Following the same approach as in [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF], we gradually generate differential trail cores, starting from short trail cores and extending them in the forward and backward direction.

Troika description

We denote the finite field with 3 elements by F 3 . We call an element of F 3 = {0, 1, 2} a trit and an element of F 3 3 a tryte.

The Troika round function Troika is a hash function from F * 3 to F 243 3 . It follows the sponge construction [START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF] with a rate of 243 trits and a capacity of 486 trits. Therefore, the state is a vector of 729 trits. The permutation f used inside the sponge construction is composed of 24 rounds. Each round follows the Keccak [START_REF] Bertoni | The Keccak SHA-3 submission[END_REF] philosophy and is composed of 5 step functions: a nonlinear layer Sub-Trytes, two shuffling layers ShiftRows and ShiftLanes, a parity-mixer AddColum-nParity and a round constant addition AddRoundConstant i . Taking the same notations as in Keccak-f , we abbreviate them here respectively by χ, ρ r , ρ ℓ , θ and ι i . We also denote by ρ the composition ρ = ρ ℓ • ρ r and λ the whole linear layer. The round function R i is then given by R i = ι i • λ • χ, where χ is the nonlinear layer and λ = θ • ρ is the linear layer.

Notations and definitions

The round function operates on a state of 729 trits, organized as a three-dimensional array of size 9 × 3 × 27 trits. In the following, x will always be an integer between 0 and 8, x B an integer between 0 and 2, y an integer between 0 and 2 and z an integer between 0 and 26. Moreover, coordinates along the x, y and z axes will always be considered modulo 9, 3 and 27 respectively. We use the letter A to denote a state, that is either seen as an element of F 729 3 or as a three-dimensional array. We write A[x, y, z] for the trit of A of coordinates (x, y, z). The box of A of coordinates (x B , y, z) is the tryte (A[3x B + i, y, z]) i∈ [0,[START_REF] Bertoni | The Keccak SHA-3 submission[END_REF] . We call a box-column a triplet of boxes that have the same x B and z coordinates. The different parts of the state of Troika can be visualised in Figure 9 of Appendix B. We denote by e (x,y,z) the canonical state whose components are all zero, except the component of coordinates (x, y, z) that equals 1.

: (A[3x B + i, y, z]) i∈[0, 2] ̸ = (0, 0, 0)}. It is denoted by w box (A).
The nonlinear layer The map SubTrytes, here denoted by χ, is the parallel application of 9 × 27 S-boxes of size 3 trits. The minimum reverse and direct weights of a state are easy to compute. Indeed, by computing the differential distribution table of the S-box, one can verify the following properties.

Property 1. For all differences A ∈ F 729 3 , w rev (A) = w dir (A) = 2 w box (A).

Property 2. It can be noticed that the following input differences ∆ in are compatible through the S-box map with output differences ∆ out of the form :

∆ in ∈ F 3 3 ∆ out = (t 0 , t 1 , t 2 ) ∈ F 3 3 ∆ in ∈ F 3 3 ∆ out = (t 0 , t 1 , t 2 ) ∈ F 3 3 (0, 0, 1) t 2 = 1 (1, 0, 0) t 1 ̸ = 0 (0, 0, 2) t 2 = 2 (2, 0, 0) t 1 ̸ = 0
This property is used in Appendix E.3 to extend trail cores in the forward direction.

Remark 1. If a differential (∆, ∆ ′ ) is valid through the bijective nonlinear map χ, then the differences ∆ and ∆ ′ have the same box-activity pattern.

The shuffling layers The permutations ShiftRows and ShiftLanes move the trits of the state along the x and z axes, without modifying their value. We denote by ρ the permutation of the set of coordinates that satisfies ρ e (x,y,z) = e ρ(x,y,z) for all (x, y, z) ∈ [0, 8] × [0, 2] × [0, 26]. For a complete description of these layers we refer to [START_REF] Kölbl | Troika: a ternary cryptographic hash function[END_REF].

The parity-mixer The map AddColumnParity, written here θ, is a column parity mixer [START_REF] Stoffelen | Column parity mixers[END_REF]. The parity plane of a state A is the bi-dimensional array of size 9 × 27 that indicates the parity (0, 1 or 2) of each column of A. It is denoted by P (A) and defined as

P (A)[x, z] := 2 y=0 A[x, y, z] mod 3.
It is said that the column of A of coordinates (x, z) has parity

P (A)[x, z] ∈ F 3 .
The θ-effect plane of A is the bi-dimensional array of size 9×27, denoted by E(A) and defined as

E(A)[x, z] := P (A)[x -1, z] + P (A)[x + 1, z + 1]. If E(A)[x, z] is zero, the column of A of coordinates (x, z
) is said to be non affected by θ. Otherwise, the column is said to be affected by

E(A)[x, z] ∈ F 3 .
The map θ is defined as

θ(A)[x, y, z] := A[x, y, z] + E(A)[x, z].
The set K := {A ∈ F 729 3 : θ(A) = A} is called the column-parity kernel (or kernel for short). Moreover, the set F 729 3 \ K is denoted by N . A state belongs to the kernel if and only if all its columns have parity 0. Given a k-round trail core ⟨a

1 , b 1 , . . . , a k-1 , b k-1 ⟩, its parity profile is written |X 1 | . . . |X k-1 | where X i = K if b i ∈ K and X i = N otherwise.
The column parity mixer θ does not change the parity of the state :

P (A) = P (θ (A)). Indeed, P (θ (A)) [x, z] = 2 y=0 A[x, y, z] + 3E(A)[x, z] mod 3 = P (A)[x, z]. Therefore, E(A) = E (θ (A))
and the inverse function of θ is given by

θ -1 (A)[x, y, z] = A[x, y, z] -E(A)[x, z].

z-equivalence classes

The four step functions χ, ρ r , ρ ℓ and θ are invariant with respect to the translation along the z-axis i.e. they commute with functions that translate the state in the z direction. Differential trails are thus considered up to translation along the z-axis.

General strategy for differential trail search [9]

Our objective is to analyze the resistance of Troika against differential cryptanalysis by providing a lower bound on the weight of any trail over a given number of rounds. We explain in this section the general strategy we followed for doing so. As Troika's round function has a similar design to Keccak-f , we naturally adopted the same strategy as the one used in [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF]. This strategy permits to lower bound the weight of 6-round trail cores by extending trail cores on 3 rounds.

Overview of the steps

All 6-round trail cores of weight less than a bound W can be generated by 1. collecting all 3-round trail cores of weight up to W/2, 2. extending these 3-round trail cores by 3 rounds in the forward direction and in the backward direction.

Remark 2. In [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF], it is sufficient to collect all the 3-round trail cores up to weight ⌊W/2⌋ since the weight is necessarily an integer in F 2 .

To cover the space of 3-round trail cores

a 1 λ --→ b 1 χ --→ a 2 λ
--→ b 2 up to some weight, the search space is split according to the parity profile of the trail cores. Trail cores of parity profile |K|K| can be generated efficiently (see Section 6.1). For trail cores of parity profile |K|N |, |N |K| and |N |N | we use the same steps as in [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF], recalled in the following lemma. To exhaustively generate the 2-round trail cores that respect the constraints of the above lemma, we use a tree traversal, as defined by Mella et al. in [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF]. We recall this technique in Section 4.2 and define the specific trees used for Troika in Section 5. The extension phase is detailed in Section 6.2.

Generating 2-round trail cores as a tree traversal

For simplicity, we explain the method presented in [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF] to study 2-round trail cores of weakly aligned primitives in the case of primitives defined on F n 2 . This technique exploits the specific features of the linear layer to take simultaneously into account the weights w rev (a) and w dir (b) of a 2-round trail core ⟨a, b⟩.

More precisely, given a bound W and two weightings α and β, a tree traversal is performed to find all trail cores ⟨a, b⟩ satisfying α w rev (a) + β w dir (b) ≤ W and possibly some other restrictions. We denote by c α,β the function that associates to a pair (a, b) ∈ (F n 2 ) 2 the quantity α w rev (a) + β w dir (b). In the following, after having fixed a pair (α, β), we will call the quantity c α,β (a, b) the cost of the trail core ⟨a, b⟩.

The idea is to generate trail cores of the form ⟨a, b⟩ by adding progressively to a variable (a, b) ∈ (F n 2 ) 2 initialised to (0, 0) some vectors of (F n 2 ) 2 . These vectors are called units and must be defined according to the distinctive features of the round function. The cost of the trail core ⟨a, b⟩ is checked each time a unit is added. This process is stopped when all the trail cores that could be obtained by adding more units would have a cost higher than W .

The tree traversal More formally, the algorithm is a tree traversal. A node of the tree is a list of units, called unit-list. A unit-list of the form

L = [u 1 , . . . , u n ] is associated to the vector (a L , b L ) := n i=1 u i and to the cost c α,β (a L , b L ). A unit-list L is said to be complete if b L = λ(a L )
, that is to say if it is associated to a 2-round trail core. It is not always the case (see the tree defined in Section 5.3). The root of the tree is the empty unit-list. A child of a unit-list L is a unit-list of the form L || [u], where u is some particular unit that does not belong to L. To avoid having two unit-lists with the same units in a different order, an order relation on the units is chosen and units are only added in ascending order. This order relation organizes the edges of the tree and must therefore be chosen to ensure good properties of the tree.

During the tree traversal a lower bound on the cost of all of the current node's descendants is calculated. The tree is pruned if this lower bound is higher than W . The goal is to define the units and the tree organization in order to be able to prune the tree efficiently. There should be no descendant of a node L that has a cost much lower than this L's cost. A node should have as few brothers as possible.

Finally, if there exists an equivalence relation on trail cores -like the zinvariance -then it is possible to visit only one representative per equivalence class. The order relation on the units induces an order relation on the unit-lists, given by the lexicographic order. A unit-list is said to be canonical if it is the smallest representative of its class. We are interested in the set formed by all canonical unit-lists of cost below W . As the Lemma 1 of [9, Section 3.2] shows that a unit-list that is not canonical cannot have a canonical descendant, the tree is also pruned if a non canonical unit-list is encountered.

Lower bounding the cost To discuss how to give a lower bound on the costs of the descendants of a unit-list, we distinguish as in [5] between two types of active coordinates, the stable ones and the unstable ones. An active coordinate of (a L , b L ) is said to be a stable coordinate of L if it is active for any pair (a L ′ , b L ′ ) where L ′ is a descendant of L and unstable otherwise. By counting only the contribution of the stable coordinates of L we obtain a lower bound on the costs of the descendants of L. This bound might be improved by studying the behavior of the unstable coordinates of L. For that, we search for some sets of passive or unstable coordinates that necessarily contribute to the cost of the descendants of L. We say that a subset I of the passive or unstable coordinates of (a L , b L ) is an activity invariant of L if for every descendant L ′ of L there exists a coordinate i ∈ I such that i is an active coordinate of (a L ′ , b L ′ ). If all the coordinates of an activity invariant belong to boxes that have not already contributed to the bound, then this bound can be increased by adding a lower bound on the contribution of that activity invariant. This process is summarized in Algorithm 1 of Appendix A.

Generating 2-round trail cores in Troika

We present in this section the trees used to exhaustively generate the 2-round Troika's trail cores of a given parity profile that also respect a cost constraint.

The cost of a 2-round trail core ⟨a, b⟩ depends only on the positions of the active trits, but in some cases we will also need to know the exact difference. For this reason we introduce the notion of mixed states.

Definition 4. (Mixed state)

A mixed state is a three-dimensional array of size 9 × 3 × 27 whose cells can take either the value 0, 1, 2 or , where the value stands for an active trit of unspecified value. It can also be seen as a vector of {0, 1, 2, } 729 .

We say that a difference A ∈ F 729 3 is compatible with a parity plane p and a mixed state M if P (A) = p and if for all coordinates (x, y, z

), A[x, y, z] = M [x, y, z] if M [x, y, z] ∈ {0, 1, 2} and A[x, y, z] ̸ = 0 otherwise.
Addition of mixed states is defined as the component-wise addition. Only the commutative addition 0 + = and the usual addition modulo 3 can occur in our algorithms. The definitions of the trit shuffling ρ, the box weight and the cost functions c α,β are extended to mixed states. We denote by m (x,y,z) the mixed state whose components are all zero, except the component of coordinates (x, y, z) that equals .

Generating |K|-trail cores

We define the tree used for the generation of trail cores ⟨ρ -1 (b), b⟩ with b ∈ K and valid cost. As the difference b of such trail cores belongs to the kernel, its columns have either zero, two or three active coordinates. A node of the tree represents a couple of mixed states (ρ -1 (M ), M ) ∈ {0, } 729 ×{0, } 729 where M has zero, two or three active coordinates per column. All nodes can be obtained by summing units of the form :

1. x,z := ρ -1 (m), m , where m = m (x,0,z) + m (x,1,z) , 2. x,z := ρ -1 (m), m , where m = m (x,0,z) + m (x,2,z) , 3. x,z := ρ -1 (m), m , where m = m (x,1,z) + m (x,2,z) , 4. x,z := ρ -1 (m (x,2,z) ), m (x,2,z) .
Units are characterized by their coordinates (x, z) and their patterns , , or . Their ordering is arbitrary. We just need to have x,z < x,z for all x and z.

Units have to be added to the unit-list in ascending order while respecting two constraints. A unit of type 4 can only be added to a unit-list that already contains the unit of type 1 of same coordinates (x, z). A unit of types 1, 2 or 3 cannot be added if there is already in the unit-list another unit of same coordinates (x, z). Thereby, the mixed state M of a node (ρ -1 (M ), M ) cannot have a column with only one active coordinate. Moreover, this ensures that all coordinates of a unit-list are stable and consequently that the cost function c α,β is monotonic with respect to units addition.

To obtain the differences b of the desired trail cores ⟨ρ -1 (b), b⟩, it just remains to generate, for each node (ρ -1 (M ), M ) reached during the tree traversal, the differences compatible with the zero parity plane and the mixed state M .

Reducing the problem of generating |N |-trail cores to that of generating parity-bare states at the input of θ

For the generation of trail cores of the form ⟨ρ -1 (c), θ(c)⟩ with c ∈ N , our approach is the same as in [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF]. Unlike the generation of |K|-trail cores, we were not able to define a tree whose nodes have only stable coordinates. The difficulty comes from the column parity mixer : activating trits at the input of θ can deactivate trits at the output of the function and vice versa. The rationale behind the tree's units and the order relation among them is to gradually choose the columns' values on either side of the map θ in an appropriate order that limits the number of unstable coordinates.

As in [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF], we reduce the problem of that of finding a good tree containing all trail cores ⟨ρ -1 (c), θ(c)⟩ such that c is a parity-bare state. That means that the unaffected columns of c have as few active trits as possible for their parity, namely zero for columns of parity zero and one for the other unaffected columns. Once the parity-bare states are generated, we no longer have to care about the θeffect and can define trees as in Section 5.1 to recover from the parity-bare states all the wanted |N |-trail cores. Indeed, any out-kernel state can be obtained by summing a parity-bare state and an in-kernel state that only adds extra active coordinates to the unaffected columns of the initial parity-bare state. We refer to Appendix C for a detailed description of the tree used to add extra active coordinates in the unaffected columns of a parity-bare state.

Example 1. Replacing an unaffected column 1 of a parity-bare state c by one

of the columns 2 2 , 2 2 , 1 2 1 , 1 1 2 , 2 1 1
does not decrease the cost of the trail core ⟨ρ -1 (c), θ(c)⟩.

Generating parity-bare states at the input of θ

We now present the tree used to organize the trail cores ⟨ρ -1 (c), θ(c)⟩ such that c is a parity-bare state. The idea is to choose the columns of the difference c in an order that makes it possible to control the parity plane and the θ-effect plane of c.

To describe more easily the tree's units and the order relation among them, we introduce the notion of diagonal coordinate d of a column. The (x, z)-coordinates and (d, z)-coordinates of a column are related by the change of coordinates (x, z) = (d + 2z mod 9, z). In the following, the letter d will always be an integer taken modulo 9 that refers to a diagonal coordinate. The coordinates of a column are implicitly given using the (d, z)-coordinates.

General form of units A unit of the tree is an element of F 729 3 × F 729 3 whose values at the input and output of θ correspond to the values of a column, affected or not, before and after θ. More formally, a unit is a pair of the form

  t 2 t 1 t 0   x,z,t := ρ -1 2 i=0 t i e (x,i,z) , 2 i=0 (t i + t)e (x,i,z) .
It is characterized by its (x, z)-coordinates, by a triplet (t 0 , t 1 , t 2 ) ∈ F 3 3 that is the column value at the input of θ and by a trit t that is the θ-effect applied to obtain the column value at the output of θ. To obtain a pair of the form (ρ -1 (c), θ(c)) by summing units, the parity-plane and the θ-effect plane formed at the input of θ have to be consistent.

Runs and loops

Similar to what is done for Keccak [START_REF] Bertoni | The Keccak SHA-3 submission[END_REF] and Xoodoo [5], to link the parity plane and the θ-effect of a state, we group all its columns of nonzero parity in sets called runs and loops. The following definitions are motivated by the fact that the θ-effect applied to a column of coordinates (d 0 + 1, z 0 ) depends on the parity of the columns of coordinates (d 0 , z 0 ) and (d 0 , z 0 + 1). Definition 5. Let A be a state. For an integer ℓ ∈ [1, 26] and some coordinates (d 0 , z 0 ), we consider the set r formed by the columns of A of coordinates (d 0 , z 0 ), . . . , (d 0 , z 0 + ℓ -1). If all the columns of r have non-zero parity and if the two columns of coordinates (d 0 , z 0 -1) and (d 0 , z 0 + ℓ) have parity zero, we say that r is the run of A of coordinates (d 0 , z 0 ) and of length ℓ. Definition 6. If a state admits a set of columns of coordinates (d 0 , 0), . . ., (d 0 , 26) that all have non-zero parity, we say that this set is a loop. The set formed by all the non-zero parity columns of a state can be partitioned into runs and loops. Each run or loop determines a part of the θ-effect plane. More precisely, if a state A admits a run of coordinates (d 0 , z 0 ) and of length ℓ, then this run determines for all i ∈ [-1, ℓ -1], the value of

E(A)[d 0 + 1, z 0 + i].
The columns of coordinates (d 0 + 1, z 0 -1) and (d 0 + 1, z 0 + ℓ -1) are always affected.

From supra-units to units Since a trail core ⟨ρ -1 (c), θ(c)⟩ formed from a parity-bare state c that has a loop has a cost too high for our search, we restrict the nodes of the tree to trail cores formed from parity-bare states that have only runs. However, the existence of loops for Troika, is a consequence of the particular θ mapping used in Troika and this effect does not appear in Keccak. The existence of these loops is due to the fact that all the diagonal coordinates form 9 disjoint sets. We use this property later to improve the lower bound on the cost of a trail.

Every parity-bare state with n runs can be decomposed into n parity-bare states with only one run. These latter have only unaffected null columns, unaffected columns with a single active trit and affected columns of parity zero. Such a decomposition is not unique. To make it unique, we adopt the same conventions as in [START_REF] Bertoni | The Keccak SHA-3 submission[END_REF] and [5]. The runs of the decomposition must not overlap. Moreover, if the initial state admits affected columns of non-zero parity, these columns have to be decomposed into an unaffected column with a single active trit at y = 0, whose value is the parity of the initial column, and an affected column chosen accordingly. We call this rule the non-zero-y0 convention. Under these conventions, the existence and the uniqueness of the decomposition can be proved as in [5, Section 7.3.2] by exhibiting a deterministic procedure that removes from a parity-bare state with n runs a parity-bare state with one run to get a parity-bare state with n -1 runs. It removes the columns of a run as well as the columns affected by this run, using the non-zero-y0 convention to split the affected columns of non-zero parity and only remove the suitable part of such columns. All the sought trail cores can be expressed as a sum of elements of F 729 3 ×F 729 3 of the form ρ -1 (A), θ(A) where A is a parity bare state with only one run. We call these elements supra-units. Since there are too many possible supra-units, they cannot directly be used as units. A finer subdivision is therefore used. It relies on the units introduced before, that enable to form the supra-units one by one. With this refinement, many supra-units have a common ancestor, which is important for the tree pruning. We define a partial order relation on the supra-units. For that, we characterise a supra-unit ρ -1 (A), θ(A) with the coordinates (d, z) and the length ℓ of the run of A. The partial order is given by the lexicographic order on [d, z, ℓ] and supra-units are put in the unit-list in ascending order.

Two types of units are used. Those that are said to be affected correspond to affected columns of parity zero at the input of θ ; those that are said to be unaffected correspond to unaffected columns with only one active trit at the input of θ. Each supra-unit of coordinates (d, z) and length ℓ is the sum of :

ℓ unaffected units with (d, z)-coordinates (d, z), . . . , (d, z + ℓ -1), -2 affected units of coordinates (d + 1, z -1) and (d + 1, z + ℓ -1), -from 0 to ℓ -1 other affected units that could be in positions (d + 1, z), . . ., (d + 1, z + ℓ -2). These units are indexed from 0 to 2ℓ and added to the unit-list in ascending order of indexes. The i-th unit has coordinates

(d + 1, z -1 + i 2 ) if i is even and (d, z + ⌊ i 2 ⌋) if i is odd.

Importance of the ordering of supra-units

The ordering of units resembles the one of [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF], except that here, the partial order on supra-units allows us to detect more active coordinates that are stable for a unit-list. This results in an improvement of the bound computed with Algorithm 1 (given in Appendix A).

We were able to increase the 3-round weight target from 33 to 41. The only way for active coordinates of a unit-list to turn passive is when an unaffected unit is added to a unit-list that already contains an affected unit of same coordinates, or vice versa. By the non-zero-y0 convention, the only overlaps allowed are of the form :

  t 2 t 1 t 0   x,z,t +   0 0 t ′ 0   x,z,0
, where

t 0 + t 1 + t 2 = 0, t ∈ {1, 2} and t ′ 0 ∈ {1, 2}.
Let L be a unit-list and (a L , b L ) = u∈L u. If a unit-list has only one of the two terms of the above sum, then the trit of a L of coordinates ρ -1 (x, 0, z) and the trit of b L of coordinates (x, 0, z) may be unstable. In the particular case of Troika, this criterion can be refined by locating columns that can no longer be concerned by an overlap and thus have only stable coordinates. The main remark is that overlaps only involve affected units of a supra-unit of diagonal coordinate d and unaffected units of a supra-unit of diagonal coordinate d+1. The ordering of supra-units implies that unaffected units that belong to a supra-unit of diagonal coordinate d > 0 are not concerned anymore by overlaps since supraunits of d-coordinate d -1 can no longer be added to the unit-list. Similarly, if we write d last for the d-coordinate of the supra-unit that is being formed or that just has been completed, then all the affected units belonging to a supra-unit of coordinate d < d last -1 cannot be involved in a new overlap. Lower bounding the cost We use Algorithm 1 to compute a lower bound on the costs of node's descendants. The criterion used to distinguish between stable and unstable coordinates of a unit-list L is explained above. It remains to describe the activity invariants of L. Suppose that the difference ρ(a L ) has an affected column of coordinates (x, z). For every descendant L ′ of L, this column remains affected and thus

a L ′ [ρ -1 (x, 0, z)] ̸ = b L ′ [x, 0, z].
In particular, at least one of these two trits is active. Suppose now that the difference ρ(a L ) has an unaffected column with only one active trit of coordinates (x, 0, z). Whether or not this column becomes affected for a descendant L ′ of L, there will always be an active trit among the set {a L ′ [ρ -1 (x, 0, z)], b L ′ [x, 0, z]}. Moreover, since the columns of coordinates (x, z) at the input and output of θ will always have a non-zero parity, the same is true for the sets {a

L ′ [ρ -1 (x, i, z)] : i ∈ [0, 2]} and {b L ′ [x, i, z] : i ∈ [0, 2]}.
An improvement for the tree traversal The fact that we are working over F 3 does not facilitate the tree traversal. If we entirely specify the value of the differences for all the active trits, there will be too many possibilities to treat. But, if we do not specify the value, the behaviour of the column parity mixer θ is too complicated to understand. To deal with this situation we introduce an equivalence relation on parity-bare states used to reduce the search space during the tree traversal. We say that two complete unit-lists L and L ′ are scalar-equivalent if the differences ρ(a L ) and ρ(a L ′ ) are scalar-equivalent. Two complete scalar-equivalent unit-lists describe trail cores that have the same trit-activity pattern. We organize the tree to have only one representative per equivalence class. At the end of the tree traversal, we generate from each representative the elements of its class.

6 Dealing with |K|K| profile and extensions

Generating 3-round trail cores of parity profile |K|K|

The space of 3-round trail cores with parity profile |K|K| can be directly scanned up to some limit weight. We search for trail cores of the form ⟨ρ

-1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩ with b 1 ∈ K and ρ(a 2 ) ∈ K.
The first step is to generate a subset A 2 ⊂ F 729 2 that contains all trit activity patterns that are good candidates for a 2 . For that, we derive necessary conditions on a 2 from the fact that the differences b 1 and ρ(a 2 ) must be in the kernel. More precisely, if ⟨ρ -1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩ is a trail core of parity profile |K|K|, then a column of ρ(a 2 ) cannot have exactly one active trit. Moreover, as b 1 ∈ K, a box-column of b 1 cannot have exactly one active box. Due to the fact that the differences b 1 and a 2 have the same box activity pattern, a box-column of a 2 cannot have exactly one active box. Thereby, we deduce the two following necessary conditions on ρ(a 2 ) and on a 2 :

-If ρ(a 2 )[x, y, z] = 1, then ρ(a 2 )[x, y + 1, z] = 1 or ρ(a 2 )[x, y + 2, z] = 1; -If a 2 [x, y, z] = 1, then it exists i ∈ {0, 1, 2} and j ∈ {1, 2} such that a 2 [3x B + i, y + j, z] = 1
, where x B = ⌊ x 3 ⌋. To take into account the weight constraint, we compute only from the trit activity pattern a 2 of a difference a 2 , a lower bound on the weight of trail cores of the form ⟨ρ -1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩, denoted by w 3-round min (a 2 ). The set A 2 is formed by all the trit activity patterns a 2 that respect the necessary conditions and that lead to a bound w 3-round min (a 2 ) below the limit weight. We refer to Appendix D for a complete description of the method to form the subset A 2 .

The second step is to generate all (|K|K|, W )-trail cores, by extending backward inside the kernel (if possible) the 2-round trail cores ⟨a 2 , ρ(a 2 )⟩ that satisfy a 2 ∈ A 2 and ρ(a 2 ) ∈ K. The details of the extension algorithm are given in Appendix E.1.

Extension of trail cores

Once all trail-cores of a certain length have been obtained, these must be extended. Extensions are treated differently depending on their direction (backward or forward) and their type (inside or outside the kernel).

For the forward extension, the authors of [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF] exploited the fact that the Keccak S-box is quadratic, a property that does not hold for Troika. To extend a trail core outside the kernel in the forward and backward direction or inside the kernel in the backward direction we use a step-by-step approach to control the extensions' weight. Our approach shares some similarities with the method of [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF] but is necessarily different because the inner components of the two functions are not the same.

Because of the page restriction all our methods used for extending the obtained trail cores are given in Appendix E.

Results and conclusion

We have covered the space of all 3-round trail cores up to weight 41 and showed that there exists no differential trail over six rounds with weight below 82. It results in a better bound than the one obtained with the MILP-based approach. Adapting the framework of [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF] for the field F 3 was harder than expected. Dealing with trits rather than bits complicates the analysis and we were not able to take a cost target for the search as high as for Keccak.

Our experimental results have been obtained on a Intel Core i5 processor running at 2.4Hz and a single core was used for each experiment. Our code is publicly available 1 . We assume that we cannot do considerably better as the number of trails to scan would rapidly be a limiting factor. This is why we did not try to run the code longer even though it may be possible to get a slightly better bound.

For the generation of 3-round trail cores of parity profile |K|K|, we were able to cover the space up to weight 65. This search takes advantage of the small size of the S-boxes, which gives restrictive conditions on the box-activity pattern of an in-kernel difference. Figure 6 reports the number of found |K|K| trail cores per weight. Finally, Figure 8 gives the weight distribution of the 3-round trail cores up to weight T 3 = 41 depending on the parity profile of the trail cores.

A Algorithm to give a lower bound on the costs of a unit-list and its descendants

We recall here the algorithm used in [5] to give a lower bound on the costs of a unit-list and its descendants. To index the coordinates of an element of Let c be a parity-bare state associated to a trail core ⟨ρ -1 (c), θ(c)⟩ of valid cost. We arrange in a tree all the trail cores ⟨ρ -1 (c * ), θ(c * )⟩ that correspond to a difference c * that has the same parity plane and affected columns as c and possibly extra active coordinates in its unaffected columns. We form, from the initial parity-bare state c, the mixed state M c defined as

F n 2 × F n 2 ,
M c [x, y, z] =      c[x, y, z] if E(c)[x, z] ̸ = 0 if E(c)[x, z] = 0 and c[x, y, z] ̸ = 0 0 otherwise .
For simplicity we describe the columns of the mixed state M c using the same attributes as those used to qualify the parity-bare state c from which they come from (affected or unaffected,parity 0, 1 or 2). The unaffected columns of M c of parity 0 are passive while those of parity 1 or 2 have only one active coordinate.

The unit (ρ -1 (M c ), M c ) is the first unit of the unit-list. Other units are added to complete the unaffected columns of M c as represented in Figure 10. They are of types 1, 2, 3, 4 (see Section 5.1) or 5. x,z := ρ -1 (m (x,1,z) ), m (x,1,z) .

Finally, we generate the trail cores ⟨ρ -1 (c * ), θ(c * )⟩ from the differences c * that are compatible with the parity plane P (c) and with the descendants of M c reached during the tree traversal.

Unaffected column of parity 0 Unaffected column of parity 1 or 2

D First step of the |K|K|-trail cores generation

We describe here the algorithm used to generate all the trit activity patterns a 2 of the wanted |K|K|-trail cores ⟨ρ -1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩.

We introduce a graph G to organize the necessary conditions on ρ(a 2 ) and a 2 . We denote by v (x,y,z) the pair of coordinates (x, y, z), ρ(x, y, z) . The set V defined as V := {v (x,y,z) : (x, y, z) ∈ [0, 8] × [0, 2] × [0, 26]} is the set of vertices of the graph G. A vertex of G represents a trit seen both from the point of view of a 2 and ρ(a 2 ). The graph G has two types of edges, one to visualize the necessary conditions on a 2 , the other to deal with the conditions on ρ(a 2 ). A vertex v (x,y,z) ∈ V has 6 neighbors by constraints on a 2 , given by the set N a2 v (x,y,z) := {v (3x B +i,y+j,z) : x B = ⌊ x 3 ⌋, i ∈ {0, 1, 2}, j ∈ {1, 2}}. It also has 2 neighbors by constraints on ρ(a 2 ), given by the set N ρ(a2) v (x,y,z) := {v ρ-1 ( ρ(x,y,z)+(0,i,0)) : i ∈ {1, 2}}.

We consider that each vertex of the graph G can be either active or passive. We say that a subset of V that indicates the active vertices of the graph G is an activity pattern. An activity pattern S ⊂ V of the graph G is valid if it corresponds to a pair (a 2 , ρ(a 2 )) that respects all the necessary conditions on a 2 and ρ(a 2 ), namely if for all v ∈ S, N a2 (v) ∩ S ̸ = ∅ and N ρ(a2) (v) ∩ S ̸ = ∅. Two activity patterns S and S ′ are equivalent if there exists z ∈ [0, 26] such that S ′ = {v + (0, 0, z), (0, 0, z) : v ∈ S}. Our goal is to generate all equivalence classes of valid activity patterns of the graph G that do not activate too many S-boxes.

This selection of activity patterns of the graph G is done with a traversal of a tree T . A node of this tree describes an activity pattern of G by listing all the vertices of G that belong to this activity pattern.

We introduce some notations to describe the tree T . A node L = [v 1 , . . . , v n ] of T defines an activity pattern S (L) := {v 1 , . . . , v n } of the graph G and a pair of trit activity patterns denoted by a 2 (L) , ρ(a 2 )

(L)
. If L and L ′ are two lists, we write L || L ′ the concatenation of L and L ′ . We use the following order relation on

V : for all v (x,y,z) , v (x ′ ,y ′ ,z ′ ) ∈ V , v (x,y,z) < v (x ′ ,y ′ ,z ′ ) if and only if (x, y, z) < lex (x ′ , y ′ , z ′ ). 2. If N a2 (v k-1 ) {v 1 , . . . , v k-1 } = ∅, as S 0 is valid, we have that the set N a2 (v k-1 ) (S 0 \ {v 1 , . . . , v k-1 )}) is not empty. Let v k be an element of N a2 (v k-1 ) (S 0 \ {v 1 , . . . , v k-1 )}. By the proposition P 2 (k -1), we know that v i(L k-1 ) < v k and therefore L k is a node of T . As {v 1 , . . . , v k-1 } is not valid, we have that i(L k-1 ) = i(L k ). As P 2 (k -1) holds, the proposition P 2 (k) is also true. 3. Similarly if N ρ(a2) (v k-1 ) {v 1 , . . . , v k-1 } = ∅, we choose for v k an element of N ρ(a2) (v k-1 ) (S 0 \ {v 1 , . . . , v k-1 )}. 4. Similarly if N a2 v i(L k-1 ) {v 1 , . . . , v k-1 } = ∅, we choose for v k an element of N a2 v i(L k-1 ) (S 0 \ {v 1 , . . . , v k-1 )}. 5. Similarly if N ρ(a2) v i(L k-1 ) {v 1 , . . . , v k-1 } = ∅, we choose for v k an ele- ment of N ρ(a2) v i(L k-1 ) (S 0 \ {v 1 , . . . , v k-1 )}.

D.2 Control the weight during the tree traversal

Among all the valid activity patterns of the graph G, we only need those that may lead to a trail core ⟨ρ -1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩ of weight below some limit weight W . Given a node L of T , we use Algorithm 3 to compute a lower bound on the weights of trail cores of the form ⟨ρ -1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩ with a 2 = a 2 (L) denoted by w 3-round min (L).

(L) ≤ min{w⟨ρ -1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩ : a 2 = a 2 (L) } ∆ ← {0} 729 min w box (∆) ← 0 for i = 1 to n do // see if min w box (∆) can be incremented (x, y, z), (ρ(x, y, z)) ← v i x B ← ⌊x/3⌋ newActiveBox ← true for j = 0 to 2 do if the box of ∆ containing the trit of coordinate ρ-1 (3x B + j, y, z) is already active then newActiveBox ← false if newActiveBox = true then min w box (∆) ← 1 + min w box (∆) for j = 0 to 2 do ∆[ρ -1 (3x B + j, y, z)] ← 1 w 3-round min (L) ← 2 min w box (∆) + w box (a 2 (L) ) + w box (ρ(a 2 ) (L) ) return w 3-round min (L)
The weight of a 3-round trail core ⟨ρ

-1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩ is w⟨ρ -1 (b 1 ), b 1 , a 2 , ρ(a 2 )⟩ = 2 w box ρ -1 (b 1 ) + w χ (b 1 , a 2 ) + 2 w box (ρ(a 2 )) ≥ 2 w box ρ -1 (b 1 ) + w box (a 2 ) + w box (ρ(a 2 )) .
The variable min w box (∆) of Algorithm 3 stores a lower bound on the weight w box ρ -1 (b 1 ) . The variables ∆ and min w box (∆) are only modified when adding 3 active trits to the variable ∆ also activates 3 new active boxes of ∆.

One of these 3 boxes is at the same position as an active box of ρ -1 (b 1 ). If a node L ′ of T is a descendant of another node L, the inequality w 3-round min (L) ≤ w 3-round min (L ′ ) holds. Consequently, we can prune the tree as soon as a node L such that w 3-round min (L) > W is reached.

E Extension of trail cores

In this section we present in detail our algorithms for trail core extensions.

E.2 Extensions outside the kernel

When looking for extensions outside the kernel, one has to deal with the column parity mixer θ as it does no longer act as the identity map. The main remark is that the map θ can be computed slice by slice. Depending on the direction of the extension, the extension's trits are either chosen at the input of θ or at the output.

Extensions in the backward direction

The trits of an extension (a, b) of Ext back (∆, W ) are chosen at the output of the map θ. In this subsection, we also denote by ℓ the variable whose trits are fixed slice by slice to obtain the final pair (ρ -1 • θ -1 (ℓ), ℓ) of weight w rev ρ -1 • θ -1 (ℓ) + w χ (ℓ, ∆). As the map θ -1 satisfies θ -1 (ℓ)[x, y, z] = ℓ[x, y, z] -P (ℓ)[x -1, z] -P (ℓ)[x + 1, z + 1] the vector Slice(θ -1 (ℓ), z) is determined by the values of the vectors Slice(ℓ, z) and Slice(ℓ, z + 1). We therefore choose the slices of ℓ in descending order of z-coordinate to know simultaneously the values of the slices of θ -1 (ℓ). Let z 0 ∈ [0, 26] be the coordinate of the first slice of ℓ that we choose and define for i ∈ [START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF]26], z i = z 0 -i. For i ∈ [0, 26], we introduce the set L i formed by all the vectors ℓ i ∈ Slice(z i ) that are compatible through χ with the output difference Slice(∆, z i ). The set L i is associated to the (i + 1)-th level of a tree. The cost of a vertex of this tree is computed using Algorithm 4 which introduces an auxiliary variable to compute the slices of θ -1 (ℓ). When a leaf ℓ is reached during the tree traversal, only the weight of the extension (ρ -1 • θ -1 (ℓ), ℓ) remains to be checked.

Extensions in the forward direction For an extension in the forward direction, trits are chosen at the input of the map θ, using again a variable that is chosen slice by slice and denoted by ℓ. Pairs of the form ρ -1 (ℓ), θ(ℓ) , that might constitute a forward extension, are generated by fixing the slices of the variable ℓ in descending order of z-coordinate for the same reason as in the case of a backward extension. The Property 2 of the nonlinear layer provides necessary conditions that the difference ρ -1 (ℓ) must fulfill to be compatible through

Lemma 1 .

 1 [START_REF] Mella | New techniques for trail bounds and application to differential trails in keccak[END_REF] Let T 3 be the weight up to which we want to collect the 3-round trail cores and T 1 be a parameter that can be adjusted. All |K|N |-trail cores up to weight T 3 can be generated by 1. collecting all |K|-trail cores ⟨a, b⟩ with w rev (a) ≤ T 1 and extending them forward outside the kernel, 2. collecting all |N |-trail cores ⟨a, b⟩ with w rev (a) + w dir (b) < T 3 -T 1 and extending them backward inside the kernel. All |N |K|-trail cores up to weight T 3 can be generated by 1. collecting all |K|-trail cores ⟨a, b⟩ with w dir (b) ≤ T 1 and extending them backward outside the kernel, 2. collecting all |N |-trail cores ⟨a, b⟩ with w rev (a) + w dir (b) < T 3 -T 1 and extending them forward inside the kernel. All |N |N |-trail cores up to weight T 3 can be generated by 1. collecting all |N |-trail cores ⟨a, b⟩ with 2 w rev (a)+ w dir (b) < T 3 and extending them forward outside the kernel, 2. collecting all |N |-trail cores ⟨a, b⟩ with w rev (a)+2 w dir (b) ≤ T 3 and extending them backward inside the kernel.

Fig. 1 .

 1 Fig. 1. Parity and θ-effect planes of a run of (d, z)-coordinates (0, 1) and of length 5

Fig. 2 .Fig. 3 .

 23 Fig. 2. Decomposition of an affected column of non-zero parity using the non-zero-y0 convention z

-Fig. 4 .

 4 Fig. 4. Columns overlapping

Definition 7 .Fig. 5 .

 75 Fig. 5. Parity planes and θ-effect planes of four parity-bare states that are scalarequivalent and their associated graph.

Fig. 6 .

 6 Fig. 6. Number of |K|K| trail cores of weight W such that ⌈W ⌉ = T3

  Figure 7 reports the number of 2-round trail cores that have to be collected in order to apply Lemma 1 with T 3 = 41 and T 1 = 11.

Fig. 7 .

 7 Fig. 7. Number of 2-round trail cores for different cost functions. Trail cores are considered in the three graphs up to z-invariance. In the second graph, trail cores are also considered up to scalar-equivalence.

Fig. 8 .

 8 Fig. 8. Number of 3-round trail cores of weight W such that ⌈W ⌉ ≤ T3 for different parity profiles.

Algorithm 1 :F n 2 Fig. 9 .

 129 Fig. 9. Different parts of the state of Troika

Fig. 10 .

 10 Fig. 10. How to complete the unaffected columns of the mixed state Mc

Algorithm 3 :

 3 w 3-round min input : A node L = [v 1 , . . . , v n ] of the tree T output: w 3-round min (L) such that w 3-round min

3 2

 3 Finding all backward extensions of a trail core C = ⟨a 1 , b 1 , . . . , a k-1 , b k-1 ⟩ of weight below some bound W ′ means finding all the pairs (a, b) ∈ F 729 that define a trail core ⟨a, b, a 1 , . . . , b k-1 ⟩ of weight below W ′ . This is equivalent to finding the set Ext back (∆, W ) := {(a, b) : b = λ(a), DP χ (b, ∆) > 0, w rev (a) + w χ (b, ∆) ≤ W } with ∆ = a 1 and W = W ′ -w⟨C⟩ + w rev (a 1 ). Similarly, extending forward a trail core under some weight constraint consists in generating a set of the form Ext for (∆, W ) := {(a, b) : b = λ(a), DP χ (∆, a) > 0, w χ (∆, a) + w dir (b) ≤ W }. We say that an element of Ext back (∆, W ) (respectively Ext for (∆, W ) ) is a backward (respectively forward) extension of weight w rev (a) + w χ (b, ∆) (respectively w χ (∆, a) + w dir (b)).To explain the algorithms, we introduce the subspacesBox-col(x B , z) = ⟨e (3x B +i,y,z) ⟩ (i,y)∈[0, 2]×[0, 2] and Slice(z) = ⟨e (x ′ ,y ′ ,z) ⟩ (x ′ ,y ′ )∈[0, 8]×[0, 2] . Given a state A, we define the states Slice(A, z) := (x ′ ,y ′ )∈[0, 8]×[0, 2] e (x ′ ,y ′ ,z) A[x ′ , y ′ , z] and Box-col(A, x B , z) := (i,y ′ )∈[0, 2]×[0, 2] e (3x B +i,y ′ ,z) A[3x B + i, y ′ , z].The algorithms used to extend a trail core outside the kernel in the forward and backward direction or inside the kernel in the backward direction follow the same principle to control the extensions' weight. Since the functions ρ and θ of the linear layer λ = θ • ρ are permutations, we can fix the trits of a pair (a, b) where b = λ(a), by choosing either the value of a, ρ(a) or b. The idea is to look for the pairs (a, b) that belong to some set Ext for (∆, W) or Ext back (∆, W) by choosing the value of a, ρ(a) or b step by step (e.g. slice by slice or box-column by box-column). These algorithms use a particular direct sum of F 729 3 -namely z Slice(z) orx B ,z Box-col(x B , z) -denoted here with the general notation k i=1 S i . A variable ℓ, that represents either the value of a, ρ(a) or b, is said to be valid if it corresponds to an extension that we are looking for. The algorithms are based on the fact that there exist some interesting sets L 1 ⊂ S 1 , . . . , L k ⊂ S k such that every valid ℓ can be decomposed as ℓ = k i=1 ℓ i , whereℓ i ∈ L i for all i ∈ [1, k]. The set { k i=1 ℓ i : (ℓ 1 , . . . , ℓ k ) ∈ L 1 × . . . × L k } is seen as the set of the x B ,z c(ℓ x B ,z ) -2 (wt(δ) -w box (δ)) ≤ 2 w box (ρ -1 (ℓ)) + w χ (ℓ, ∆).For a level k ∈ [1, 81] of the tree, a node ℓ k of this level has the form k i=1 ℓ x B i ,zi where ℓ x B i ,zi ∈ L x B i ,zi for all i ∈[1, k]. The cost of ℓ k , that is a lower bound on the weights of the leaves reachable from ℓ k , is given by k i=1 c(ℓ Bi,zi ) + 81 i=k+1 min{c(d) : d ∈ L x B i ,zi } -2 (wt(δ) -w box (δ)) .

https://github.com/MargotFunk/troikaDifferentialCryptanalysis

The root of T is the empty list. Children of a node of T are given by Algorithm 2, in order to have in the tree all the desired activity patterns. ;

D.1 Proof that all desired activity patterns are in the tree

We want to show that if S ⊂ V is a valid activity pattern of the graph G, then it exists a node L of the tree T such that S (L) is equivalent to S.

Let n be the cardinality of the valid activity pattern S ⊂ V and let v (xmin,ymin,zmin) be the smallest element of S. We define the set S 0 := {v (x,y,z-zmin) : v (x,y,z) ∈ S}. We can numbered the elements of S 0 from v 1 to v n so that for all k ∈ [1, n], the list L k defined as L k := [v 1 , . . . , v k ] satisfies the propositions: leaves of a tree, where the first level corresponds to the choice of ℓ 1 ∈ L 1 , the second level deals with the choice of ℓ 2 ∈ L 2 etc. It is generally not necessary to reach the last level of the tree to realize that the path leads to leaves that have a weight too large. Extensions are generated with a tree traversal, during which we compute a lower bound on the weights of the leaves that can be reached from the current vertex. The tree is pruned as soon as this lower bound, called the cost of the vertex, is too high.

The algorithm that deals with forward extensions inside the kernel takes advantage of the very strong requirement that an extension (a, b) ∈ Ext for (∆, W ) must satisfy to have at the same time the difference a with the same box-activity pattern as ∆ and the difference b inside the kernel. The χ-compatibility and the weight constraint are only checked subsequently.

E.1 Backward extensions inside the kernel

We denote by ℓ the variable used to gradually generate the difference b of a pair (a, b)

z is empty, then it do not exist a backward extension in the kernel. That happens for instance if the difference ∆ has a box-column with exactly one active box. If none of the sets L x B ,z is empty, the sets L x B ,z define a tree as explained above. A leaf ℓ of this tree verifies ℓ ∈ K and DP χ (ℓ, ∆) > 0. Only the leaves of weight w rev (ρ -1 (ℓ)) + w χ (ℓ, ∆) below W must be reached.

Let ℓ = x B ,z ℓ x B ,z , where (ℓ 0,0 , . . . , ℓ 2,26 ) ∈ L 0,0 ×. . .×L 2,26 , be a leaf of the tree. During the tree traversal, for each coordinate (x B , z), we know the exact contribution of ℓ x B ,z to the weight w χ (ℓ, ∆), that is w χ (ℓ x B ,z , Box-col(∆, x B , z)). However, without the knowledge of the whole vector (ℓ 0,0 , . . . , ℓ 2,26 ), we cannot know the exact contribution of ρ -1 (ℓ x B ,z ) to the weight w rev (ρ -1 (ℓ)) = 2 w box (ρ -1 (ℓ)). Indeed, two differences ρ -1 (ℓ x B ,z ) and ρ -1 (ℓ x ′ B ,z ′ ) can have an active trit in the same box. Therefore, it is not possible to assign to ρ -1 (ℓ x B ,z ) a precise number of box activations. We consider roughly that a vector ρ -1 (ℓ x B ,z ) activates as many boxes as its number of active trits. Given an element ℓ x B ,z of L x B ,z , we define its contribution to the total weight w rev (ρ

, where wt stands for the Hamming weight. This overestimation needs to be corrected in order to have a lower bound on the weight of the extension (ρ -1 (ℓ), ℓ). Let δ = ρ -1 (box(∆)). As the set of active coordinates of δ contains all the active coordinates of ρ -1 (ℓ)

This is equivalent to

χ with the input difference ∆. More precisely, it indicates the activity or passivity of some trits of ρ -1 (ℓ) and specifies the value of some other trits. As the map ρ only permutes trits, conditions on the slices of ℓ directly follow. We write z 0 ∈ [0, 26] for the coordinate of the first slice of ℓ that is chosen and z i = z 0 -i for i ∈ [START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF]26]. For i ∈ [0, 26], the i + 1-th level of the tree is given by the set that contains all the vectors of Slice(z i ) satisfying the constraints stated above.

During the tree traversal, it is necessary to ensure that the path will lead to a leaf ℓ such that ρ -1 (ℓ) has the same box-activity pattern as the difference ∆ and of weight w χ (∆, ρ -1 (ℓ)) + w rev (θ(ℓ)) not too high. An algorithm similar to Algorithm 4 is used to compute a lower bound on the weights of the χ-compatible leaves that descend from a particular vertex. A leaf ℓ of this tree does not necessarily satisfy DP χ (∆, ρ -1 (ℓ)) > 0. This condition needs to be checked each time a leaf is reached.

E.3 Forward in-kernel extension

We present the method used to generate the set

formed by all differences a satisfying DP χ (∆, a) > 0 and ρ(a) ∈ K.

Filtering phase A filtering phase is first applied to identify cases of impossible extensions. During that step, some coordinates of the differences a ∈ A ∆ that are necessarily active and some that are necessarily passive are identified.

For all a ∈ A ∆ , the box activity pattern of a is equal to that of ∆. Moreover, since the difference ρ(a) belongs to the kernel, it cannot have a column with exactly one active trit. This is why, using Algorithm 5, it may be possible to conclude from the box activity pattern of the difference ∆ that the set A ∆ is Algorithm 5: First filter input : The difference ∆ output: false if it can be deduced that A∆ is empty; Otherwise, a difference ä such that the implication ä[x, y, z] = 0 =⇒ a[x, y, z] = 0 holds for all a ∈ A∆ and (x, y, z) empty. If the difference ∆ passes this filter, the algorithm outputs a variable ä that indicates trits of the differences a ∈ A ∆ that are necessarily passive.

A second filter is applied if the difference ∆ passes the first one. If the difference ∆ has boxes whose values belong to the set {(0, 0, 1), (0, 0, 2), (1, 0, 0), (2, 0, 0)}, it is possible to locate, using Property 2 (see Section 3), some trits of the differences a ∈ A ∆ that are necessarily active. If there are after this step trits that are simultaneously necessarily active and passive, the set A ∆ is empty.

Finally, from the difference ä returned by Algorithm 5, it may be possible to deduce other trits of a and ρ(a) that must be active. If a box of ä has a unique active coordinate, we conclude that this is an active coordinate of a. Indeed, the box of a containing that coordinate must be active, and this trit is the only one of the box that can be active. Moreover, if a column of ρ(ä) has exactly 2 active trits and one of them is necessarily active, then the second is also necessarily active.

Extension phase If the difference ∆ passes the filtering phase, an extension phase is performed. It consists in scanning all pairs of the form (a, ρ(a)) with ρ(a) ∈ K that also respect the constraints deduced during the filtering phase. We test for each pair if the output difference a is compatible with the input difference ∆ through χ.