Iain S Duff
email: i.s.duff@rl.ac.uk

Bora Uc ¸ar

ON THE BLOCK TRIANGULAR FORM OF SYMMETRIC MATRICES *

Keywords: sparse matrices, block triangular form, Dulmage-Mendelsohn decomposition, maximum cardinality matchings AMS subject classifications. 05C50, 05C70, 05D15, 65F50

We present some observations on the block triangular form (btf) of structurally symmetric, square, sparse matrices. If the matrix is structurally rank deficient, its canonical btf has at least one underdetermined and one overdetermined block. We prove that these blocks are transposes of each other. We further prove that the square block of the canonical btf, if present, has a special fine structure. These findings help us recover symmetry around the anti-diagonal in the block triangular matrix. The uncovered symmetry helps us to permute the matrix in a special form which is symmetric along the main diagonal while exhibiting the blocks of the original btf. As the square block of the canonical btf has full structural rank, the observation relating to the square block applies to structurally nonsingular, square symmetric matrices as well.

1. Introduction. We are interested in the block triangular form (btf) of structurally symmetric sparse matrices. We include in our study the particular case when a matrix is structurally rank deficient. Throughout the paper, A is always a structurally symmetric matrix with no all-zero rows or columns. The block triangular form is based on a canonical decomposition of bipartite graphs known as the Dulmage-Mendelsohn decomposition [START_REF] Dulmage | Coverings of bipartite graphs[END_REF] (see [START_REF] Pothen | Computing the block triangular form of a sparse matrix[END_REF] for a detailed account). When permuted into the block triangular form, the matrix A assumes the form

  H C S C V C H R A H * * S R O A S * V R O O A V   . (1.1)
As we shall see, the three blocks on the diagonal are of special importance. The block A H , formed by the rows in the set H R and the columns in the set H C , is underdetermined; the block A S , formed by the rows in the set S R and the columns in the set S C , is square and can itself have a btf with the blocks on the diagonal being all square; the block A V , formed by the rows in the set V R and the columns in the set V C , is overdetermined. As in [START_REF] Pothen | Computing the block triangular form of a sparse matrix[END_REF], we will call these three blocks horizontal, square, and vertical, respectively. In (1.1), there are no nonzero entries in the sub-diagonal blocks shown as O. If A is structurally rank deficient, the horizontal and vertical blocks are non-empty, otherwise those blocks are empty. Consider the following 3 × 3 symmetric, structurally rank deficient matrix and its btf shown on the right (we provide a summary on how to obtain the btf later):

  c 1 c 2 c 3 r 1 × × × r 2 × 0 0 r 3 × 0 0     c 3 c 2 c 1 r 1 × × × r 2 0 0 × r 3 0 0 ×   .
(1.2)

In this matrix, the square block is empty; the horizontal block has a single row r 1 and two columns c 2 and c 3 ; the vertical block has a single column c 1 and two rows r 2 and r 3 . Notice that the set of row indices in H R is equal to the set of column indices in V C , furthermore the set of column indices in H C is equal to the set of row indices in V R . In other words, the blocks A H and A V for this matrix are structural transposes of each other. One of the main results in this paper is that this last relation between the horizontal and vertical blocks of the btf holds for any structurally rank deficient, symmetric matrix. Consider now the following 3 × 3 symmetric, structurally full rank matrix with its btf shown on the right

  c 1 c 2 c 3 r 1 × × × r 2 × × 0 r 3 × 0 0     c 3 c 2 c 1 r 1 × × × r 2 0 × × r 3 0 0 ×   . (1.3)
As the matrix is full rank, the btf has only a square block which in turn has three square blocks on the diagonal. The first block has row r 1 and column c 3 ; the second block has row r 2 and column c 2 ; the third block has row r 3 and column c 1 . In this example, a block has the set of row indices equal to the set of column indices (as in the second block in the example), or the sets of row indices and column indices are disjoint and there is another block whose sets of row indices and column indices are respectively equal to the sets of column indices and row indices of the former block (as in the first and third blocks in the example). One of the main results in this paper is that this last observation on the square blocks of the btf holds for any symmetric, structurally full rank matrix.

In the following two subsections, we provide the reader with definitions (mostly standard), and necessary background material from Duff, Erisman, and Reid [4, Chapter 6], Pothen and Fan [START_REF] Pothen | Computing the block triangular form of a sparse matrix[END_REF], and Pothen [13, Section 2.7] on the computation and properties of the btf. The computation of the btf is based on maximum cardinality matchings, or just maximum matchings, in bipartite graphs (these are discussed in Sections 1.1 and 1.2). We discuss two transformations on maximum matchings of symmetric matrices in Section 2. One of the transformations is used in [START_REF] Duff | Strategies for scaling and pivoting for sparse symmetric indefinite problems[END_REF]; the other is based on the notion of cycles of a permutation, and to the best of our knowledge is discussed and used for the first time in this paper. We use these transformations to show that for a symmetric matrix there is a maximum matching with some special properties. In Section 3, we formally state the main results on the btf of symmetric matrices that we illustrated in the examples (1.2) and (1.3), 1.1. Definitions. As is common, we associate a bipartite graph G = (R ∪ C, E) with the n × n matrix A, where R = {r 1 , . . . , r n } and C = {c 1 , . . . , c n } are the two sets of the vertex bipartition, and E is the set of edges. Here, the vertices in R and C correspond to the rows and the columns of A, respectively, such that (r i , c j ) ∈ E if and only if a ij = 0. For a given i ∈ {1, . . . , n}, the row r i and the column c i are referred to as symmetric counterparts of each other. Similarly, the edges (r i , c j ) and (r j , c i ) are called symmetric counterparts of each other. When necessary, we will make it clear whether a vertex is a row or a column vertex, usually by labelling the vertex with an r or a c respectively. An edge (r i , c j ) ∈ E is said to be incident on the vertices r i and c j . Two vertices are called adjacent if there is an edge incident on both. The set of vertices that are adjacent to a vertex v is indicated by adj(v). A path is a sequence of edges of the form (v 0 , v 1 ), (v 1 , v 2 ), . . . ,

(v k-1 , v k ) . A cycle is a sequence of edges of the form (v 0 , v 1 ), (v 1 , v 2 ), . . . , (v k-1 , v k ) where v k = v 0 .
A set of edges M is a matching if no two edges in M are incident on the same vertex. In matrix terms, a matching corresponds to a set of nonzero entries no two in the same row or column. A vertex is said to be matched (with respect to a given matching) if there is an edge in the matching incident on the vertex, and to be unmatched otherwise.

Given a matching M, an M-alternating path is a path whose edges are alternately in M and not in M. We use the notation u M --→ v to denote that vertex u reaches vertex v with an M-alternating path (we assume that u and v are different, in other words an alternating path has at least one edge). Note that this is a bidirectional relation in an undirected graph: if

u M --→ v, then v M --→ u.
An alternating path is called an augmenting path, if it starts and ends at unmatched vertices.

The cardinality of a matching is the number of edges in it. A maximum cardinality matching or a maximum matching is a matching of maximum cardinality. Given a bipartite graph G and a matching M, a necessary and sufficient condition for M to be of maximum cardinality is that there is no M-augmenting path in G (the result is due to Berge [START_REF] Berge | Two theorems in graph theory[END_REF] and is also summarized in different places, see for example [START_REF] Lovasz | Matching Theory[END_REF]Chapter 1]).

We use mate(v), to denote the vertex matched to the vertex v in a matching M, e.g., if mate(r i ) = c j , then we also have mate(c j ) = r i . We use •, • to differentiate a matching edge from an ordinary edge, e.g., we use r i , c j or c j , r i to denote that the row r i is matched to the column c j . We say a vertex set X is completely matched to another one Y , if for all x ∈ X, we have mate(x) ∈ Y ; for clarity we note that |X| ≤ |Y |, where | • | denotes the cardinality of a set. Some of the definitions in this paragraph can be found in [START_REF] Marcus | A Survey of Matrix Theory and Matrix Inequalities[END_REF]. Let A be an n × n matrix, and I and J be two subsets of {1, . . . , n}. The matrix formed by selecting the rows and columns indexed by I and J , respectively, is called a submatrix of A confined to the rows in I and the columns in J . The matrix A is said to be partly decomposable if it contains an s × (n -s) zero submatrix, for s ≥ 1. More explicitly, A is partly decomposable if there exist permutation matrices P and Q such that

P AQ = B C O D ,
with B and D being square. If A contains no s × (n -s) zero submatrix for s = 1, . . . , n -1, then it is called fully indecomposable, also called irreducible [START_REF] Duff | Direct Methods for Sparse Matrices[END_REF]. We note for later use that an n × n symmetric matrix A, where n > 2 and n is odd, a ij = a ji = 0 for i = 1, . . . , n and j ≡ i + 1 (mod n), and a ij = a ji = 0 elsewhere, is fully indecomposable. The bipartite graph of this matrix is a cycle on 2n vertices with n row vertices and n column vertices. Any n × n matrix B whose sparsity structure is a superset of that of A, i.e., b ij = 0 if a ij = 0, is also fully indecomposable.

1.2. Computation and properties of the block triangular form. Algorithms to compute the btf of a matrix have been available for some time, see for example [START_REF] Duff | An implementation of Tarjan's algorithm for the block triangularization of a matrix[END_REF][START_REF]Two algorithms for bipartite graphs[END_REF][START_REF] Pothen | Computing the block triangular form of a sparse matrix[END_REF]. The first step of these algorithms is to find a maximum cardinality matching M on the bipartite graph representation of the given matrix. Then, the row and column vertices are classified using the following equations based on alternating paths with respect to M (the equations are rephrased from [13, Section 2.7]):

U C = {c ∈ C : c is unmatched} U R = {r ∈ R : r is unmatched} H R = {r ∈ R : r M --→ u for some u ∈ U C } V C = {c ∈ C : c M --→ u for some u ∈ U R } H C = {c ∈ C : c M --→ u for some u ∈ U C } V R = {r ∈ R : r M --→ u for some u ∈ U R } H C = U C ∪ H C V R = U R ∪ V R S R = R \ (H R ∪ V R ) S C = C \ (H C ∪ V C ) .
For completeness, we provide Algorithm 1 that finds the set of rows H R and the set of columns H C of the horizontal block. The algorithm grows the row set H R and the column set H C by running a graph search algorithm. At a column vertex c known to be in H C (whose adjacency is not explored yet), it adds all neighbouring rows to H R . At a row vertex r known to be in H R , the algorithm only visits the column v = mate(r) and adds v to H C if it is not already there. for each row vertex r ∈ adj(c) \ HR do if column v / ∈ U ∪ HC then 10:

Algorithm 1 Algorithm to find horizontal block of the btf

U ← U ∪ {v}
A similar algorithm is run to find the rows and columns in the vertical block. In this case, at a column vertex in V C , only its mate is visited and added to V R , if necessary; at a row vertex in V R , the neighbouring columns are added to V C , whenever necessary. After finding the rows and columns of the horizontal and vertical blocks, the remaining rows and columns are marked to be in the sets S R and S C , respectively.

We note the following properties of the block triangular form without proving them. The proofs can be found in [START_REF] Duff | On permutations to block triangular form[END_REF], [START_REF] Duff | Direct Methods for Sparse Matrices[END_REF]Chapter 6] and [13, Section 2.7]. These properties hold for any matrix.

Fact 1.1. The rows in H R are completely matched to the columns in H C . The columns in S C are completely matched to the rows in S R and vice versa. The columns in V C are completely matched to the rows in V R .

Fact 1.2. The block triangular form is unique. In other words, any maximum matching yields the same sets H R , H C , S R , S C , V R , and V C .

The previous two properties also imply that all entries of a maximum matching should reside in the blocks on the diagonal of the btf.

Fact 1.3. In the block triangular form of a structurally rank deficient, square matrix (not necessarily symmetric), the horizontal and vertical blocks both should be present. The square block may be missing.

It may be possible to decompose the three blocks on the diagonal A H , A S , and A V further into smaller submatrices, resulting in a fine decomposition. In the fine decomposition, the horizontal and vertical blocks have block diagonal structure where the individual blocks on the diagonal are horizontal and vertical, respectively. In a given block, each vertex (row or column vertex) can reach all the other vertices in the bipartite graph representation of the same block.

The fine decomposition of the square block A S is obtained by identifying irreducible blocks. Essentially, the fine decomposition is achieved by including all rows and columns corresponding to the vertices in an alternating tour (an alternating cycle where one can repeat edges) in a single block. We summarise some of the properties of the fine decomposition of the square block that will be needed in the rest of the paper. Let p be the number of irreducible blocks (all of them square) in the fine decomposition of A S , and let R i and C i be the sets of row and column indices in the ith block for i = 1, . . . , p. The rows whose indices are in R i are matched to the columns whose indices are in C i . The sets R i and C i for i = 1, . . . , p are unique-they are independent of the choice of maximum matching [START_REF] Duff | On permutations to block triangular form[END_REF]. The blocks cannot be combined to yield another decomposition satisfying the properties given above. Figure 1.1 shows a symmetric matrix and the fine decomposition induced by a maximum matching shown with highlighted nonzero entries. There are two fine blocks in the horizontal and vertical submatrices and three blocks in the square submatrix. Horizontal and vertical lines are used to draw the borders of the fine blocks, and thicker lines are used to separate the square coarse block from the others.

Two transformations.

As discussed in the previous section, the btf is unique and can be obtained using any maximum matching. In this section, we discuss two processes that transform any maximum matching in the bipartite graph of a symmetric matrix into another that has some special properties. We first need a few definitions.

Definition 2.1. Given a matching, not necessarily of maximum cardinality, in the bipartite graph of a square matrix, an m-sequence is a sequence of edges r i , c j , r j , • , . . . , •, c k , r k , c , where each edge is in the matching. Notice that an edge r k , c in an m-sequence is followed by a matching edge of the form r , • . a closed m-sequence is an m-sequence where the start and end vertices are symmetric counterparts of each other. an open m-sequence is an m-sequence which is not closed.

Note that the above definitions depend on the numbering of the rows and the columns and hence it is important to use a numbering (in our case the original one) that preserves the symmetric structure.

We note that an m-sequence is not necessarily a path in the bipartite graph, as the two consecutive matching edges •, c k and r k , • are not necessarily connected by the edge (c k , r k ). Without loss of generality, we assume that an m-sequence starts at a row vertex and ends at a column vertex. Consider the matching shown in Fig. 1.1. In this figure, r 14 , c 9 , r 9 , c 1 , r 1 , c 11 forms an m-sequence. Any matching in the bipartite graph of a square matrix can be decomposed into open and closed m-sequences. In order to see this, consider the following process. Take a matching edge r i , c j , which is an m-sequence starting at row vertex r i and ending at column vertex c j ; if the symmetric counterpart c i of the starting vertex is also matched, say to r k , extend the m-sequence by the matching edge r k , c i to obtain the m-sequence ( r k , c i , r i , c j ); if the symmetric counterpart r j of the end vertex is also matched, say to c , extend the m-sequence by the matching edge r j , c and continue the process until the symmetric counterparts of the start and end vertices are also in the path so grown (obtaining a closed m-sequence) or they are both unmatched (obtaining an open m-sequence). Consider the m-sequence given above. Since the symmetric counterpart r 11 of the end vertex is not matched, we cannot add another edge to the end. Since, the symmetric counter part c 14 of the starting vertex is matched, we add r 15 , c 14 to the beginning. The symmetric counterpart c 15 of the new starting vertex is not matched, therefore we obtain an open m-sequence OS 1 = r 15 , c 14 , r 14 , c 9 , r 9 , c 1 , r 1 , c 11 . The other open m-sequence is OS 2 = r 17 , c 10 , r 10 , c 16 . There are five closed m-sequences: the first is CS 1 = r 7 , c 8 , r 8 , c 7 ; the second is CS 2 = r 20 , c 3 , r 3 , c 20 ; the third is CS 3 = r 19 , c 4 , r 4 , c 12 , r 12 , c 21 , r 21 , c 19 ; the fourth is CS 4 = r 2 , c 6 , r 6 , c 2 ; and the fifth is CS 5 = r 13 , c 5 , r 5 , c 18 , r 18 , c 13 .

2.1. Automorphic maximum matchings. We define a matching to be automorphic if it matches a set of rows to the corresponding set of columns. That is, for a matching M to be automorphic, whenever r i , c j ∈ M, the column c i and the row r j should be matched by M-not necessarily to each other.

We need the following theorem [9, Theorem 4.1, p. 191] which is a restatement of a result by Mendelsohn and Dulmage [START_REF] Mendelsohn | Some generalizations of the problem of distinct representatives[END_REF]Theorem 1].

Theorem 2.2. Let G = (R ∪ C, E) be a bipartite graph and let M 1 , M 2 be two matchings in G. Then, there exists a matching M ⊆ M 1 ∪ M 2 , such that M covers all the vertices of R covered by M 1 and all the vertices of C covered by M 2 .

Let M be a maximum cardinality matching in the bipartite graph of a symmetric matrix, and I and J be the set of row and column indices matched by M, i.e., I = {i : r i , c j ∈ M for some j} and J = {j : r i , c j ∈ M for some i}. Then, because of the symmetry of the matrix, the matching M = { r j , c i : r i , c j ∈ M} is 2.1, OS 1 on the left and OS 2 on the right, with solid lines along with some edges (dashed lines) that are symmetric counterparts of some matching edges. The dashed edges are used to modify the matching so that the edge r 10 , c 17 replaces r 10 , c 16 for OS 1 become a closed m-sequence, r 14 , c 15 replaces r 14 , c 9 , and r 11 , c 1 replaces r 9 , c 1 for OS 2 become a closed m-sequence. Combined with the existing closed m-sequences, the new maximum matching becomes automorphic as shown in Fig. 2.2, as is easily seen by observing that neither the rows nor the columns 9 and 16 is in the matching.

Permutation cycles of an automorphic matching.

An automorphic matching from I to I can be perceived as a permutation of the set I in an algebraic sense (a one-to-one and onto function). By starting from an element of the set I and by applying the permutation until the starting element is seen again, we can obtain cycles of the permutation (for more on cycles of a permutation see [2, Section 1.5]). Similarly, by following the matching edges of an automorphic matching M as r i , c j , r j , • , . . . , •, c i , we can obtain the closed m-sequences of M. Due to this correspondence, we refer to the closed m-sequences of an automorphic matching as the permutation cycles.

Note that as the permutation cycles are also closed m-sequences, they do not necessarily correspond to ordinary cycles in the underlying bipartite graph. Consider for example the permutation cycle r i , c j , r j , c i . If a ii or a jj is zero in A, then we do not have a cycle in the graph; we only have a permutation cycle. The length of a permutation cycle is the number of matching edges in it. The length 2 permutation cycles, also called transpositions [11, p.11], are of the form r i , c j , r j , c i and are of special importance. a hypothetical example. An odd permutation cycle is of odd length, and an even permutation cycle is of even length. Note that the edges of an odd permutation cycle (with length greater than one) when put together with their symmetric counterparts form a unique ordinary cycle in the bipartite graph of A. Note also that any pair of a row and a column in an odd permutation cycle is reachable from each other via two alternating paths: one starting and ending with a matching edge, the other starting and ending with an unmatched edge. For an even permutation cycle of length k, adding the symmetric edges partitions the permutation cycle into two ordinary cycles each having k/2 matching edges and k/2 non-matching edges, where the row vertices in one cycle are symmetric counterparts of the column vertices in the other one; the two cycles may be connected in the bipartite graph due to existence of other edges, but we are not interested in this possibility. Consider, for example, the length 4 permutation cycle r i , c j , r j , c k , r k , c l , r l , c i shown in Fig. 2.3. The permutation cycle is split between two ordinary cycles in the bipartite graph of A: r i , c j ,(c j , r k ), r k , c l ,(c l , r i ) and r j , c k ,(c k , r l ), r l , c i ,(c i , r j ) . As seen, each of these cycles contain 2 matching edges and 2 non-matching edges, and the row vertices in one cycle are symmetric counterparts of the column vertices in the other.

From an automorphic matching M, we construct another automorphic matching M which is composed of odd length permutation cycles and length 2 permutation cycles. We proceed as follows. First, all edges of M that form an odd permutation cycle are copied into M , e.g., for a length 3 permutation cycle of the form r i , c j , r j , c k , r k , c i , these three edges are copied into M . Then, even length permutation cycles of M are decomposed into length 2 permutation cycles, and these length 2 permutation cycles are added to M such that if r i , c j ∈ M , then r j , c i ∈ M . As noted above, the even length permutation cycles are split between two ordinary cycles in the bipartite graph when the symmetric edges are considered. By alternating the status of the edges according to the matching in one of the cycles, we can obtain length 2 permutation cycles. The decomposition of an even permutation cycle into length 2 permutation cycles is best seen in matrix terms. Consider the matching shown on the left below

        1 2 3 4 5 6 1 × * 2 * × 3 * × 4 * × 5 * × 6 × *                 1 2 3 4 5 6 1 × * 2 × * 3 * × 4 × * 5 * × 6 * ×         . ( 2.1)
In the matrix on the left of (2.1), the original matching whose entries are marked by × is automorphic and corresponds to a length 6 permutation cycle. Using the entries symmetric to the matching entries, shown with * , we obtain two ordinary cycles: first r 1 , c 2 ,(c 2 , r 3 ), r 3 , c 4 ,(c 4 , r 5 ), r 5 , c 6 , (c 6 , r 1 ) and second r 2 , c 3 , (c 3 , r 4 ), r 4 , c 5 , (c 5 , r 6 ), r 6 , c 1 , (c 1 , r 2 ) which share the original matching edges evenly. Now by taking the second cycle and alternating the status of the edges according to the matching, we obtain (r 2 , c 3 ), c 3 , r 4 , (r 4 , c 5 ), c 5 , r 6 , (r 6 , c 1 ), c 1 , r 2 . As seen, the new set of matching edges form three length 2 permutation cycles: r 1 , c 2 , r 2 , c 1 , r 3 , c 4 , r 4 , c 3 , and r 5 , c 6 , r 6 , c 5 . The resulting matching is shown on the right of (2.1). As is clear, the two matchings M and M have the same cardinality; if M is of the maximum cardinality, so is M .

Recall from Section 2.1 that after the maximum matching on the sample matrix was modified to be automorphic, three more closed m-sequences are created: CS We note that the transformation described above is performed to facilitate the proofs that will follow in the next section. They modify the matching, but do not change the matched rows or columns contrary to the transformation discussed in the previous subsection. 3. The block triangular form of symmetric matrices. As shown in the previous section, any maximum matching in the bipartite graph of a structurally singular, symmetric matrix A can be transformed into an automorphic one consisting of odd permutation cycles and length 2 permutation cycles. Therefore, we assume that we have a matching M with those properties. We recall the uniqueness of the sets H R , S R , V R , H C , S C , and V C of the block triangular form of a matrix (Fact 1.2).

Before we prove our main theorem, we start with a series of lemmata. Lemma 3.1. The odd permutation cycles are confined to only one block on the diagonal of the block triangular form.

Proof. Permutation cycles of length 1 are trivially confined to only one block. Recall from Section 2.2 that an odd permutation cycle is a part of an ordinary cycle. Since the matching edges within the ordinary cycle are in the blocks on the diagonal of the btf, having those nonzeros straddle more than one block on the diagonal can only be possible if the submatrix confined to the rows and columns of the cycle is partly decomposable. However, as noted towards the end of Section 1.1, matrices whose sparsity structure corresponds to a superset of odd length cycles are fully indecomposable.

We have a result which is stronger than the previous lemma. Lemma 3.2. The odd permutation cycles are confined to the square block. Proof. From Lemma 3.1, an odd length permutation cycle is confined to a single block. Take an odd-length permutation cycle C = r i , c j , r j , • , . . . , •, c i and suppose, for the sake of contradiction, that C is in the horizontal block. Since all row vertices in C are in H R , each one of these vertices reaches an unmatched column with an alternating path. Suppose row r i reaches, with an alternating path, an unmatched column c u , i.e., r i M --→ c u without going through other vertices in the permutation cycle C (this assumption is not weaker but gives a cleaner argument). Let P = (r i , c l ), c l , r i+1 , . . . , •, r i+t , (r i+t , c u ) be that alternating path. Due to the symmetry of the matrix, the same path exist in the reverse direction from row r u to column c i . That is we have the path P T = (r u , c i+t ), (c i+t , •), . . . , (c i+1 , r l ), (r l , c i ) in the bipartite graph of the matrix. An example for the proof of Lemma 3.2. The solid bold lines correspond to edges of a maximum matching. A length 3 permutation cycle C = ` r i , c j , r j , c k , r k , c i ´is shown; the solid lines represent the edges symmetric to that of the permutation cycle. Column cu is not matched and reachable from row r i with the alternating path P = `(r i , c l ), c l , rm , (rm, cu)

´.

The symmetric path P T is shown with dashed lines. Row ru is not matched, as the matching is automorphic. Column cm should have a mate, and since it reaches an unmatched row, it should be in the vertical block. It is shown in the proof that the column cm should have been matched to r l ; this matching edge is shown with a dashed bold line. Therefore, the path `(ru, cm), cm, r l , (r l , c i ), c i , r k , (r k , c j ), c j , r i , (r i , c l ), c l , rm , (rm, cu) ´is an augmenting path, contradicting the fact that M is a maximum matching.

We now investigate the status of the edges in P T with respect to the given maximum matching M. We show that P T must be an alternating path. In other words, it must have the form P T = (r u , c i+t ), c i+t , • ,. . . , c i+1 , r l ,(r l , c i ) . Note that since r u and c u are both unmatched, P T being an alternating path implies that the path (r u , c i+t ),

c i+t M --→ c i M --→ r i M --→ r i+t , (r i+t , c u
) is an augmenting path, contradicting the assumption that M is a maximum matching. We first note that c i M --→ r i as c i and r i are in an odd permutation cycle. Note that since M is automorphic, row r u is not matched. Consider the last row vertex r i+t in P . Column c i+t is the first column vertex in P T . Since r u is not matched, c i+t should have a mate (otherwise M would not be a maximum matching). Therefore, c i+t is in the vertical block (being a matched vertex reaching an unmatched row). Now, since r i+t is in the horizontal block and c i+t is in the vertical one, due to Lemma 3.1 the vertices r i+t and c i+t cannot be in an odd permutation cycle. Therefore, they are in a length 2 permutation cycle. That is, if mate(r i+t ) = c x , then mate(c i+t ) = r x . Consider the next column vertex c i+t-1 in P T . It should have a mate, otherwise an augmenting path r u M --→ c i+t-1 exists, and should be in the vertical block. With the same reasoning as above, it is matched to the row that corresponds to the mate of row r i+t-1 in P . Therefore, the path P T is an alternating path symmetric to P . Figure 3.1 displays the arguments for a length 3 permutation cycle C = r i , c j , r j , c k , r k , c i and an alternating path P = (r i , c l ), c l , r m , (r m , c u ) .

With similar arguments, it can be shown that odd permutation cycles cannot be confined to the vertical block. Therefore, the odd permutation cycles are confined to the square block.

Corollary 3.3. For each r i , c j ∈ M in the horizontal block, we have r j , c i ∈ M. Similarly, for each r k , c l ∈ M in the vertical block, we have r l , c k ∈ M.

We have a refinement of the previous corollary. Lemma 3.4. The length 2 permutation cycles are not contained entirely in the horizontal or vertical blocks.

Proof. We prove the lemma for the horizontal block, that is we show that length 2 permutation cycles are not contained in the horizontal block; the vertical block case is similar. Suppose, for the sake of contradiction, r i , c j ∈ M and its symmetric counterpart r j , c i ∈ M are in the horizontal block. As in the proof of Lemma 3.2, we take an unmatched column c u that is reachable from row r i with an alternating path. Again, due to M being automorphic, row r u is not matched. However, as in the proof of Lemma 3.2, we have an alternating path from column c i to unmatched row r u , contradicting the fact that c i is in the horizontal block.

We are now ready to state and prove the following theorem regarding the block triangular form of a structurally rank deficient symmetric matrix.

Theorem 3.5. Given a structurally rank deficient symmetric matrix A, let H R , S R , V R , H C , S C , V C be the sets in the block triangular form of A. Then, the set of indices of rows in H R is equal to the set of indices of columns in V C ; the set of indices of the rows in S R is equal to the set of indices of the columns in S C ; the set of indices of the rows in V R is equal to the set of indices of the columns in H C .

Proof. Since A is square and structurally rank deficient, we know that both horizontal and vertical blocks are present in the block triangular form. The square block may be missing.

Consider a matching edge r i , c j in the horizontal block. As shown in Lemma 3.2, it is not in an odd permutation cycle and hence, as noted in Corollary 3.3, r j , c i ∈ M. We know from Lemma 3.4 that r j , c i ∈ M is not in the horizontal block. Two cases remain to be investigated: r j , c i is either in the square block or in the vertical block. For the sake of contradiction, suppose r j , c i is in the square block. As in the proof of Lemma 3.2, we take an unmatched column c u that is reachable from row r i with an alternating path. Again, due to M being automorphic, row r u is not matched. However, as in the proof of Lemma 3.2, we have an alternating path from column c i to the unmatched row r u , contradicting the fact that c i is in the square block. Similar arguments can be used to show that for a r k , c l in the vertical block, r l , c k is in the horizontal block. Therefore, a matching edge r i , c j is in the horizontal block if and only if the matching edge r j , c i is in the vertical block.

We have established two results. First, the set of indices of rows in H R is equal to the set of indices of columns in V C . Second, the set of column indices that are matched to the rows in H R is equal to the set of row indices that are matched to the columns in V C . These equivalence relations are shown in Fig. 3 Once the equivalence relations stated in Theorem 3.5 are established, it is easy to recover a structural symmetry in the block triangular form.

Corollary 3.6. The block triangular form of a structurally singular, symmetric matrix can be permuted to be symmetric around the anti-diagonal. This can be achieved by fixing a permutation of the rows in H R , S R , and V R , and then by reorganizing V C , S C and H C such that the reverse order within these later blocks match those of H R , S R , and V R , respectively. It is possible to refine this form by looking at the fine structure of the square block A S . We first need the following theorem.

Theorem 3.7. Let R i and C i be the set of row and column indices of the ith irreducible block in the fine decomposition of the square block A S . Then, either R i = C i ; or R i ∩ C i = ∅ and there exists an irreducible block j in the fine decomposition of A S with R j = C i and C j = R i .

Proof. Take the ith irreducible block and suppose for the sake of contradiction R i = C i and R i ∩ C i = ∅. Define three sets: first I = R i ∩ C i , second I 1 = R i \ I, and third J 2 = C i \ I. With this partitioning of the rows and columns, we can permute the ith irreducible block into the following form

A i = I J 2 I A 11 A 12 I 1 A 21 A 22 . (3.1)
First note that A 12 = O and A 21 = O, otherwise the block will be reducible. Now consider the larger square submatrix consisting of the set of row indices I ∪ I 1 ∪ J 2 and the same set of column indices

A L =   I J 2 I 1 I A 11 A 12 A T 21 I 1 A 21 A 22 * J 2 A T 12 * A T 22   . (3.2)
For the columns whose indices are in the set I 1 and the rows whose indices are in the set J 2 to be in a different block from i, the submatrix of A L defined by the row indices I ∪ J 2 and the column indices I ∪ I 1 should be reducible. But the matrix is the transpose of A i (see (3.1)), as A 11 = A T 11 . Since A i is irreducible, so is its transpose shown in (3.3). Therefore, the rows whose indices are in the set J 2 and the columns whose indices are in the set I 1 cannot be in a different block from the one that contains I.

I I 1 I A 11 A T 21 J 2 A T 12 A T 22 (3.3)
We have established that either

R i = C i or R i ∩ C i = ∅. If R i ∩ C i = ∅,
all matching nonzeros in this block should be in length 2 permutation cycles, as the odd permutation cycles are irreducible. Therefore, we have another irreducible block j with R j = C i and C j = R i and the proof is completed.

Having defined the fine structure of the square block A S , we refine Corollary 3.6 by using that structure. As before, let R i and C i denote the set of row and column indices of the ith irreducible block of A S . We will order the rows of A and then apply that order in the reverse direction to the columns. We first order the rows in the horizontal block. Then, we order the rows in square block A S using the fine structure as follows. Let i be an irreducible block whose rows are yet to be ordered. If the set of column indices C i is equal to the set of row indices R i , order R i . If C i ∩ R i = ∅, order R i and then the rows that are symmetric counterparts of the columns whose indices are in the set C i . After this blockwise ordering of all the rows in the square block A S , we order the rows in the vertical block. We do not specify the order of the rows in a subblock-it can be arbitrary. Now applying the order obtained for the rows to the columns in the reverse direction results in a matrix that is symmetric along the anti-diagonal. Figure 3.3 shows the matrix of the previous figures permuted to be symmetric around the anti-diagonal. We emphasize that the matching itself is not symmetric around the anti-diagonal because of the odd permutation cycle on indices 5, 13, and 18. The matching entries can be placed to be symmetric around the anti-diagonal, but then the symmetry in other parts of the matrix can be lost.

Notice that one can also permute the matrix so that the resulting matrix is symmetric along the main diagonal; this time by ordering the rows as described above and then by applying the same permutation to the columns. The resulting permuted matrix is shown in left side of Fig. We note that Theorem 3.5, Corollary 3.6, and Theorem 3.7 hold for structurally full rank, symmetric matrices. In particular, the fine decomposition of such a matrix has square irreducible blocks with a row index set R i and a column index set C i where either R i = C i or there exists another irreducible block j (with row index set R j and column index set C j ) with R j = C i and C j = R i .

4. Concluding remarks. We have presented observations on the block triangular form of structurally symmetric matrices. The two main results are that (i) if the matrix is structurally rank deficient, the horizontal and vertical blocks are transposes of each other, (ii) each block in the square submatrix has the same set of row and column indices or those two sets are totally disjoint and there is another square block being the transpose of the first one. These symmetrical structures help us recover the symmetry of the original matrix in the Dulmage-Mendelsohn decomposition (or in the block triangular form).

We note, for historical reasons, that Dulmage and Mendelsohn note (at the last paragraph in their seminal paper [START_REF] Dulmage | Coverings of bipartite graphs[END_REF]) that they think it may be worthwhile to study the decomposition for symmetric bipartite graphs. We think that the observations in this paper could address some of their concerns.

4 : 5 :

 45 Input M: a maximum matching; mate(v) giving the mate of a vertex v Output HR and HC : the set of rows and columns of the horizontal block 1: HR ← HC ← ∅ 2: U ← {unmatched columns} 3: while U = ∅ do Pick a column vertex c ∈ U and set U ← U \ {c} HC ← HC ∪ {c} 6:

7 :HR ← HR ∪ {r} 8 :

 78 v ← mate(r) should exist; otherwise flags an augmenting path 9:

Fig. 1 . 1 .

 11 Fig. 1.1. A symmetric 21 × 21 matrix with a structural rank of 19 and its Dulmage-Mendelsohn ordering induced by a maximum cardinality matching shown with highlighted nonzeros.

Fig. 2 . 1 .

 21 Fig. 2.1. The two open m-sequences are shown with solid lines. The set of row indices and column indices are extended to have the same set of row and column vertices. Dashed lines are symmetric counterparts of some matching edges; they are used to update the matching such that the new matching is automorphic. The new matching edges for the left subfigure is ` r 17 , c 10 , r 10 , c 17 ´, and the new matching for the right subfigure is ` r 15 , c 14 , r 14 , c 15 , r 1 , c 11 , r 11 , c 1´.

  Figure 2.3 displays permutation cycles of length 1 to 4 in

Fig. 2 . 2 .

 22 Fig. 2.2. An automorphic maximum matching is shown with highlighted nonzeros.

Fig. 2 . 3 .

 23 Fig. 2.3. Permutation cycles of an automorphic matching. The matching edges are shown with bold solid lines. The other edges, shown with dashed lines, are present because of the symmetry of the matrix. Matching edges of the form r i , c i give a permutation cycle of length 1 (first subfigure); two matching edges of the form ` r i , c j , r j , c i ´give a permutation cycle of length 2 (second subfigure); length 3 (third subfigure) and length 4 (fourth subfigure) permutation cycles are also shown.

  6 = r 17 , c 10 , r 10 , c 17 , CS 7 = r 15 , c 14 , r 14 , c 15 , and CS 8 = r 1 , c 11 , r 11 , c 1 . Among all closed m-sequences only the fifth one CS 5 = r 13 , c 5 , r 5 , c 18 , r 18 , c 13 is an odd-length permutation cycle, hence does not undergo any transformation. The closed m-sequences CS 1 , CS 2 , CS 4 , and CS 6 to CS 8 are length 2 permutation cycles, and they do not undergo any transformation. We are left with CS 3 = r 19 , c 4 , r 4 , c 12 , r 12 , c 21 , r 21 , c 19 . As CS 3 is a permutation cycle of length 4, it can be decomposed into two length 2 permutation cycles: r 19 , c 4 , r 4 , c 19 , and r 12 , c 21 , r 21 , c 12 . The resulting matching is shown in Fig. 2.4.

Fig. 2 . 4 .

 24 Fig. 2.4. The automorphic maximum matching shown contains only length-2 or odd permutation cycles.

  Fig.3.1. An example for the proof of Lemma 3.2. The solid bold lines correspond to edges of a maximum matching. A length 3 permutation cycle C = ` r i , c j , r j , c k , r k , c i ´is shown; the solid lines represent the edges symmetric to that of the permutation cycle. Column cu is not matched and reachable from row r i with the alternating path P = `(r i , c l ), c l , rm , (rm, cu)´.

. 2 .

 2 As the matching is automorphic, the set of indices of the unmatched columns (K in the figure) is equal to the set of indices of the unmatched rows (L in the figure); we have thus established the equivalence between the sets of indices of the columns in H C and the rows in V R . Since the matrix is square, the set of indices of the of remaining rows S R is equal to the set of indices of the remaining columns S C .

Fig. 3 . 2 .

 32 Fig. 3.2. A matching is shown by the slanted line; the rows in I are matched to columns in J, and the columns in I are matched to rows in J. The borders of the horizontal, square, and vertical blocks are shown with solid lines. The dashed lines divide the set of columns in the horizontal block and the set of rows in the vertical block into two sets. The index sets K and L are equal as the set of indices of unmatched columns is equal to the set of indices of unmatched rows.

Fig. 3 . 3 .

 33 Fig. 3.3. The matrix permuted blockwise so that the resulting matrix is symmetric along the anti-diagonal.

3

 3

  .4. One can further permute the matrix such that the square block of the Dulmage-Mendelsohn decomposition comes

Fig. 3 . 4 .

 34 Fig.3.4. The matrix permuted blockwise so that the resulting matrix is symmetric along the main diagonal. When the square block of the coarse decomposition is permuted before the other blocks, a block tridiagonal form is obtain using the three blocks of the coarse Dulmage-Mendelsohn decomposition, with the last block on the diagonal being void of nonzeros

Acknowledgements. We thank two anonymous referees and Cleve Ashcraft, also a referee, for their constructive comments and suggestions. Cleve also provided us with some Matlab code for the figures. We also thank Alex Pothen for his remarks on an earlier version of the paper and bringing the Mendelsohn-Dulmage theorem, restated in Section 2.1, to our attention.

* This work was supported by "Agence Nationale de la Recherche", through the SOLSTICE project ANR-06-CIS6-010.


The general context Cryptography is a computer discipline that aims to protect messages through encryption systems. In symmetric cryptography, a secret parameter, called a key, is used both to encrypt and to decrypt messages. The security provided by a symmetric encryption system is evaluated using cryptanalysis techniques which aim, for example, to find the secret key.

Quantum computer arrival could impact the cryptographic field. Indeed, in 1994, Shor exhibited that quantum computers could be used to improve assymetric cryptanalysis [START_REF] Peter | Algorithms for quantum computation: Discrete logarithms and factoring[END_REF]. With the recent breakthrough in quantum computer, the security of cryptographic primitives against quantum adversary can not be taken as guaranteed. The NIST launched a competition for new primitives that are safe even against adversaries that has access to a quantum computer. To estimate the quantum security of a cryptographic scheme, it is necessary to perform its quantum cryptanalysis. Quantum cryptanalysis techniques sometimes are quantum adaptation of classical cryptanalysis techniques. This transformation is called quantizing.

Let's note that an attack is valid if and only if it is more efficient than the naive attack. In the classical setting, the naive attack is the generic exhaustive search, in the quantum setting, it is the Grover search algorithm [START_REF]Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing[END_REF].

The research problem

The report aims to study impossible differential attacks introduced independantly by Knudsen [START_REF] Knudsen | Deal-a 128-bit block cipher[END_REF] and Biham et al. [START_REF] Biham | Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[END_REF], and then derive a valid quantizing. The authors in [START_REF] Bonnetain | Quantum security analysis of AES[END_REF], that designed a quantum attack on AES, pointed out that impossible differential technique has not been yet quantized and that its supposed efficiency was not clear.

Your contribution

In order to build a valid attack, we will split the classic attack into different steps. Each of these steps will then be modified to obtain the most efficient quantizing. A study of this effectiveness will be given through an accurate analysis of the complexity.

Arguments supporting its validity

Various examples of applications such as CLEFIA-128 [START_REF] Shirai | The 128bit blockcipher CLEFIA (extended abstract)[END_REF], AES-128 and ForkSkinny-128-256 [START_REF] Antoon | Forkae v[END_REF] will be given to understand how far the validity of quantum impossible differential attacks extends. We will also identify the factors that break the validity of the attack.

Summary and future work

The applications of impossible quantum attacks have shown that some schemes are vulnerable to quantum computer and that security with respect to impossible differential attacks is to be studied before claiming any quantum security. However, an overhead in time complexity induced by the quantizing is not negligible. Indeed, some primitives vulnerable to classical impossible attacks lose this vulnerability when transposition in the quantum world. This overhead seems to be related to the memory. Understanding how to quantify the memory operations of the classical world will reduce this extra cost and therefore provide better attacks.

1 Preliminaries

Classical impossible differential attacks

Impossible differential attacks were independantly introduced by Knudsen [START_REF] Knudsen | Deal-a 128-bit block cipher[END_REF] and Biham et al. [START_REF] Biham | Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[END_REF]. The goal of cryptanalysis technique is to recover the secret key k * , belonging to some key set K, used in the encryption scheme. This is done by discarding all the wrong keys with the help of a pair of plaintexts that leads to an impossible pattern under its encryption with the wrong key.

Building an impossible differential attack of an n-bit block cipher over r rounds mainly consists of two steps. In the first step the goal is to find a maximal length impossible differential, i.e. we want to find a pair of differentials ∆ X , ∆ Y together with an integer r imp (that we look forward to maximize) such that the probability of a difference ∆ X propagates to a difference ∆ Y after r imp rounds is 0. In this step, we also want to find two integers r in , r out such that r in + r D + r out = r. We denote by impossible pattern the quantity (∆ X , ∆ Y , r imp , r in , r out ). The second step, called the seiving phase, consists on finding two sets D in ⊂ {0, 1} n and D out ⊂ {0, 1} n . Let's denote by E the encryption oracle and E in (resp. E out ) the partial encryption function between round 0 and r in (resp r in + r imp and r ).

E in E out D in ∆ X ∆ Y D out r in r imp r out
If we are given a pair of plaintexts x, y with difference in D in and their corresponding ciphertexts E(x), E(y) with difference belonging to D out , due to the impossible pattern, we can discard any key k that verifies:

E in (k)(x) ⊕ E in (k)(y) = ∆ X ) ∧ (E -1 out (k)(E(x)) ⊕ E -1 out (k)(E(y)) = ∆ Y
The seiving phase goal is to discard as many keys as possible using many plaintexts pairs.

Remark. If we denote by K in ⊂ K the key bits involved in E in and K out ⊂ K the key bits involved in E out , we can remark that the key bits involved in the impossible key distinguisher are K in ∪ K out . Therefore our analysis is done on the subkeyspace K in ∪ K out .

The seiving phase that we will describe is inspired from [START_REF] Boura | Scrutinizing and improving impossible differential attacks: Applications to clefia, camellia, lblock and simon[END_REF]. It decompose iteself in a two steps procedure:

• Pair Generation. In this part, we focus in solving the following problem:

Data: N ∈ N, E : {0, 1} n → {0, 1} n D in ⊂ {0, 1} n , D out ⊂ {0, 1} n Question: Find N pairs (x, y) ∈ {0, 1} 2n such that x ⊕ y ∈ D in and E(x) ⊕ E(y) ∈ D out
A good analysis of this problem in the classical setting is given in [START_REF] Boura | Making the impossible possible[END_REF] with an efficient algorithm for solving it. At the end of this step, we will dispose of a set of N differential pairs. We will denote by P airs the set obtained.

• Pair Filtering. This step follows the Pair Generation, hence we dispose of a set of differential pairs. The goal of this step is to split the set of subkey K in ∪ K out into two sets : one that countains all the subkeys that have been invalidated by some pair of P airs and the another that countains the other subkey. A very interresting optimization in this step is called early abort technique. It is described in [START_REF] Boura | Making the impossible possible[END_REF]. For a given key k ∈ K in ∪ K out , the goal of this optimization is to filter these pairs only to keep the pairs that will invalidate k.

To explain how the filtering is done, we will introduced tests functions. Let's assume that -There exists sets

K 1 , • • • , K l that decompose K in ∪ K out = K 1 ⊗ K 2 ⊗ • • • ⊗ K l
These sets usually reprensent some subyte of the subkeyspace.

-There exists sets P 1 , • • • , P l such that P airs

⊂ P 1 ⊗ P 2 ⊗ • • • ⊗ P l
Together with this decomposition, we dispose of l test functions T i :

K i ⊗ P i → {0, 1}.
Example. Let's give an example of a test function. In this example based on CLEFIA-128 wich specification is given in section 3.1.1. We are looking at round 11 and 12, we note P 12 0 , P The early abort technique aim to recover the set of pairs that satisfy all the tests functions that we note:

P airs(k) = {p ∈ P airs | ∀i T i (k i , p i ) = 1}
We will assume that the tests function are build such that the following property holds: P airs(k) = ∅ if and only if there exists no pairs in P airs that invalidates k. This assumption is legitimate since it holds in practice. Then a key will be discarded if P airs(k) = ∅.

In the end, we have described a probabilistic procedure that discards a subkey k (different from the one used in the encryption) with some probability P . We denote by candidate key all the keys that have not been discarded. To recover the remaining key bits, i.e K \ K in ∪ K out , we will perform an exhaustive search on these bits and the candidate keys. Let's remark that if there is less key candidates than |K in ∪ K out | then the exhaustive search on the key candidate and the remaining key bits will be more efficient than the exhaustive search on the whole key space. If the procedure discards a certain amount of keys, an attack will be valid if and only if its seiving procedure is more efficient than the naive exhaustive search. In the following section, we will discuss about the complexity analysis of this procedure.

Complexity analysis

In this section, we will provide both the data complexity and the time complexity of the impossible attack described in the previous section.

Data complexity

In impossible differential attacks, the data complexity is completly determined by the cost of building the set P airs. Hence, it is enough to estimate the size of P airs : N . Considering a differential pair with input difference in D in and output difference in D out , we denote by c in the nuber of bit conditions for a pair to propagate to a difference of ∆ X at round r in , and c out the number of bit condition to reach a difference of ∆ Y at round r in + r D . With these notation, the probability P of discarding a bad key can be written

P = (1 -2 -(c in +cout) ) N
This equation allows us to write

N = O(ln(1/P ) • 2 c in +cout )
For instance, if we want to get only one subkey in the end, it is enough to ask for arround

P = 1 |K in ∪Kout therefore N = O(2 c in +cout • log(| K in ∪ K out ) |).

Time complexity

To study the time complexity of the attack, we need to emphasize that the search of the impossible differential pattern is not involved here. We suppose as it is common in the litterature that a good impossible differential pattern is already known. The complexity of the attack is mainly determined by the seiving phase. We detail here the complexity of all its steps.

• Pair Generation. To estimate the complexity of this part, it is necessary to introduce some notation for the cardinality of ∆ in and ∆ out . For the following, we will note

2 ∆ in = |D in | and 2 ∆out = |D out |.
The complexity of the Pair Generation problem was studied in [START_REF] Gilbert | Super-sbox cryptanalysis: Improved attacks for AESlike permutations[END_REF] for the special case where N = 1. The complexity for finding one such pair with acess to encryption oracle is given by:

C 1 = max min ∆∈{∆ in ,∆out} √ 2 n+1-∆ , 2 n+1-(∆ in +∆out)
Then to build N pairs, we could use the previous technique N times and get a complexity of N • C 1 . However, as shown in [START_REF] Boura | Scrutinizing and improving impossible differential attacks: Applications to clefia, camellia, lblock and simon[END_REF], with acess to encryption oracle, it is possible to reduce this complexity to:

C N = max min ∆∈{∆ in ,∆out} √ N 2 n+1-∆ , N 2 n+1-(∆ in +∆out)
• Pair Filtering.

Lemma 1. Given a set of differential pairs, checking if P airs(k) is empty for all key can be done in time

|K 1 | (|P 1 | + |K 2 | (|P 2 | + |K 3 |(|P 3 | + • • • |K l ||P l | ) )
The procedure is described in [START_REF] Boura | Making the impossible possible[END_REF], it essentially consists of first guessing the key partial key k 1 ∈ K 1 and then by using an exhaustive search on P 1 to find all the pairs that satisfy T 1 . Then we gess k 2 ∈ K 2 and repeat the process until we make the exhaustive search on P l . At this point, the remaining pairs are the elements of P airs(k), hence it is enough to check if there is any pair left.

Remark. This time complexity can be reduced if an efficient data structure is used. For instance, using lookup table could help to improve the complexity.

In the end, the total complexity is the sum of the complexity of the two steps:

|K 1 | (|P 1 | + |K 2 | (|P 2 | + |K 3 |(|P 3 | + • • • |K l ||P l | ) ) + C N + P • 2 |K|
The quantity P • 2 |K| corresponds to the exhaustive search that is perform at the end to recover all the bits of the secret key.

Quantum preliminaries

In this section, we will introduce some quantum tools and describe the most important quantum adversary models that are usually considered. All the normalization terms are omitted for a better readability.

Quantum computing

We will remind here some basis of quantum computing, a better introduction to the subject is given in [START_REF] De | Quantum computing: Lecture notes[END_REF].

Qubits. In a classical computer, the unitary units of computation are bits and their value can either be 0 or 1. In a quantum computer, bits are replaced by qubits that can be a superposition of two states |0 and |1 . Therefore, a qubit is represented by a vector of a Hilbert space:

α |0 + β |1
where α, β ∈ C and |α| 2 + |β| 2 = 1. α and β are called amplitude, the quantity |α| 2 and |β| 2 corresponds to the probability to retrieve |0 or |1 when the qubit is measured. Hence, |0 and |1 are the basis of this Hilbert space.

Entanglement. Combining two qubits, vectors of H, creates a system belonging to H ⊗ 2 . Indeed, any system of two qubits can be describe by a superposition over the following states |00 ,|10 ,|01 and |11 . It is important to remark that there is a strict difference between H 2 and H ⊗ 2 . Therefore a system of two qubits can't always be described by a pair of qubits.

Quantum algorithm. In this standard model of quantum computing, a quantum algorithm is a sequence of elementary operations: quantum gates. A good example of quantum gate is the Hadamard gate that performs the following transformation:

H ⊗ n : |x → 1 √ 2 n y∈{0,1} n (-1) x•y |y
Each of the gate can be represented by a unitary and reversible operation, therefore each algorithm is a unitary and reversible operation. A consequence of this property is that there exists no algorithm that copies a qubit, since the copy operation is not unitary. Therefore, to duplicate a qubit, it is necessary to repeat the process that creates it. The quantum computation ends with a measurement that will make the quantum state collapse to an element of the basis.

Models

There exist several models that aim at modelizing quantum adversary. With the same terminology used in [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF], we will introduce two of them that are the most often considerd.

• Q1 Model. The adversary is allowed to make quantum computations but she can only make classical queries to the encryption and decryption oracles.

• Q2 Model. The adversary can make quantum superposition queries to the encryption oracle. This model refers to IND-qCPA ("quantum chosen-plaintext") in [8, ?] Our quantum version of impossible differential attack will be placed in Q2. This is necessary if we want to give an efficient quantum optimization of the Pair Generation problem.

For the data model, we will allow the use of a quantum RAM (qRAM). The qRAM model used in the following is called classical RAM with quantum acess. It consists of storing classical information that we can query in superposition. The following quantum gate represents the qRAM

|x |0 qRAM |x |qRAM [x] Figure 1: qRAM 1.3.

Quantum Tools

In the following, we will introduce some usefull tools from quantum information theory.

1. Grover search. Grover search algorithm introduced in [START_REF]Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing[END_REF], is an algorithm that solves the followig problem:

Data: N elements including t marked elements Question: Find a marked element A precise description of this algorithm is given in [START_REF] De | Quantum computing: Lecture notes[END_REF]. The complexity associated to this problem is

O ( N t (S + C ) )
where S is the complexity of building the quantum superposition on the N elements and C is the cost of checking if an element is marked. In the classical case the complexity is

N t • C.
In the following, for any boolean function T : X → {0, 1}, we denote by Grover on T the application of Grover algorithm on the set X. The marked elements corresponds to all x ∈ X such that T (x) = 1.

2. Amplitude amplification.In [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF], the following problem is introduced:

Data: A : ∅ → Y a random quantum algorithm performing no measurement χ : Y → {0, 1} a Boolean function p the probability that χ(A()) = 1 Question: Find a element y ∈ Y such that χ(y) = 1
In the classical version of this problem, 1/p computation of A() are recquired in average. Quantummly, it is possible to solve this problem with only 1/p computations of A() as explaind in [START_REF] De | Quantum computing: Lecture notes[END_REF].

Collision finding : Ambainis algorithm. The Collision finding problem was intro-

duced by Andris Ambainis in [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF]. It consists of Data:

H : {0, 1} n → {0, 1} n a random function Question: Find two elements x, y ∈ {0, 1} n such that H(x) = H(y).
The time complexity obtain by the quantum algorithm in [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF] is O(2 n/3 ). Due to the birthday paradox, the complexity for solving this problem in the classical setting is O(2 n/2 ).

4. Quantum walk. The last problem that we will need is the quantum walk, introduced in [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF]. The problem that we're looking to solve is Data: A graph G of N vertices including an proportion of marked vertices An oracle deciding if a vertex is marked in time C Question: Find one marked vertice

The idea of the algorithm is to quantify the classical random walk algorithm:

Start at some specific vertex y on the graph. Repeat the following process a given number of times: Query the oracle to check if y is marked, if not, choose one of its neighbors at random and set y to this value.

With the approach given in [START_REF] De | Quantum computing: Lecture notes[END_REF], the classical time complexity of the procedure is

S + 1 (C + 1 δ U )
and the quantum time complexity is

S + 1 √ (C + 1 √ δ U )
where S is the complexity of building the quantum superposition on all the vertices of G, is the fraction of marked states, C is the cost of checking if a vertex is marked, δ is the spectral gap1 , G and U is the cost of updating a vertex to its neighbor.

Quantum Impossible Differential

In this section, I will present the quantized version of impossible differential attack that I developped during my internship. For this, we will provide a quantized version of the Pair Generation, the Pair filtering phases.

Pair Generation : Quantum Limited Birthday Problem

In this section we come back to the Pair Generation problem. Data:

N ∈ N, E : {0, 1} n → {0, 1} n D in ⊂ {0, 1} n , D out ⊂ {0, 1} n Question: Find N pairs (x, y) ∈ {0, 1} 2n such that x ⊕ y ∈ D in and E(x) ⊕ E(y) ∈ D out
Let's first note we consider to have acces to both the encryption and the decryption oracles. Therefore it is possible to swap the roles of D in and D out to optimize the final complexity.

In [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF] an algorithm is given to solve this problem for N = 1. The complexity reached is

Q 1 = max 2 (n-∆out)/3 , 2 (n-∆out)/2-∆ in /3
Like in the classical setting, we could pay N • Q1 to recover N pairs but there exits procedures that reduce this time complexity. In the following, such a procedure will be described.

Let's first remark that solving the Collision Finding problem provides a solution to Pair Generation. Let's pick any y ∈ {0, 1} n , we can define H y :

H y : D in → { 0,1 } n-∆out x → E(y) ⊕E(y ⊕ x) mod D out
here mod D out stands for the relation x = y mod D out ⇔ x ⊕ y ∈ D out . In practice D in and D out are correspond to subits of the plaintext and ciphertext, then mod D out can be checked by a projection on the complementary set of D out in {0, 1} n .

We remark that finding a collision for H y corresponds exactly to finding a good differential pair for E. We will denote by structure any function H y that follows the pattern previously described.

Lemma 2. Let H : {0, 1} n → {0, 1} m be a function such that H has 2 2c collision pairs. Let c < 2c, there exists a quantum algorithm which outputs 2 c such collisions in time and memory 2 Proof. We will give a quantum algorithm that achieves the complexity goal. It consists of a quantum walk. First, let r ∈ N be some integer such that 2 r << 2 n . We will walk on the graph G = <V, E > with

1. V = {1, • • • , 2 n } 2 r , i.e 2 r -tuples of integers of {1, • • • , 2 n }. 2. E = {(x, y) ∈ E 2 | ∃!i x i = y i }
We define the set of marked state as follows M = {x ∈ V | ∃i, j x i = x j ∧ H(x i ) = H(x j )}, hence a vertex is marked whenever it countains at least one non trivial collision. Our procedure splits in three parts:

1. Setup. First, we construct the initial uniform superposition of all vertices. We will build a superposition in each of the 2 r registers (this represents the quantum memory used in this procedure).

2. Quantum walk. Then, we will perform a walk on the graph2 until we reach a superposition of marked states. Because there is 2 2c collision pairs, the fraction of marked vertices is given by

= 2 c+r 2 c+r-1 2 n 2 n-1 ≈ (2 c+r-n ) 2
Therefore the quantum walk needs to run 2 n-c-r steps. Furthermore, the spectral gap is estimate by δ =

2 n 2 r (2 n -2 r ) ≈ 2 -r .
3. Measurement. Once we got the quantum state |ψ corresponding to the superposition over the marked states, we compute the value of each element through H.

|ψ = (x 1 ,x 2 ,••• ,x 2 r )∈M |(x 1 , x 2 , • • • , x 2 r ) → (x 1 ,x 2 ,••• ,x 2 r )∈M |(x 1 , x 2 , • • • , x 2 r ) |(H(x 1 ), H(x 2 ), • • • , H(x 2 r ))
At this point, we perform a sort on the H side to put the collision in the two first register. Then, we will measure these two registers to get the first collision. Each of the 2 r -2 registers left collapse to the uniform superposition over the 2 n elements. Therefore by adding two registers countaining the uniform superposition, we produce the same state that we had at the beginning of step2. This way, we can repeat this process O(2 c ) times to collect the 2 c collisions.

This technique allow us to avoid the setup cost when we loop back to step2 2 c times. In the end the complexity of this algorithm is

2 r + 2 c • 2 n-c-(r/2)
By taking r = 2 3 (nc + c ), we obtain a complexity of 2

2 3 (n-c+c ) .
Remark. The exact complexity of the procedure involves a polynomial factor in n (due to the sort) that we will neglect.

Remark. Under the assumption that H : {0, 1} n → {0, 1} m follows the random oracle model, there is arround 2 2n-m collisions.

For every structure H y , we have described a way to collect collisions from which we can derive pairs. Depending on the value of N , ∆ in and ∆ out , the number of structures that we will need to consider in order to recover N pairs will be different. Indeed, for each structure we expect 2 2∆ in -(n-∆out) collisions.

1. First, we will consider N < ). Then, by applying Lemma 1, we can find N collisions for H in time:

2 2 3 (∆ in -(∆ in - n-∆ out 2 )+log 2 (N )) = 2 n-∆ out 3 + 2 3 log 2 (N ) = N 2 3 2 n-∆ out 3
2. Now, let's consider another scenario : 2 2∆ in 2 n-∆ out < 1. This part follows the ideas of [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF]. This corresponds to the case in which there is less than one pair per structure on average.

Lemma 3. If 2 2∆ in
2 n-∆ out < 1, one can retrieve a differential pair in quantum time:

2 n-∆ out 2 - ∆ in 3
and quantum memory:

2 2 3 ∆ in
Proof. Let's consider y ∈ {0, 1} n . If we apply Ambainis' algorithm to H y , we can find a Collision (if exists) in time and memory:

2 2 3 ∆ in
Then because the probability of getting a structure in which there is a differential pair is 2 2∆ in 2 n-∆ out , by applying an amplitude amplification algorithm, one can get a differential pair in time:

√ 2 n-∆out-2∆ in • 2 2 3 ∆ in = 2 n-∆ out 2 - ∆ in 3
Property 2 (Less than one pair).

If 2 2∆ in 2 n-∆ out < 1, one can retrieve N differential pairs in quantum time: N • 2 n-∆ out 2 - ∆ in 3
and quantum memory:

2 2 3 ∆ in
Remark. In this case, the final complexity corresponds to N • Q 1 .

3. There is one last scenario to consider:

1 < 2 2∆ in 2 n-∆ out < N .
Here, we will need to consider multiple structures that all have severals differential pairs (we expect 2 2∆ in 2 n-∆ out pairs per structure). For the following, we will need to define n s :

n s = log 2 (N ) + n -2∆ in -∆ out
This quantity represents the number of structures that we will need to consider to recover N differential pairs. Property 3 (multiple structures).

If 1 < 2 2∆ in 2 n-∆ out < N , one can retrieve N differential pairs in quantum time N 2 2 3 (n-∆out-∆ in )
Proof. We will apply the procedure describe in Property 1 2 ns times. Each times, we are looking to collect N = 2 2∆ in 2 n-∆ out collisions. The quantum time cost for the full procedure is

2 ns • N 2 3 2 n-∆ out 3 = 2 ns • 2 4 3 ∆ in - n-∆ out 3 = N 2 2 3 (n-∆ in -∆out)
Now that we have studied all the cases, we can consider the knowledge of both oracles and conclude: Theorem 1. Let E : {0, 1} n → {0, 1} n be a block cipher such that both E and E -1 can efficiently handle superposition queries. The Limited Birthday Problem can be solved in quantum time

Q N = max { min ∆∈{∆ in ,∆out} N 2/3 2 (n-∆)/3 , min(N 2 2 3 (n-∆out-∆ in ) , min ∆∈{∆ in ,∆out} N 2 n 2 -∆ 6 - ∆ in +∆ out 3 )}
This theorem concludes the quantum version of Pair Generation. The set P airs will be stored in a classical RAM with quantum access (qRAM). The qRAM will be set as a boolean function qRAM [p] = (p ∈ P airs) ∈ {0, 1}

Quantum Pair Filtering

The notations of section 1.1 are used here, hence P airs

= P 1 ⊗ • • • ⊗ P l and K in ∪ K out = K 1 ⊗ • • • ⊗ K l .
If classically, the goal would be to recover the set

P airs(k) = {(p 1 , p 2 , p 3 • • • p l ) ∈ P airs | ∀i T i (k i , p i ) = 1}
Quantumly, we aim to recover the superposition of the elements of this set:

k |k p∈P airs(k) |p
To lighten the notation, let's define

• S i (k i ) = {p i ∈ P i | T i (k i , p i ) = 1}.
In practice, the quantity |S i (k i )| does not depends too much on the subkey k. In our analysis, we will assume that it is constant. We will denote by

σ i = |S i (k i )|.
• Likewise, we will suppose that the cardinality of the set P airs(k) (when nonempty) does not depend too much on k. We will denote by the quantity such that 2 = |P airs(k)| .

Lemma 4. One can retrieve the vector k |k p∈P airs(k) |p in quantum time

O     i |P i | σ i   i σ i 2  
Proof. We will now describe our original approach for quantum Pair Filtering. Computing k |k p∈P airs(k) |p can be done in a 2-steps procedure. For more clarity, we start by describing the procedure for one fixed subkey. The final procedure will consider the uniform superposition on these subkeys.

• Collecting the conditions. For each i ∈ [1, l], let's pick k i ∈ K i . We can perform a Grover on the predicates T i (k i ) : P i → {0, 1} to recover the superposition of the elements of S i . The complexity of one Grover is c i (setup i + check i ) where

c i = O |P i | σ i , setup i = O(1)
and check i = O(1). Because all the tests T i are independant, the complexity for l tests is

O   l i=1 |P i | σ i  
At this point we have computed for each i ∈ [1, l] the quantum vector |k i s∈S i (k i ) |s for some k i ∈ K i . By concatenating these l vectors, we obtain

ψ k = |k s 1 ∈S 1 (k 1 ),••• ,s l ∈S l (k l ) |s 1 |s 2 • • • |s l
• Retrieving the pairs. We have built ψ k , a vector that carries the bit conditions for a pair to belong to P airs(k). To recover the superposition over P airs(k), it is enough to perform a Grover on the qRAM (seen as a boolean function) to recover the pairs that belong to the solution space i S i (k i ). This Grover search will set ψ k as initial state. Hence, the total complexity is

O     i |P i | σ i   i σ i 2  
By replacing |k by k |k in the previous procedure, we will recover k |k p∈P airs(k) |p .

Remark. Another way to proceed is to start with the superposition over the pairs and then filter with respect to the T i . The Grover tests in this case won't be independant and the final complexity will be O(

i |P i | 2 ) = O( N 2 )
which is too much.

Theorem 2. One can retrieve a candidate key in quantum time

O   |K in ∪ K out |   i |P i | σ i   i σ i 2 + Q N  
Proof. Let's describe the full procedure and its quantum complexity:

• Pair Generation. The complexity to store N pairs in the qRAM is Q N . Its precise value is given in section 2.1.

•
O   |K in ∪ K out |   i |P i | σ i   i σ i 2  
In the end, the total complexity is

O   |K in ∪ K out |   i |P i | σ i   i σ i 2 + Q N  
If N is build such that the only candidate key corresponds to the key used during encryption, by measuring the superposition over the candidate keys, we will recover k * .

To retrieve the secret key, we perform a Grover search on the missing key bits. In the end, the complexity to recover the secret key is

O   |K in ∪ K out |   i |P i | σ i   i σ i 2 + Q N + |K \ K in ∪ K out |   3 Applications

Application : 12 rounds CLEFIA-128

CLEFIA is a popular lightweight 128-block cipher designed by Shirai et al. in 2007 [16]. It is based on a 4-branch Feistel network. We will provide a short descrition of the encryption function. The best classical impossible differential attack reaches 13 rounds and it is described in [START_REF] Boura | Scrutinizing and improving impossible differential attacks: Applications to clefia, camellia, lblock and simon[END_REF]. The quantum attack that follows attempts to reach 12 rounds of CLEFIA-128. The last quantum impossible differential attack that could build works on 11 rounds.

Description

We will now describe a R rounds CLEFIA-128 encryption scheme. Let P = P 0 | P 1 | P 2 | P 3 be a 128-bit plaintext with each P i a 32-bits vectors and C be the corresponding cyphertext. A key schedule algorithm, whose description is given in [START_REF] Shirai | The 128bit blockcipher CLEFIA (extended abstract)[END_REF], is used to generate 2R round keys (Rk i ) 0≤i≤2R-1 and 4 whitening keys W k 0 • • • W k 3 that all are 32-bits vectors. F 0 and F 1 are the two round functions considered here, they are composed of an S-box followed by a linear layer M 0 for F 0 and M 1 for F 1 .

F 0 P i 0 P i 1 P i 2 P i 3 F 1 P i-1 0 P i-1 1 P i-1 2 P i-1 3 RK 2i-2 RK 2i-1
The encryption function is described in the following algorithm:

Algorithm 1 CLEFIA-128 encryption scheme Require:

P P 0 0 | P 0 1 | P 0 2 | P 0 3 ← P 0 | P 1 ⊕ W k 0 | P 2 | P 3 ⊕ W k 1 for i = 1 to R do P i 0 ← F 0 (P i-1 0 , Rk 2i-2 ) ⊕ P i-1 1 P i 1 ← P i-1 2 P i 2 ← F 1 (P i-1 2 , Rk 2i-1 ) ⊕ P i-1 3 P i 3 ← P i-1 0 end for C ← P R 0 | P R 1 ⊕ W k 2 | P R 2 | P R 3 ⊕ W k 3 return C 3.1.2 Properties of CLEFIA-128
CLEFIA-128 is a 4-branch feistel network. Therefore the scheme does not diffues very well, there is two consequences.

• It is possible to build test function that have a small domain. The filtering will then be very effective

• The diffusion of the impossible pattern to D in and D out will be small too. Hence, D in and D out tend to be small sets. The Pair Generation part might be significantly too ineffective.

Impossible Differential attack

The complexity that follows the analysis given in appendix A are the following:

• Pair Generation: 2 88

• Pair Filtering:

2 32
Since the size of the key space is 2 128 , the Grover search will find the secret key in time 2 64 . Therefore the Pair Generation part is not effective enought.

Application to AES-128

In [START_REF] Boura | Scrutinizing and improving impossible differential attacks: Applications to clefia, camellia, lblock and simon[END_REF], a classical impossible differential attack on 7 rounds of AES-128 is described which arguably proposes the best attack known on reduced round AES. Directly quantizying this attack is not going to produce a valid attack since the number of pairs considered is N = 2 68 > 2 64 . One could try to consider a version of AES-128 on 6 rounds but the complexity to generate the pairs does not decrease enough. In the end, it seems that collecting the differential pair is not possible for this scheme. However, we could generate the superposition over all the diffential pairs on the fly. This time, the complexity of filtering will be drastically increased since it will not be possible to decompose the Grover search on the test function.

In the end, AES-128 seems relatively strong to quantum impossible differential attack at first glance. In the analysis above, the impossible pattern used is borrowed from [START_REF] Boura | Scrutinizing and improving impossible differential attacks: Applications to clefia, camellia, lblock and simon[END_REF]. A sharper analysis of AES-128 security against quantum impossible should definitly use other impossible patterns.

FORKAE: SKINNY based Fork scheme

During this internship, I improved the best known classical cryptanalysis of a candidate of the NIST lightweight competition: ForkSkinny and I proposed a quntized version of this attack. In this section, we will describe the improved impossible diffential attack on ForkSkinny-128-256 and its quantizing. The attack described in the following is a relative tweakey attack: we will consider difference in the tweakey to build the attack. To the best of our knoledge, this is the best classical attack so far on this scheme, and the first quantum cryptanalysis on it.

Description

ForkSkinny-128-256 is a NIST candidate introduced in [START_REF] Antoon | Forkae v[END_REF]. It is based on the block cipher Skinny-128-256 that was introduced in [START_REF] Beierle | The SKINNY family of block ciphers and its low-latency variant mantis[END_REF]. The Skinny ciphers follow the tweakey3 framework, so each instance of plaintext P and tweakey T K produce a ciphertext C. This block cipher has an internal state of 128 bits and a tweakey of 256 bits. ForkSkinny-128-256 is a forkcipher [START_REF] Andreeva | Forking a blockcipher for authenticated encryption of very short messages[END_REF], therefore the encryption function will follow the pattern of forkciphers as represented in the following figure .  In a forkcipher, the plaintext is first encrypted during r init rounds. At this point, the forking point is reached and three options are available.

1. If option 1 is chosen, the encryption will continue on branch 1 for r 1 rounds ending up with C 1 .

2. If option 0 is chosen, some branch constant (known to the attacker) will be xored to the current state and then the encryption will continue on branch 0 for r 0 rounds ending up with C 0 .

3. The last option available is b (both), in this case the encryption scheme will produce both C 0 and C 1 .

Plaintext

C 1 C 0 r init r 1 r 0
Similar options are available when decrypting, from C b we can recover P , C 1⊕b or (P , C 1⊕b ).

In the case of ForkSkinny-128-256, r init = 21 and r 0 = r 1 = 27. As for the AES, the internal state is represented by a 4 × 4 and each cell of matrix is a byte.

Round function. Let's give a description of the round function of ForkSkinny. The operations are:

• SubCells (SC): Each of the 16 cells of the matrix is modified by a 8 × 8 Sbox. The precise description of the Sbox in given in [START_REF] Beierle | The SKINNY family of block ciphers and its low-latency variant mantis[END_REF].

• AddConstants(AC): A constant depending on the round number is xored to the internal state. Since we are building a diffential attack, these constants will cancel out. Hence, we don't need to focus on this precise piece of the round function.

• AddRoundT weakey (ART ): The tweakey material,derived from the tweakey, is xored to the two first lines of the internal state. A tweakey schedule is used to compute the tweakey material.

• Shif tRows (SR): This operation leaves the first line intact, rotates the second line by 1 cell, the third line by 2 cells and the fourth line by 3 cells.

• M ixColumns (M C): This operation acts linearly on the columns. Its action is described on the circuit of Figure 2.

Tweakey Schedule. We will describe now the tweakey schedule since it takes a crucial part in the attack. The internal state is composed of two 4 × 4 matrices of bytes. The tweakey schedule follows this pattern:

• First, the two first lines of both matrices are extracted. Then the lines with the same position are xored to build the tweakey material used in the rond function. • Then apply a cell permutation P T to both matrices. We can remark that the permutation globally swaps the two first lines and the two last lines. • Finally, a LFSR is applied only to the cells of the first two collumns of the second matrix.

It is important to remark that the LFSR used here (described in [START_REF] Beierle | The SKINNY family of block ciphers and its low-latency variant mantis[END_REF]) is linear and that there exists non zero elements of order 15, i.e ∃x LFSR 15 (x) = x. The round function used in ForkSkinny differs slightly from the block cipher SKINNY: AddConstants will now take the number of the round into account. This number of round is determined in ForkSkinny following this pattern:

From the plaintext to the forking point, the round number goes from 1 to r init then from the forking point to C 1 the rounds are numbered from r init + 1 to r init + r 1 and finally, from the forking point to C 0 , it goes from r init + r 1 + 1 to r init + r 1 + r 0 . The number of the round minus 1 corresponds to the number of iteration of the tweakey schedule applied so far. The graph shows how the tweakey schedule and the round function align one and other.

Plaintext Tweakey

C1 C0 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ W W
In [START_REF] Beierle | The SKINNY family of block ciphers and its low-latency variant mantis[END_REF], the autors remarked a property of the tweakey schedule that we will use in the attack. It is described in the following lemma: Lemma 5. Let δ be a byte such that LFSR 15 (δ) = δ. For every position i on the first two lines of a 4 × 4 matrix, if we set a difference of δ in position i for both of the tweakey matrices, there will be a cancelation of difference in the tweakey material every 30 rounds.

In the following, this cancelation property is used to optimize the impossible pattern of the impossible differential attack on ForkSkinny.

Classical impossible attack

In this section, we present an impossible differential attack on reduced round ForkSkinny with r init = 7, r 1 = 27 and r 0 = 19. Let's note that we aim to recover the tweakey that is 256 bits. Hence, our attack will be valid as long as its time complexity is smaller than 2 256 . This attack is inspired by the attack on reduced round SKINNY in [START_REF] Sadeghi | Cryptanalysis of reduced round SKINNY block cipher[END_REF] that reached up to 23 rounds. First, a description of the impossible pattern is given.

Impossible Pattern. Similarly to the attack in [START_REF] Sadeghi | Cryptanalysis of reduced round SKINNY block cipher[END_REF], a precise difference will be injected in the tweakey material so that it cancels itself at round 6 and at round 36. Lemma 6 justifies that a difference satisfying these conditions can be found.

The fork structure of ForkSkinny enables an important optimization of the impossible pattern. Indeed, this new impossible pattern is three rounds bigger than the impossible pattern presented in [START_REF] Sadeghi | Cryptanalysis of reduced round SKINNY block cipher[END_REF]. This new pattern is placed between round 4 and round 48 over the initial branch and the left branch (the 0 branch). A precise image of the impossible pattern is given in appendix B.

If in [START_REF] Sadeghi | Cryptanalysis of reduced round SKINNY block cipher[END_REF] one cancelation was used in the impossible pattern, two cancelations in a row are used in the impossible pattern for ForkSkinny. By remarking that r 1 = 27, the double cancelation is a consequence of Lemma 6. Indeed, if we place a cancelation two rounds before the forking point, another cancelation will appear two rounds after the forking point on branch 0, since 30 rounds of tweak schedule separate the two cancelations. In appendix B, a precise description of the impossible pattern is given.

Seiving. The seiving phase is mostly the same as in [START_REF] Sadeghi | Cryptanalysis of reduced round SKINNY block cipher[END_REF]. The differential path D out → ∆ Y has no changes with respect to the one in [START_REF] Sadeghi | Cryptanalysis of reduced round SKINNY block cipher[END_REF] and the differential path D in → ∆ X undergoes minor modifications. This similarity in the construction between the two attacks has as a consequence that the complexities both in memory and time of both attacks are equal. Since the attack in [START_REF] Sadeghi | Cryptanalysis of reduced round SKINNY block cipher[END_REF] has a better complexity than the exhaustive search, this new attack provides a valid attack on reduced round ForkSkinny. The precise differential path is given in appendix B.

In my intership, I designed other efficient classical impossible attacks against some other variants of ForkSkinny: Forkskinny-128-288 and Forkskinny-64-192. In this setting, the impossible pattern is placed between the two ciphertexts.

Quantum impossible attack

The quantum attack will consider a reduced ForkSkinny encryption scheme with r init = 7, r 1 = 27 and r 0 = 17. The classical attack in [START_REF] Sadeghi | Cryptanalysis of reduced round SKINNY block cipher[END_REF] can not be quantized as memory needs wouls be to hight, therefore we need to perform on this attack to build a classical attack and then quantize it. Both of these transformations induce an overhead in the time complexity. A reduction in the number of rounds seems necessary to balance this overhead. In our case, the number of rounds is reduced by 2. We will use the same impossible pattern as previously. With the 2 rounds reduction, the following update will be made r in = 3, r imp = 18 and r out = 3.

Pair Generation Let's remark that ∆ in = 32 and ∆ out = 72, c in = 24 and c out = 72 , |K in ∪ K out | = 2 144 . By using the formulae of section 3.1, we can state that N = 2 104 and Q N = 2 120 .

Filtering First, we aim to collect the conditions in the plaintext and in the ciphertext to propagate to the impossible pattern. By following the ideas of section 3.2, we introduce tests functions. First, we can introduce T ∆ in →∆ X ( resp. T ∆out→∆y ) that returns true whenever a pair of plaintexts propagates to ∆ X after r in rounds (resp. a pair of ciphertext propagates to ∆ Y after r out rounds). Even if it is not clear how to compute the tests, we can state that since the scheme is IND-CPA 4 , they are independant. The conditions in the input and the output can be searched independantly.

Let's now give a descrition of T ∆ in →∆ X . We will split the test in subtests T ∆ in →∆ X = T R 1 →R 2 ∧T R 2 →R 3 where T R i →R i+1 denotes the test that checks if the differential path is followed from R i ro R i+1 . These two tests are not independant therefore the complexity of the Grover searches will multiply one and other. Finally, each round test is a product of tests that verify byte conditions induced by M ixColumns.

A similar decomposition can be done to compute T ∆out→∆y . By putting all together, the filtering phase time complexity is:

( √ 2 8 + √ 2 8 + √ 2 16 ) × ( √ 2 8 + √ 2 8 ) × √ 2 16 + √ 2 16 √ 2 8 = O 2 20
Recover the superposition of the pairs that satifies the conditions can be done in time

2 48 /2 7 = √ 2 41
Complexity. The final complexity to the attack is

2 120 + √ 2 144 2 20 √ 2 41 + 2 256-144 2 = O(2 120 ) < 2 128
In the end, we provided a quantum impossible differential attack on 24 rounds of ForkSkinny.

Conclusion

In this report we were able to provide a quantized version of impossible differential attacks. This quantum version of impossible differential attacks is crutial for analyzing in the future the security margin of symetric primitives. We have provided several applications that was left in [START_REF] Bonnetain | Quantum security analysis of AES[END_REF] as an open problem. Also during the internship, we improved the best known attack on a NIST candidate for the lightweight competition. Both results will be submitted to well renowed cryptography conferences. Since the memory request is a major concern in quantum impossible attack, it is crutial to handle efficiently the pair generation problem to describe an efficient attack. Some scheme that are weak to classical impossible diffential attacks are loosing this weakness while transposing to the quantum world whenever it seems not possible to collect efficently the diffential pairs. A better understanding on the Pair Generation problem seems to be the best improvement towards better quantum impossible differential attacks. that for all pairs the P 2 part can be written (a, a + δ) for some vector δ. qRAM. In this attack, we will have a qRAM function with domain ∆P 1 ⊗ ∆P 2 ⊗ ∆P 3 ⊗ C 1 ⊗ ∆C 1 ⊗ ∆C 2 where C 1 corresponds to the second byte of C 1 . For every pair, we will write a 1 in the cell of the qRAM that has the corresponding difference and ciphertext.

Let's consider a fixed subkey k, i.e a 40-bits vector. Collecting conditions. ∆ in → ∆ X . We will use the state test technique as explained in [START_REF] Boura | Scrutinizing and improving impossible differential attacks: Applications to clefia, camellia, lblock and simon[END_REF]. Let's call x the 8 bits vector in the leftmost nibble before the F 0 function of round 2 and δ x the associated difference. One can remark that δ x = δP 1 and that x = y ⊕ RK 2 [0]. Therefore x can take every possible value if we choose the appropiate key RK 2 [0]. If we now look at the difference at position P 2 0 (that needs to be 0 32 ), we remark that x and δ x define δp 2 , i.e. there exists some function F k (x, δ x ) = δp 2 . Similarly, by remarking that the difference in P 1 3 is 0 32 , there exists some function G k such that G k (δp 2 ) (it does not depends of p 2 since it is constant equal to a).

∆ out → ∆ Y . With the same idea, one can find H k such that δc 2 = H k (c 1 , δc 1 ).

Retrieving the pairs. Now, we want to find the superposition on the pairs of P airs that satisfy:

• There exists some 8-bit vector x ∈ X such that δp 2 = F k (δp 1 , x)

• δp 3 = G k (F k (δp 1 )) • δc 2 = H k (c 1 , δc 1 )
Since N • 2 -(c in +cout) = 2 8 , we expect 2 8 pairs satifying the conditions (hence with our notation = 8) . Therefore retrieving the quantum superposition cost

|X| • |∆ x | • |∆C 1 | • |C 1 | 2 8 = 2 16 • 2 16 2 8 = 2 12
Now we just need to follow the procedure described in Section 2 to finish the attack. In the end, the complexity for filtering and deciding is

2 12 • 2 8+32 2 = 2 32 < 2 64
However the complexity of gernerating the pairs is Q N = 2 88 which invalidate this attack since the final complexity exceeds 2 64 . To obtain a complexity that does not exceed 2 64 , we need to consider a reduced version of CLEFIA-128 on 11 rounds. In the end, an improvement on the quantum pair geneation part is needed. The complexity reached for the filtering and deciding is still encouraging.

  Quantum impossible differential attack. Applications to CLEFIA, AES and SKINNY Nicolas David , Maria Naya-Plasencia, INRIA Paris September 2, 2019

2 3

 2 (n-c+c ) .

Figure 2 :

 2 Figure 2: ForkSkinny round function (image from [3])

Figure 3 :

 3 Figure 3: Tweakey schedule (image from [3])

Figure 5 Figure 6 :

 56 Figure 5: Impossible Pattern

  Then, the test function to propagate from round 12 to round 11 is T : P12 1 , P 12 2 , RK 23 → F 1 (P12 1 ⊕ RK 23 ) = P 12 2

	12 1 , P 12 2 , P 12 3 the internal state
	at round 12. We want no difference at round
	11 on P 11 0 , P 11 1 , P 11 3 , therefore the following
	equation holds:

F 1 (P

12

1 ⊕ RK 23 ) ⊕ P 12 2 = 0

  2 2∆ in 2 n-∆ out . Property 1 (One Structure). If N < 2 2∆ in 2 n-∆ out then one can recover N differential pairs in time N 2/3 2 If E is IND-CPA, we can suppose that H y is random for any y ∈ {0, 1} n . Then we can assume that it has 2 2∆ in 2 n-∆ out collisions (hence c = ∆ in -n-∆out 2

	n-∆ out 3	.
	Proof.

  Pair Filtering. It is possible to generate k |k p∈P airs(k) |p in time O Therefore it is enought to check if the quantum vector p∈P airs(k) |p invalidates k to decide if k is a key candidate. Here is the final test: T : k, p → p invalidates k A Grover on T will retrun the superposition over the candidate keys. The complexity of this test is

	i	|P i | σ i	i σ i 2
	as explained before. Now, for a given k, if P airs(k) = ∅, the second register of

k |k

p∈P airs(k) |p will correspond to a pair that does not invalidate k.

if we note A the normalized adjacency matrix of G and λ1 = 1 > λ2 > • • • > λN its eigenvalue, the spectral gap of G is the quantity 1 -max i≥2 λi

This graph is in fact in our case really close to the Johnson graph J(2 r , 2 n )

for tweak and key, we aim to recover the 256 bits of tweakey

computationally indistinguishable from a random oracle

A Detail CLEFIA-128

In [START_REF] Boura | Scrutinizing and improving impossible differential attacks: Applications to clefia, camellia, lblock and simon[END_REF], a classical impossible attack on CLEFIA is given. We will use the same impossible pattern, i.e ∆ X = 0 32 | 0 32 | 0 32 | (α, 0 8 , 0 8 , 0 8 ), ∆ Y = 0 32 | 0 32 | (0 8 , β, 0 8 , 0 8 ) | 0 32 and r imp = 9. However this time, we will consider r in = 2 and r out = 1. Classically, we had r in = 2 and r out = 2. In our case, the parameters of the attack are:

• ∆ in = 48. We are considering the difference on the first byte of ∆P 1 . On ∆P 2 , the shape of the differences allowed is M 0 (δ) where δ = ( * | 0 24 ) . Finally on ∆P 3 , all the 32 bit difference are allowed.

• ∆ out = 16. For ∆C 2 , differences on the first byte are considered. On ∆C 3 , the shape of the differences considered is M 1 (δ) where δ = ( * | 0 24 ).

• c in = 40 and c out = 8

Our goal is to recover the keybits of RK 1 and RK 23 [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF], hence |K in ∪ K out | = 2 40 . By taking a look at the formulae of section 2, we can remark that the Pair Generation considered here is the "less than one pair" scenario. The number of structures considered is arround 2 61 to recover N = 2 56 pairs. This 2 61 sieve will be performed on the input corresponding to P 0 and P 3 (it is legitimate since | P 0 ⊗ P 3 |= 2 64 ). Therefore there exists some 32 bit vector a such