Ernst Schulte-Geers

On CCZ-equivalence of Addition mod 2 n

Keywords: CCZ-equivalence, addition, Walsh transform, differential eq. of addition

We show that addition mod 2 n is CCZ-equivalent to a quadratic vectorial Boolean function. We use this to reduce the solution of systems differential equations of addition to the solution of a system of linear equations and to derive a fully explicit formula for the correlation coefficients, which leads to new results about the Walsh transform of addition mod 2 n . The results have applications in the cryptanalysis of cyptographic primitives which use addition mod 2 n .

Introduction

Addition mod 2 n is frequently used as one source of Boolean nonlinearity in modern block ciphers and hash functions. It is e.g. used in the ciphers FEAL, IDEA, SAFER,RC5, MARS, Twofish and the current SHA-3 finalists Skein and BLAKE. We revisit here the compatibility of addition mod 2 n (⊞) with XOR. The different aspects of compatibility of XOR with modular additions have been the subject of extensive research, mostly along the following lines: (1) The Markov chain of carries : one way to treat the approximation of addition by XOR probabilistically is to consider the Markov chain generated by the carry bits ( [START_REF] Staffelbach | Cryptograpic significance of the carry for ciphers base on integer addition[END_REF], [START_REF] Holte | Carries, combinatorics and an amazing matrix[END_REF], [START_REF] Sarkar | On approximating addition by exclusive or[END_REF], [1]). In [1] Alquié gave an explicit formula for the bias of the i-th carry bit for any fixed number n of summands.

(2) Differential cryptanalysis (DC): beginning with the DC of FEAL by Biham&Shamir [2] partial results begin to appear, but a complete (fully explicit) formula for the differential probabilities of addition mod 2 n was apparently only given in 2001 by Lipmaa&Moriai ( [5]). These authors also give efficient algorithms to compute certain maximal differential probabilities. Closely related to DC of addition are "differential equations of addition"(DEA), where a DEA is an equation of the form (x ⊞ y) ⊕ ((x ⊕ a) ⊞ (y ⊕ b)) = c (where a, b, c are given and x, y are to be found). Paul&Preneel [START_REF] Paul | Solving systems of differntial equations of addition[END_REF] studied the decision problem for systems of DEAs, showed that it is in P, and moreover gave efficient algorithms to solve such systems completely if solutions exists.

(3) Linear cryptanalysis (LC): Wallén [START_REF] Wallén | Linear approximations of addition mod 2 n[END_REF] gave a formula for the linear correlations of addition mod 2 n and undertook an in depth study of the algorithmic aspects of computing them. However, the formula is not explicit in the sense that one of its ingredients has to be computed recursively (for details, see the remark after Theorem 4 below). Another method for the computation of linear correlations of addition, applicable also in the case of more than two summands, was shown by Nyberg&Wallén in [START_REF] Nyberg | Improved linear distingusihers for snow 2.0[END_REF].

Our results

We observe that addition mod 2 n is CCZ-equivalent to a quadratic vectorial Boolean function and apply this to the circle of questions above. DC: We show that the solution of systems of DEA can be reduced to the solution of systems of very simple linear equations. In the course we give a simple re-derivation for the Lipmaa-Moriai explicit formula for the differential probabilities of addition. LC: We give a completely explicit formula for the Walsh transform of addition. We use this formula to determine maximal correlations for the case where one or two input masks are fixed. The simplicity of our results and the easiness of obtaining them indicate that CCZ-equivalence is the natural framework to treat these aspects of addition.

Prelimimaries

Notations and Conventions, Reminder

Bits and bit vectors, modular addition Throughout n is a fixed natural number.

F 2 denotes the field with the two elements 0, 1 ("bits"), F n 2 denotes the F 2vector space of bit vectors of length n. We write the elements of F n 2 as rows (i.e. 1 × n matrices) and denote them by small bold face letters. Subscripted indices denote coordinates. The left most coordinate of a bit vector x has the index 0 and corresponds to the least significant bit of x. Bit vectors are always written in the form x = (x 0 , . . . , x n-1 ),i.e. "little-endian". ⊕ denotes binary addition (of bits as well as of bit vectors). For x = (x 0 , . . . , x n-1 ) ∈ F n 2 we let x := n-1 i=0 x i 2 i ∈ N denote the natural number represented by x. Identifying bit vectors with natural numbers in this way, the addition mod 2 n of elements x, y ∈ Z 2 n gives an operation on F n 2 . We denote this "modular addition"by ⊞ (i.e. x ⊞ y ∼ = (x + y) mod 2 n ). For bit vectors x, y ∈ F n 2 we denote their bitwise AND with x ⋆ y (i.e. x ⋆ y = (x 0 y 0 , . . . , x n-1 y n-1 )), and their bitwise OR with x|y (i.e. x|y = (x 0 |y 0 , . . . , x n-1 |y n-1 )).

The all one vector is denoted by e, the bitwise complement of x then is x ⊕ e.

denotes the partial order on F n 2 defined by x y ⇔ x i ≤ y i ∀i ∈ {0, . . . , n-1} The Hammingweight (also called "length") of x ∈ F n 2 is denoted by |x|.

For any z ∈ F n 2 the set U z := {x ∈ F n 2 : x z} is an F 2 -vectorspace of dimension |z|.
The algebraic normal form (ANF) of a vectorial boolean function f :

F n 2 -→ F m 2 is given by the 2 n coefficients c f (z), z ∈ F n 2 where c f (z) := x z f (x) ∈ F m 2 . The degree of a vectorial Boolean function is deg f := max{|z| : c f (z) = 0}. A vectorial Boolean function of degree 2 is called quadratic. The k-th vector of the standard basis of F n 2 is denoted by e k , 0 ≤ k ≤ n -1. The superscript t indicates transposition of a matrix. If S ∈ F m×n 2 is a matrix and x ∈ F n 2 we let S(x) := xS t ∈ F m 2 ,
i.e. we don't distinguish in notation between S and the linear mapping defined by S w.r. to the standard bases domain and codomain.

L : F n 2 -→ F n 2 denotes the "left shift" x = (x 0 , . . . , x n-1 ) → L(x) = (x 1 , . . . , x n-1 , 0). R : F n 2 -→ F n 2 denotes the "right shift" x = (x 0 , . . . , x n-1 ) → R(x) = (0, x 0 , . . . , x n-2 ). Finally M : F n 2 -→ F n 2 denotes the (right shifted) "partial sums mapping" x = (x 0 , . . . , x n-1 ) → M (x) = (0, x 0 , x 0 ⊕ x 1 , . . . , x 0 ⊕ . . . ⊕ x n-2 ) I denotes the identity matrix. Clearly M = R(I ⊕ R) -1 = (I ⊕ R) -1 R and L = R t , R = L t

Fourier transform

We use the Fourier transform on the abelian group (F n 2 ,⊕) in the following form: We write the standard character χ of (F 2 , ⊕) (i.e. χ(0) = 1, χ(1) = -1) in the suggestive form χ(x) = (-1) x . For two binary vectors x, y ∈ F n 2 we let x • y :=

xy t = n-1 i=0 x i y i . Each y ∈ F n 2 defines a charakter χ y of (F n 2 ,⊕) by χ y : F n 2 -→ C, χ y (x) := χ(y • x) = (-1) y•x . We identify F n
2 with its character group via y ∼ = χ y . For a real function f :

F n 2 -→ R and u ∈ F n 2 we define the Fourier transform f by f (u) := x∈F n 2 f (x)(-1) u•x
We a call a mapping g :

F n 2 -→ F m 2 a vectorial Boolean function. For such a vectorial Boolean function and t ∈ F m 2 , u ∈ F n 2 we define the Walsh transform W g by W g (t, u) := x∈F n 2 (-1) t•g(x)⊕u•x .
We call the value φ g (t, u) :=

Wg(t,u) 2 n
the "linear correlation" of g at (t, u). Clearly W g = 1Gg , that is, the Walsh transform of the vectorial Boolean function g is simply the ordinary Fourier transform of the indicator function 1 Gg of the graph

G g := {(g(x), x) : x ∈ F n 2 } ⊂ F n+m 2 .

CCZ-equivalence of vectorial boolean functions

Vectorial Boolean functions h, g :

F n 2 -→ F m 2 are called CCZ-equivalent([3]) iff there is an affine-linear permutation A of F n+m 2 such that G g = A(G h )
that is, h and g are CCZ-equivalent iff the graph G h of h can be affine-linearly transformed into the graph G g of g.

CCZ-equivalence

Recursive carry computation

The "grade school method" for adding integers x, y in the binary number system is well known (see e.g. [START_REF] Staffelbach | Cryptograpic significance of the carry for ciphers base on integer addition[END_REF]). Let c j = c j (x, y) denote the carry-bit which is produced in position j -1 and added in position j and let c = c(x, y) be the carry vector produced in the modular addition of x and y. Then the grade school addition algorithm performs the following recursion: c 0 = 0 and (x ⊞ y) j = x j ⊕ y j ⊕ c j and c j+1 = x j y j ⊕ (x j ⊕ y j )c j (since a carry is produced at position j iff the majority of x j , y j , c j is 1). Clearly this also computes the carry for the addition mod 2 n if done up to j = n -1.

Linear equivalence of the modular addition graph

For cryptographic purposes one is interested in the Walsh spectrum and in the differential spectrum of modular addition. These are properties of the graph

G ⊞ := {(x ⊞ y, x, y) : x ∈ F n 2 , y ∈ F n 2 } ⊂ F 3n 2 .
In general, if for sets A, B ⊂ F m 2 and a linear permutation T the relation A = T (B) holds, then the Walsh resp. differential properties are transformed by the relations 1A (u) = 1B (T t (u))

resp.

(

1 A * 1 A )(x) = (1 B * 1 B )(T -1 (x)) (here * denotes convolution)
It is therefore of great value to observe that the graph of modular addition can be linearly transformed into the graph of a much simpler vectorial Boolean function.

To describe this let q : F n 2 × F n 2 -→ F n 2 the mapping (x, y) → M (x ⋆ y), and let G q := {(q(x, y), x, y) : x ∈ F n 2 , y ∈ F n 2 } be the graph of q. The following lemma is the basis for our results.

Lemma 1. The mapping

β : F n 2 × F n 2 -→ F n 2 × F n 2 , (x, y) → (x ⊕ c(x, y), y ⊕ c(x, y))
is a bijection with inverse

α : F n 2 × F n 2 -→ F n 2 × F n 2 , (x, y) → (x ⊕ q(x, y), y ⊕ q(x, y))
Proof. Let c = c(x, y) be the carry vector produced in the modular addition of x and y. By the grade school algorithm (see 3.1. above) we have c 0 = 0 and c j+1 ⊕ c j = (x j ⊕ c j ) • (y j ⊕ c j ) for j = 0, . . . , n -2. Thus (

I ⊕ R)(c) = R((x ⊕ c) ⋆ (y ⊕ c)) and hence c = M ((x ⊕ c) ⋆ (y ⊕ c)) = q(x ⊕ c, y ⊕ c). Since (x, y) = (x ⊕ c, y ⊕ c) ⊕ (c, c
) and since c can be computed from (x ⊕ c), (y ⊕ c) the mapping F 2n 2 ∋ (x, y) → (x ⊕ c(x, y), y ⊕ c(x, y)) ∈ F 2n 2 is injective (hence bijective). Since c = q(x ⊕ c, y ⊕ c) the inverse mapping is (x, y) → (x ⊕ q(x, y), y ⊕ q(x, y)) Theorem 1. (CZZ-equivalence of ⊞ and q) The linear mapping T :

(F n 2 ) 3 -→ (F n 2 ) 3 , (x, y, z) → T (x, y, z) = (x ⊕ y ⊕ z, x ⊕ y, x ⊕ z) maps the graph of G q bijectively onto the graph of G ⊞ . Proof. Let (x ′ , y ′ ) := β(x, y) = (x ⊕ c(x, y), y ⊕ c(x, y)) We have G ⊞ = {(c(x, y) ⊕ x ⊕ y, x, y) : x ∈ F n 2 , y ∈ F n 2 } = {(c(x, y) ⊕ x ⊕ y, x ⊕ c(x, y) ⊕ c(x, y), y ⊕ c(x, y) ⊕ c(x, y)) : x ∈ F n 2 , y ∈ F n 2 } = {(q(x ′ , y ′ ) ⊕ x ′ ⊕ y ′ , q(x ′ , y ′ ) ⊕ x ′ , q(x ′ , y ′ ) ⊕ y ′ ) : x ′ ∈ F n 2 , y ′ ∈ F n 2 }
where the final equality follows from lemma 1. The result is now obvious. Some remarks:

1. Thus for each n ≥ 1 the mappings (x, y) → x ⊞ y and (x, y) → q(x, y) give an example of a pair of vectorial Boolean functions F, G : F 2n 2 -→ F n 2 which are CCZ-equivalent. 2. Written in coordinates , q is the vectorial Boolean function

(x, y) → (0, x 0 y 0 , x 0 y 0 ⊕ x 1 y 1 , . . . , x 0 y 0 ⊕ . . . ⊕ x n-2 y n-2 )
For j ≥ 1 the ANF of the coordinate function q j (x, y) is of degree 2 in the variables x 0 , . . . , x n-1 , y 0 , . . . , y n-1 . On the other hand it is easy to see that the ANF of the coordinate function (x, y) → (x ⊞ y) j is of degree j + 1 in these variables. For n ≥ 3 therefore ⊞ and q can not possibly be (extended) affine equivalent.

3. Of course, addition mod 2 n is e.g also CCZ-equivalent to the vectorial Boolean function (x, y) → (x 0 y 0 , x 1 y 1 , . . . , x n-2 y n-2 , 0) and others. Since such standard linear equivalences of q do not add anything substantially new to the picture, we do not consider them here. 4. The recursion for the carries is also the starting point of all other published investigations of the boolean properties of addition mod 2 n . New in the approach here is the use of the bijections α, β to exploit CCZ-equivalence. 5. The graph of addition mod 2 n is thus "only" the graph of a quadratic vectorial function. From this perspective addition mod 2 n is a very simple boolean operation. Here we use this fact only to revisit the linear and differential properties of addition mod 2 n , but it should be clear that it can potentially also be useful for algebraic attacks.

Differential properties

The differential properties of quadratic vectorial Boolean functions are easy to describe, since their difference functions are affine-linear. To take advantage of this fact here, we observe:

Theorem 2. Let a, b, d ∈ F n 2 and for x, y ∈ F n 2 let (x ′ , y ′ ) := α(x, y) = (x ⊕ q(x, y), y ⊕ q(x, y)). Then q(x ⊕ a, y ⊕ b) = q(x, y) ⊕ d ⇔ (x ′ ⊞ y ′ ) ⊕ ((x ′ ⊕ a ⊕ d) ⊞ (y ′ ⊕ b ⊕ d)) = a ⊕ b ⊕ d Equivalently q(x⊕b⊕d, y⊕a⊕d) = q(x, y)⊕a⊕b⊕d ⇔ (x ′ ⊞y ′ )⊕((x ′ ⊕ a) ⊞ (y ′ ⊕ b)) = d
But the left equation is the same as

R(x ⋆ (a ⊕ d)) ⊕ R(y ⋆ (b ⊕ d)) = R((a ⊕ d) ⋆ (b ⊕ d)) ⊕ (I ⊕ R)(a ⊕ b ⊕ d) ( * * ),
i.e. a (very simple) system of linear equations. Thus the set of solutions of a DEA is simply an affine linear subspace of (F n 2 ) 2 , "deformed" by α. This observation reduces the question of solvability resp. the computation of all solutions of a system of DEAs to linear algebra: just solve the equivalent linear system first, and then compute the image of the solution set under α. We remark that single equations of this type can easily be solved explicitly: This leads immediately to the solutions of ( * * ). . Since x 0 ⋆ y 0 = 0 for this special solution x ′ 0 = x 0 , y ′ 0 = y 0 . Combining the two preceding results we find:

Theorem 3. (Lipmaa-Moriai) Let (X, Y ) be uniformly distributed on F n 2 ×F n 2 . Then P ((X ⊞ Y ) ⊕ ((X ⊕ a) ⊞ (Y ⊕ b)) = d) = 1 {(I⊕R)(a⊕b⊕d) R((a⊕d)|(b⊕d))} 2 -|(R((a⊕d)|(b⊕d))|
This is theorem 1 from [5] (up to notation), where it forms the basis of an extensive discussion of the differential spectrum of addition mod 2 n . Finally we note that solving systems of DEAs is much easier than solving general linear equations. In fact, by theorem 2 a system of k DEAs is equivalent to a system of equations of the form

(a i ⋆ x) ⊕ (b i ⋆ y) = d i i = 1, . . . , k
(plus trivial equations for the least significant bits). The linear equations on the lhs of each such equation are described by a coefficient matrix A i B i where A i , B i are diagonal matrices. Therefore such a system of equations can be solved extremely efficiently.

Linear correlations of addition mod 2 n

In this section we revisit linear correlations of addition. We show that CCZequivalence leads to a simple explicit formula for the correlation coefficients and use this formula to extend the results of [START_REF] Wallén | Linear approximations of addition mod 2 n[END_REF]. Let u := (u 0 , . . . , u n-1 ), v := (v 0 , . . . , v n-1 ), w := (w 0 , . . . , w n-1 ) ∈ F n 2 (u is the "output mask", and v, w are the "input masks"), and let z = M t (u).

We are interested in the linear correlations coefficients of addition mod 2 n

φ 2 (u, v, w) := E(-1) u•(X⊞Y )⊕v•X⊕w•Y = 1 2 2n 1G ⊞ (u, v, w)
(where X, Y are independent and uniformly distributed on {0, 1} n ) .

By the above we need only compute the Walsh transform of q, as (by theorem 1) the relation Especially each solution a of ( * ) must fulfil : v ⊕ w L(a); i.e. R(v ⊕ w) a.

φ 2 (u, v, w) = φ q (u ⊕ v ⊕ w, u ⊕ v, u ⊕ w) ( * ) Example
Additionally we must have: if v i = w i = 0 and a i = 1 then it must be that a i+1 = 1. If a section 10 k in v|w corresponds to a section 0 k+1 in w ⋆ v, then the corresponding section in L(a) must (for each solution a of ( * )) be 1 k+1 . Let m(v, w) denote the the vector which is constructed by these modifications starting from R(v ⊕ w).

Lemma 2 .

 2 Let a, b, d ∈ F n 2 and consider the equation(a ⋆ x) ⊕ (b ⋆ y) = d ( * ) Then ( * ) has a solution iff d a|b. In this case (x 0 , y 0 ) := (a ⋆ d, (b ⊕ a ⋆ b) ⋆ d)is a solution. All other solutions can be obtained from (x 0 , y 0 ) by modifying y 0 arbitrarily at positions i were a i = 1, b i = 0, modifying x 0 arbitrarily at the positions where a i = 0, b i = 1, modifying x 0 , y 0 in the same way (i.e. leaving x i ⊕y i unchanged) where a i = b i = 1 and choosing x i , y i arbitrarily if a i = b i = 0. Thus there are 2 2n-|a|b| solutions, if solutions exist.

Corollary 1 .

 1 (x ′ ⊞ y ′ ) ⊕ ((x ′ ⊕ a) ⊞ (y ′ ⊕ b)) = d (or equivalently ( * * ) ) has solutions iff (I ⊕ R)(a ⊕ b ⊕ d) R(a ⊕ d)|R(b ⊕ d)In this case, with d := R((a⊕d) * (b⊕d))⊕(I ⊕R)(a⊕b⊕d), â := R(a⊕d), b := R(b ⊕ d) a special solution is given by (x 0 , y 0 ) := (L(â ⋆ d), L(( b ⊕ â ⋆ b) ⋆ d))

1 .

 1 Let n = 13 and let u = (1110 1101 0011 1) = (7351) 2 (little-endian!). Then L(u) = (1101 1010 0111 0) has 1 one-block of length 1, 2 one-blocks of length 2, and one one-block of length 3. Thus d(u) = 1 + 2 + 2 = 5. Further a L (u) = (1010 0101 0010 1) = (5285) 2 and b(u) = (1110 1111 0111 1) = (7927) 2 . Hence in row 7351 of the correlation matrix the element φ 2 (7351, 7927, 7351) = 2 -5 is maximal.Column maximaSimilarly a correlation of maximal modulus can be found when two masks, say v and w, are fixed. We have to determine s = u ⊕ v ⊕ w s.th. M t (s) has minimal Hamming weight under the side conditionss ⊕ w = u ⊕ v M t (s) and s ⊕ v = u ⊕ w M t (s) .With s = a ⊕ L(a) the task then is to determine a s.th. L(a) has minimal weight under the side conditions a ⊕ v L(a), a ⊕ w L(a) ( * ).

Theorem 7 .

 7 (column maxima) Let v, w ∈ F n 2 be given s.th. v n-1 = w n-1 = 1, let a(v, w) := a L (v ⋆w)|m(v, w) and let u(v, w) := (v ⊕ w) ⊕ (I ⊕ L)(a(v, w)). Then

holds. But φ q (u, vw) is easy to compute: φ q (u, vw) = E(-1) M t (u)•(X⋆Y )⊕v•X⊕w•Y = δ 0,vn-1 δ 0,wn-1 n-1 i=1 E(-1) ziXiYi+viXi+wiYi = 1 {v z} 1 {w z} (-1) v•w 2 -|z| (Here we have used the fact that for bits a, b, c and independent uniform random bits X, Y the relation E(-1) aXY ⊕bX⊕cY = 1 {b a} 1 {c a} (-1) bc 2 -a holds.) We thus have:

Some remarks

1. This theorem is equivalent to Theorem 1 of [START_REF] Wallén | Linear approximations of addition mod 2 n[END_REF], however, there the simple explicit description of z was not obtained. Instead z had to be computed recursively from the vectors u and v ⊕ w ⊕ e. It is this explicit description of z as z = M t (u ⊕ v ⊕ w) which gives additional insight into the Walsh spectrum of addition. 2. If the absolute value of φ 2 (u, v, w) is non-zero it e.g. only depends on the Hamming weight of the binary vector

By the above we have the following "pencil and paper" method to compute φ 2 (u, v, w):

) is non-zero, iff for all i with z i = 0 the equality u i = v i = w i holds.

In this case the absolute value of φ 2 (u, v, w) is 2 -|z| and the sign is -1

We collect some properties of the correlation matrix:

Corollary 2. (symmetry properties)

3. If e k M t (u) for a standard basis vector e k then φ 2 (u, u ⊕ e k , u) = 0. The corresponding vector z = M t (u ⊕ e k ) = M t (u) ⊕ k-1 i=0 e i , i.e. it is computed from the corresponding z = M t (u) for (u, u, u) by complementation below k.

In cryptanalysis one is mainly interested in correlations of high absolute value.

In the sequel we deal with the problem of determining "best" approximations when one or two of the masks are fixed.

A combinatorial problem

Consider the following problem: given u ∈ F n 2 , let

Problem: find a L-minimal vector for u, i.e. find a vector a = a(u) ∈ A L (u) s.th. the Hamming weight |L(a)| is minimal. It is clear that A L (u) = ∅, since clearly u ∈ A L (u). Thus there exist solutions.

We need the following assertion (the proof is deferred to appendix A):

The function a L (u) was introduced in [5] under the name of "all one parity".

Maximal correlations

We return to the problem of determining maximal correlations of addition mod 2 n . In order to have a convenient way to formulate the results we call the elements φ 2 (u, ., .) the "row" u of the correlation matrix, and the elements φ 2 (., v, w) the "column" (v, w) of the correlation matrix. (By the the symmetry properties (lemma 3) only these cases need to be considered.) We first treat the row case.

Summary

Addition mod 2 n is CCZ-equivalent to a quadratic vectorial Boolean function. This is theoretically interesting and it also leads to practical results: it makes the solution of differential equations of addition extremely easy (Section 4, improving on [START_REF] Paul | Solving systems of differntial equations of addition[END_REF]), and it leads to advanced results on the Walsh transform of addition mod 2 n (identifying for the first time "row"-resp. "column"-maxima and making the formula of [START_REF] Wallén | Linear approximations of addition mod 2 n[END_REF] explicit). The results are helpful for the analysis of cryptographic primitives which use addition mod 2 n . (E.g. since the correlation matrix F r of the M IX(r) operation in Threefish is F r (t 1 , t 2 ; u 1 , u 2 ) = φ 2 (t 1 ⊕ t 2 ; u 1 , u 2 ⊕ (t 2 ≫ r)) the results of section 5 can be applied almost directly in the LC of Threefish). The results show that (in the sense of CCZ-equivalence) addition mod 2 n is a very simple vectorial Boolean function.


Ayça C ¸eşmelioglu
email: cesmelioglu@sabanciuniv.edu

Wilfried Meidl
email: wmeidl@sabanciuniv.edu

A construction of bent functions from plateaued functions

Keywords: Bent functions, weakly regular bent, non-weakly regular bent, quadratic functions, plateaued functions

In this presentation a technique for constructing bent functions from plateaued functions is introduced. This generalizes earlier techniques for constructing bent from near-bent functions. Analysing the Fourier spectrum of quadratic functions we then can construct weakly regular as well as non-weakly regular bent functions both in even and odd dimension. This type of functions yield the first known infinite classes of non-weakly regular bent functions. Weakly regular bent functions with certain additional properties can be used to construct partial difference sets and strongly regular graphs. We show how to obtain appropriate bent functions using our construction.

Introduction

Let p be a prime, and let V n be any n-dimensional vector space over F p and f be a function from V n to F p . If p = 2 we call f a binary or Boolean function, if p is an odd prime we call f a p-ary function. The Fourier transform of f is the complex valued function f on V n given by f (b) = x∈Vn ǫ f (x)-b,x p where ǫ p = e 2πi/p and , denotes any inner product on V n . The function f is called a bent function if | f (b)| 2 = p n for all b ∈ V n .

The normalized Fourier coefficient at b ∈ V n of a function from V n to F p is defined by p -n/2 f (b). A binary bent function clearly must have normalized Fourier coefficients ±1, and for the p-ary case we always have (cf. [START_REF] Helleseth | Monomial and quadratic bent functions over the finite field of odd characteristic[END_REF])

p -n/2 f (b) = ±ǫ f * (b) p
: n even or n odd and p ≡ 1 mod 4 ±iǫ f * (b) p : n odd and p ≡ 3 mod 4 [START_REF] Carlet | Normal extensions of bent functions[END_REF] where f * is a function from V n to F p .

A p-ary bent function f is called regular if for all b ∈ V n

p -n/2 f (b) = ǫ f * (b) p .
As easily seen from ( 1), a p-ary regular bent function can only exist for even n and for odd n when p ≡ 1 mod 4.

A p-ary bent function f is called weakly regular if, for all b ∈ V n , we have

p -n/2 f (b) = ζ ǫ f * (b)
p for some complex number ζ with absolute value 1. By [START_REF] Carlet | Normal extensions of bent functions[END_REF], ζ can only be ±1 or ±i. Note that regular implies weakly regular.

A function

f from V n to F p is called plateaued if | f (b)| 2 =
A or 0 for all b ∈ V n . By Parseval's identity we obtain that A = p n+s for an integer s with 0 ≤ s ≤ n. We will call a plateaued function with | f (b)| 2 = p n+s or 0 an s-plateaued function. The case s = 0 corresponds to bent functions by definition. For 1-plateaued functions the term near-bent function is common (see [START_REF] Mcguire | A construction of weakly and non-weakly regular bent functions[END_REF][START_REF] Leander | Construction of bent functions from near-bent functions[END_REF]), binary 1-plateaued and 2-plateaued functions are referred to as semi-bent functions in [START_REF] Charpin | On bent and semi-bent quadratic Boolean functions[END_REF].

We present a technique for constructing bent functions from plateaued functions which generalizes earlier constructions of bent functions from near-bent functions. Employing quadratic plateaued functions, families of bent functions with interesting properties are obtained. Using plateaued instead of only quadratic near-bent functions, we can obtain bent functions of various algebraic degree. With our construction, we obtain the first known infinite classes of non-weakly regular bent functions in odd dimension. Using direct sums of bent functions we also can construct non-weakly regular bent functions in even dimension. Weakly regular bent functions with certain additional properties can be used to construct strongly regular graphs. With our construction, we can obtain various classes of bent functions in any characteristic that can be used to construct strongly regular graphs (of Latin square and of negative Latin square type). Until now, only a few such bent functions were known, though already yielding new strongly regular graphs, [START_REF] Tan | Strongly regular graphs associated with ternary bent functions[END_REF].

Quadratic functions

If we associate V n with the finite field F p n , we use the inner product x, y = Tr n (xy), where Tr n (z) denotes the absolute trace of z ∈ F p n . The Fourier transform of a function f from F p n to F p is then the complex valued function on F p n given by

f (b) = x∈F p n ǫ f (x)-Trn(bx) p . A function f from F p n to F p of the form f (x) = Tr n l i=0 a i x p i +1 (2)
is called quadratic, its algebraic degree is two, see [START_REF] Charpin | On bent and semi-bent quadratic Boolean functions[END_REF][START_REF] Helleseth | Monomial and quadratic bent functions over the finite field of odd characteristic[END_REF]. Every quadratic function from F p n to F p is s-plateaued, where s is the dimension of the kernel of the linear transformation on F p n defined by

L(x) = l i=0 a p l i x p l+i + a p l-i i x p l-i . (3)
Choosing and fixing a basis {α 1 , . . . , α n } of F p n over F p , we correspond x = n i=1 x i α i to the vector x = (x 1 , . . . , x n ). Then we can associate a quadratic function f (x) = Tr n ( l i=0 a i x p i +1 ) with a quadratic form

f (x) = x T Ax,
where x T denotes the transpose to the vector x, and the matrix A has entries in F p . Any quadratic form is equivalent to a diagonal quadratic form, i.e. D = C T AC for a nonsingular matrix C over F p and a diagonal matrix

D = diag(d 1 , . . . , d n ).
The following proposition is obtained by generalizing the related result in [START_REF] Helleseth | Monomial and quadratic bent functions over the finite field of odd characteristic[END_REF], which corresponds to the case that f (x) is nondegenerate, using [8, Theorem 6.27, Theorem 5.15] if ns odd and [START_REF] Lidl | Finite Fields[END_REF]Theorem 6.26] if ns is even.

Proposition 1. Let f be an s-plateaued quadratic function from F p n to F p and f (x) = x T Ax be the associated quadratic form. Then a corresponding diagonal matrix D has ns (not necessarily distinct) nonzero entries d 1 , . . . , d n-s , and the Fourier spectrum of f is given by 0, η(∆)p where J(x) is a function from the support supp( f

) := {b ∈ F p n | f (b) = 0} of f to F p , ∆ = n-s i=1 d i ,
and η denotes the quadratic character in F p .

3 Construction of bent from plateaued functions

Theorem 1. For each a = (a 1 , a 2 , • • • , a s ) ∈ F s p , let f a (x) be an s-plateaued function from F p n to F p . If supp( f a ) ∩ supp( f b ) = ∅ for a, b ∈ F s p , a = b, then the function F (x, y 1 , y 2 , • • • , y s ) from F p n × F s p to F p defined by F (x, y 1 , y 2 , • • • , y s ) = a∈F s p (-1) s s i=1 y i (y i -1) • • • (y i -(p -1)) (y 1 -a 1 ) • • • (y s -a s ) f a (x)
is bent.

Sketch of the proof

The Fourier transform

F of F at (α, a) ∈ F p n × F s p is F (α, a) = x∈F p n ,y1,••• ,ys∈Fp ǫ F (x,y1,••• ,ys)-Trn(αx)-a•y p = y1,••• ,ys∈Fp ǫ -a•y p f y (α).
As each α ∈ F p n belongs to the support of exactly one f y , y ∈ F s p , for this y we have

F (α, a) = |ǫ -a•y p f y (α)| = p n+s 2 .
✷

The following theorem shows how to construct a set of s-plateaued functions such that the supports of the Fourier transforms are pairwise disjoint.

Theorem 2. For each a = (a 1 , • • • , a s ) ∈ F s p
, let g a be a quadratic s-plateaued function from F p n to F p and L a be the corresponding linearized polynomial. For all a ∈ F s p , if L a has the same kernel in

F p n with basis {β 1 , • • • , β s } and γ a ∈ F p n is such that g a (β j ) + Tr n (γ a β j ) = g 0 (β j ) + a j , (4)
for all j = 1, • • • , s, then the s-plateaued function f a defined by f a (x) = g a (x) + Tr n (γ a x) satisfies supp( f a ) ∩ supp( f b ) = ∅ for b ∈ F s p , a = b. Proof We have to show that -α ∈ supp( f b ) implies -α ∈ supp( f a ) for a = b. Suppose -α ∈ supp( f b ), i.e. g b (β j ) + Tr n (γ b β j ) + Tr n (αβ j ) = g 0 (β j ) + b j + Tr n (αβ j ) = 0, for each j = 1, • • • , s.
Let a = b and suppose that a j = b j for some 1 ≤ j ≤ s. Then f a (β j )+Tr n (αβ j ) = g a (β j )+Tr n (γ a β j )+Tr n (αβ j ) = g 0 (β j )+a j +Tr n (αβ j ) = 0. ✷ Remark 1. By the linear independence of β 1 , . . . , β s , the existence of γ a satisfying equation ( 4) for all j = 1, . . . , s, is guaranteed. In fact, if {δ 1 , δ 2 , . . . , δ n } and {ρ 1 , ρ 2 , . . . , ρ n } are dual bases of F p n over F p , and

β j = b j1 δ 1 +b j2 δ 2 +• • •+b jn δ n , then the coefficients x i of γ a = x 1 ρ 1 + x 2 ρ 2 + • • • + x n ρ n satisfy Tr n (γ a β j ) = b j1 x 1 + b j2 x 2 + • • • + b jn x n .
A value for γ a is then obtained with a solution of the linear system Bx = c over F p for the (s

× n)-matrix B = (b jk ) and c = (c 1 , • • • , c s ) T with c j = g 0 (β j ) + a j -g a (β j ), j = 1, 2, . . . , s.
We can consequently construct bent functions starting with any quadratic function f . In a first step we determine the value of s for the function f . Then we can choose p s constants in F * p and the linearized polynomials have the same kernel in F p n for all of the form cf , c ∈ F * p , hence we can apply Theorem 2 and Theorem 1. For some simple quadratic functions we know the value s in advance:

I: The quadratic monomial f (x) = Tr n (ax p r +1 ) ∈ F p n [x] is s-plateaued for some a ∈ F *
p n if and only if n is even, s is an even divisor of n and ν(s) = ν(r)+1, where ν denotes the 2-adic valuation on integers. The appropriate elements a ∈ F * p n can be determined and for the remaining a, f (x) is bent.

II: Binomials. Let c ∈ F * p , then the function f (x) = Tr n cx p r +1 -cx p t +1 from F p n to F p is near-bent if and only if gcd(n, r + t) = gcd(n, r -t) = gcd(n, p) = 1.
The kernel of the corresponding linearized polynomial is F p . Moreover if n is odd, then ∆ defined as in Proposition 1 is independent of the choice of r, t satisfying the above condition. Hence the Fourier spectrum is independent of the choice of r, t.

For c ∈ F * p the function f = Tr n cx p r +1 + cx p t +1 from F p n to F p is near-bent if and only if gcd(n, 2(r + t)) = gcd(n, 2(rt)) = 2, rt is odd, and gcd(n, p) = 1. The kernel of the corresponding linearized polynomial consists of the solutions of x p + x.

4 Non-weakly regular bent functions, weakly regular bent functions and strongly regular graphs

All classical examples of bent functions are weakly regular. However, in general, weak regularity is not easy to prove. With the subsequent corollaries of Proposition 1 and our construction presented in Section 3 we can design weakly regular and non-weakly regular bent functions. This also yields the first infinite classes of non-weakly regular bent functions.

In order to construct non-weakly regular bent functions, we need to change the signs of the Fourier coefficients of the s-plateaued functions. Proposition 1 suggests that if ns is odd, we can change signs by multiplying the functions with nonsquare elements of F p . If ns is even, we only obtain weakly regular bent functions for any choice of the coefficients. The following two corollaries can be seen as results of Proposition 1 and Theorem 1, 2. For the Corollaries 1,2 we fix the following notation: For integers n, s -G = {g a | a ∈ F s p } is a set of p s quadratic s-plateaued functions from F p n to F p such that the corresponding linearized polynomials L a have all the same kernel in

F p n ; -C = {c a | a ∈ F s p } is a set of p s nonzero elements of F p ; -{γ a | a ∈ F s p } is a set of elements of F p n such that the set F = {f a | a ∈ F s p } of p s quadratic s-plateaued functions from F p n to F p defined by f a (x) = c a g a (x) + Tr n (γ a x) satisfies supp( f a ) ∩ supp( f b ) = ∅ for a, b ∈ F s p , a = b.
Corollary 1. Let F be the bent function in dimension n+s given as in Theorem 1 constructed with the set F. If ns is odd, then F is weakly regular for (p -1) p s /2 p s -1 choices for C, and non-weakly regular for the remaining (2 p s -1 -1)(p -1) p s /2 p s -1 choices for C.

Corollary 2. Let g a = g for all a ∈ F s p and let F be the bent function in dimension n + s given as in Theorem 1 constructed with the set F. If ns is even, then F is weakly regular. If ns is odd, then F is weakly regular if and only if all elements of C have the same quadratic character in F p . Remark 2. Versions of the above corollaries for the special case that s = 1 were used in our work [START_REF] Mcguire | A construction of weakly and non-weakly regular bent functions[END_REF] to present the first infinite classes of non-weakly regular bent functions. These bent functions are in odd dimension, their algebraic degree is p + 1. With s > 1 non-weakly regular bent functions of higher degree can be constructed.

We now present the first construction of non-weakly regular bent functions in even dimension. Let the vector space V m+n of dimension m + n over F p be the direct sum of the vector spaces V m and V n of dimension m and n, respectively, and let f 1 be a p-ary function on V m and f 2 be a p-ary function on V n . Then the direct sum f 1 ⊕ f 2 of f 1 and f 2 is defined as the p-ary function on

V m+n = V m ⊕ V n given by (f 1 ⊕ f 2 )(x 1 + x 2 ) = f 1 (x 1 ) + f 2 (x 2 ). As pointed out in [1], we have f 1 ⊕ f 2 = f 1 f 2 , thus f 1 ⊕ f 2 is bent if f 1 and f 2 are bent.
In particular if exactly one f 1 or f 2 is non-weakly regular, then f 1 ⊕ f 2 is non-weakly regular. The latter argument was recently used in [START_REF] Tan | A recursive approach to construct p-ary bent functions which are not weakly regular[END_REF] to give a recursive approach to construct non-weakly regular bent functions -once a nonweakly regular bent function is obtained. Taking for f 1 a non-weakly regular bent function in odd dimension (Corollaries 1,2) and for f 2 a weakly regular bent function in odd dimension (e.g. quadratic bent function, Corollaries 1,2), then f 1 ⊕ f 2 is non-weakly regular in even dimension.

Examples

Example 1. The monomials g 0 (x) = Tr 4 (x 4 ), g 1 (x) = Tr 4 (x 28 ) have the same corresponding linearized polynomial L(x) = x + x 3 2 with a kernel of dimension 2 in F 3 4 . A basis for this kernel is {β, β 3 } where β is a root of the polynomial

x 4 + x 2 + 2. Since we have g 0 (β) = g 0 (β 3 ) = g 1 (β) = g 1 (β 3 ) = 0 for each a = (a 1 , a 2 ) ∈ F 3 × F 3 , we choose γ a ∈ F 3 4 such that Tr 4 (γ a β) = a 1 , Tr 4 (γ a β 3 ) = a 2 .
For the nine required 2-plateaued functions with pairwise disjoint supports of their Fourier transforms we then can choose

f (0,0) (x) = Tr 4 (x 4 + x), f (0,1) (x) = Tr 4 (x 4 + (β 3 + 1)x), f (0,2) (x) = Tr 4 (x 4 + (2β 3 + 2)x), f (1,0) (x) = Tr 4 (x 4 + βx), f (1,1) (x) = Tr 4 (x 4 + (β 3 + β)x), f (1,2) (x) = Tr 4 (x 28 + (2β 3 + β + 1)x), f (2,0) (x) = Tr 4 (x 28 + (2β + 1)x), f (2,1) (x) = Tr 4 (x 28 + (β 3 + 2β)x), f (2,2) (x) = Tr 4 (x 28 + (2β 3 + 2β)x).
The ternary function

F (x, y, z) = a=(a1,a2)∈F3×F3 yz(y -1)(z -1)(y -2)(z -2) (y -a 1 )(z -a 2 ) f a (x)
is a weakly regular bent function on F 3 4 × F 3 × F 3 of algebraic degree 6.

Example 2. Let p = 3, n = 8. The quadratic binomials g 0 (x) = Tr 8 (x 10 +x 4 ) and g 1 (x) = Tr 8 (x 3 6 +1 +x 3 5 +1 ) on F 3 8 are near bent. The kernel of the corresponding linearized polynomial consists of the solutions of

x 3 + x. Let β ∈ F 3 2 be a root of the polynomial x 2 + 1 ∈ F 3 [x]
. Then, the function

f 1 (x, y) = 2y 2 Tr 8 (x 3 5 +1 + 2x 4 + x) + yTr 8 (x 3 5 +1 + 2x 4 + βx) + Tr 8 (x 10 + x 4 + x)
from F 3 8 × F 3 to F 3 is a weakly regular bent function of algebraic degree 4.

Example 3. With g 0 (x), g 1 (x) in Example 2 and using different coefficients, we obtain the function

f 2 (u, w) = 2w 2 Tr 8 (v 3 6 +1 + 2v 3 5 +1 + v) + wTr 8 (v 3 6 +1 + v 3 5 +1 + v 10 + v 4 + βv) + Tr 8 (v 10 + v 4 + v)
from F 3 8 × F 3 to F 3 which is a non-weakly regular bent function of algebraic degree 4 in odd dimension 9.

Example 4. The direct sum of f 1 , f 2 is the ternary function

H(x, y, v, w) = f 1 (x, y) + f 2 (v, w)
on (F 3 8 ×F 3 )×(F 3 8 ×F 3 ) which is a non-weakly regular bent function of algebraic degree 4 in even dimension 18.

Example 5. The direct sum of the weakly regular bent function F (x, y, z) in Example 1 and the non-weakly regular bent function f 2 (v, w) of Example 3 is the ternary function

F (x, y, z) + f 2 (v, w) = a=(a1,a2)∈F3×F3 yz(y -1)(z -1)(y -2)(z -2) (y -a 1 )(z -a 2 ) f a (x) + 2w 2 Tr 8 (v 3 6 +1 + 2v 3 5 +1 + v) + wTr 8 (v 3 6 +1 + v 3 5 +1 + v 10 + v 4 + βv) + Tr 8 (v 10 + v 4 + v) on (F 3 4 × F 3 × F 3 ) × (F 3 8 × F 3
) which is a non-weakly regular bent function of algebraic degree 6.

In [START_REF] Chee | Strongly regular graphs constructed from p-ary bent functions[END_REF][START_REF] Feng | Partial difference sets from p-ary weakly regular bent functions and quadratic forms[END_REF][START_REF] Tan | Strongly regular graphs associated with ternary bent functions[END_REF] it is shown that partial difference sets and strongly regular graphs can be obtained from some classes of p-ary bent functions: Let n be an even integer and f : F p n → F p be a bent function with the additional properties that (a) f is weakly regular (b) for a constant k with gcd(k -1, p -1) = 1 we have for all t ∈ F p f (tx) = t k f (x).

Then the sets D 0 , D R , D N defined by

D 0 = {x ∈ F p n | f (x) = 0}, D N = {x ∈ F p n | f (x) is a nonsquare of F p }, D R = {x ∈ F p n | f (x) is a nonzero square of F p }
are partial difference sets of F p n . Their Cayley graphs are strongly regular. Some of the classical bent functions (e.g. quadratic and Coulter-Matthews) satisfy condition (b). In fact, using Coulter-Matthews functions, some new strongly regular graphs have been discovered in [START_REF] Tan | Strongly regular graphs associated with ternary bent functions[END_REF]. But in general, condition (b) is not satisfied. With an appropriate choice of near bent functions, the construction of Theorem 1 yields bent functions satisfying (b): Theorem 3. Let g 0 , g 1 be distinct quadratic near-bent functions from F p n to F p such that the corresponding linearized polynomials L 0 , L 1 have the same (1dimensional) kernel with basis {β}, and suppose that g 0 (β) = g 1 (β) = 0. Let γ ∈ F p n such that Tr n (γβ) = 0. Then the function

F (x, y) = y p-1 (g 1 (x) -g 0 (x)) + yTr n (γx) + g 0 (x)
is a bent function of degree p+1 that satisfies F (tx, ty) = t 2 F (x, y) for all t ∈ F p .

Examples

In the following part, we construct examples of weakly regular bent functions in even dimension satisfying (b). Example 6. p = 3, n = 7: Let g 0 (x) = Tr 7 (x 10x 4 ), g 1 (x) = Tr 7 (x 82x 28 ). Using Theorem 3, we construct the bent function F (x, y) = y 2 Tr 7 (x 82 -2x 10 + x 4 ) + yTr 7 (x) + Tr 7 (x 10x 4 ) in dimension 8 and of algebraic degree 4 on F 3 7 × F 3 . The normalized Fourier spectrum of F (x, y) with multiplicities is (-1) 2133 , (-ǫ 3 ) 2214 , (-ǫ 2

3 ) 2214 where ǫ 3 is a complex primitive third root of unity.

Example 7. p = 3, n = 8: g 0 (x) = Tr 8 (x 3 6 +1 + x 3 5 +1 ), g 1 (x) = Tr 8 (x 10 + x 4 ). By using Theorem 3, we construct the ternary bent function F (x, y) = y 2 Tr 8 (x 3 6 +1 + x 3 5 +1 + 2x 10 + 2x 4 ) + yTr 8 (γx) + Tr 8 (x 10 + x 4 ) of degree 4 in odd dimension 9. The quadratic monomial f (x) = Tr 5 (x 10 ) on F 3 5 is weakly regular bent and if we form the direct sum of F (x, y) with f (x), the resulting ternary function on F 3 8 × F 3 × F 3 5 will be regular bent i.e. the normalized Fourier spectrum will be {1, ǫ 3 , ǫ 2 3 }. We remark that this direct sum preserves (b). We further remark that using 2g 0 (x), 2g 1 (x) instead of g 0 (x), g 1 (x), changes the sign in the Fourier spectrum. The resulting strongly regular graph will then be of negative latin square type, see [START_REF] Tan | Strongly regular graphs associated with ternary bent functions[END_REF]. Example 8. p = 5 and n = 7: g 0 (x) = Tr 7 (x 5 4 +1 -x 2 ), g 1 (x) = Tr 7 (x 5 3 +1 -x 5+1 ) be two functions from F 5 7 to F 5 . Then we construct the following bent function of degree 6 on F 5 7 × F 5 : F (x, y) = y 4 Tr 7 (x 5 4 +1x 5 3 +1 + x 5+1x 2 ) + yTr 7 (x) + Tr 7 (x 5 4 +1x 2 ). Example 9. p = 5, n = 4: g 0 (x) = Tr 4 (x 5 3 +1 + x 5 2 +1 ), g 1 (x) = Tr 4 (4x 5 3 +1 + 4x 5 2 +1 ). We construct the following bent function on F 5 4 × F 5 : F (x, y) = y 4 Tr 4 (3x 5 3 +1 + 3x 5 2 +1 ) + yTr 4 (βx) + Tr 4 (x 5 3 +1 + x 5 2 +1 ).

The quadratic monomial f (z) = Tr 5 (z 26 ) is a bent function on F 5 5 and by taking the direct sum, we obtain G(x, y, z) = F (x, y) + g(z)

= y 4 Tr 4 (3x 5 3 +1 + 3x 5 2 +1 ) + yTr 4 (βx) + Tr 4 (x 5 3 +1 + x 5 2 +1 ) + Tr 5 (z 26 ), which is a bent function of degree 6 defined on (F 5 4 × F 5 ) × F 5 5 .

::

  p ≡ 3 mod 4 and ns odd, p ≡ 3 mod 4 and ns even,


Robert Niebuhr

Pierre-Louis Cayrel
email: pierre-louis.cayrel@cased.de

Johannes Buchmann

Improving the efficiency of Generalized Birthday Attacks against certain structured cryptosystems

Keywords: Generalized Birthday Attack, quasi-cyclic, quasi-dyadic, codes, post quantum, cryptography

Code-based cryptographic schemes are promising candidates for post-quantum cryptography since they are fast, require only basic arithmetic, and because their security is well understood. Due to their main drawback of large public key sizes, there have been many proposals on how to reduce the key sizes. Many of these use highly structured matrices which can be stored more efficiently. In this paper, we show how a broad class of such structures can be exploited to increase the time and memory efficiency of a Generalized Birthday Attack (GBA), which is one of the best generic attacks against code-based cryptosystems. For example, this improves the best attack against QD-CFS (with n = 30924) and FSB512 by a factor of 180 and 1984, respectively. In general, for a parity-check matrix of size r × n, the improvement is a factor of r, which is typically in the order of 2 8 to 2 12 .

Introduction

In 1994, P. Shor [START_REF] Shor | Algorithms for quantum computation: discrete logarithms and factoring[END_REF] has shown that quantum computers can break most or all "classical" cryptosystems, e.g. those based on RSA or elliptic curves. Therefore, it is crucial to develop cryptosystems that are resistant to quantum computer attacks. Code-based cryptography is a very promising candidate for post-quantum cryptography since the cryptographic schemes use only basic arithmetic operations and do not require special hardware, specifically no cryptographic coprocessor. The first application was the McEliece encryption scheme [START_REF] Mceliece | A public-key cryptosystem based on algebraic coding theory[END_REF] which was published in 1978. It is as old as RSA and has resisted cryptanalysis to date (except for a parameter adjustment). Other examples of code-based cryptosystems are the (provably secure) FSB hash function, and QD-CFS signature, which achieves a signature size of only 180 bit. One of the most important generic attacks against code-based cryptosystems is the Generalized Birthday attack (GBA) and its modifications. It has been proposed by Wagner in 2002 [START_REF] Wagner | A generalized birthday problem[END_REF] and was generalized by Minder and Sinclair in 2009 [START_REF] Minder | The extended k-tree algorithm[END_REF]. Many code-based cryptosystems have the drawback of having large public key sizes. Therefore, there have been many proposals attempting to reduce these key sizes; most recently, quasi-cyclic (QC) alternant [START_REF] Berger | Reducing key length of the McEliece cryptosystem[END_REF] and quasi-dyadic (QD) Goppa [START_REF] Misoczki | Compact McEliece keys from Goppa codes[END_REF] codes, and the QD-CFS signature scheme [START_REF] Barreto | Quasi-dyadic CFS signatures[END_REF]. Many of these proposals have in common that they use codes that can be represented by highly structured matrices, which allows to store them more efficiently.

Related work

The birthday paradox refers to the fact that collisions between two (usually random) lists can be found in O(2 n/2 ), much faster than O(2 n ) for checking every possible combination. Wagner's generalized this algorithm in 2002 by allowing more than two lists. The GBA takes lists L 1 , . . . , L t and an element s as input and attempts to find exactly one element x i ∈ L i per list such that i x i = s. By starting with t instead of 2 lists, the generalized algorithm achieves a complexity of O(2 2 √ n ). However, it requires a larger number of input elements and therefore more memory than the classic Birthday algorithm. Minder and Sinclair's extended k-tree algorithm can be seen as a further generalization of Wagner's work. It allows to balance the time and memory efficiency of the algorithm. This enables an attacker to optimize the attack performance in the presence of memory constraints. We will demonstrate our improvement based on Minder and Sinclair's version of the GBA. In 2009, Bernstein et al. published a successful attack [START_REF] Bernstein | INDOCRYPT[END_REF] against FSB 48 , a toy version of FSB, that required just under 8 days. This attack used the two techniques mentioned in Remark 3, but did not exploit the quasi-cyclic structure of the matrix.

Our contributions

In this paper, we show how the structure of the parity check matrix can be used to speed up GBA-like algorithms and reduce the memory requirements. Our efficiency improvement covers a broad range of structures, that includes, but is not limited to, the proposals above. Examples are given in Table 1. Due to the structure of the corresponding parity check matrix, the original GBA calculates and stores the same elements many times. We demonstrate how to exploit the structure to get the above improvements.

Organization of the paper

In Section 1 we begin with a review on code-based cryptography. The next section outlines a basic GBA algorithm and shows how it can be used to attack code-based cryptosystems. We present our efficiency improvement in Section 3. We conclude in Section 4.

1 Preliminaries

Coding theory

In this paper, we consider linear error-correcting codes over a finite field F q , where q is a prime power. A linear code C is a k-dimensional subspace of an n-dimensional vector space over F q and is called an [n, k] code. The elements of a code are called codewords. The (Hamming) weight of a vector is the number of its non-zero entries, and the (Hamming) distance of two vectors is the weight of their difference. Another common notation is the co-dimension r where r = n-k.

Definition 1 (Generator and Parity Check Matrix). Let C be a linear code over F q . A generator matrix G of C is a matrix whose rows form a basis of C: C = {xG : x ∈ F k q }. Two generator matrices generate equivalent codes if one is obtained from the other by a linear transformation. Therefore, we can write any generator matrix G in systematic form G = [I k |R], with R ∈ F k×r q and I k is the identity matrix of size k, which allows a more compact representation. A parity check matrix H of C is defined by

C = {x ∈ F n q : Hx T = 0}
and generates the dual space of C.

If C is generated by G = [I k |R], then a parity check matrix for C is H = [-R T |I r ]
(sometimes H is transformed so that the identity submatrix is on the left hand side). For a given parity check matrix H and any vector e, we call s the syndrome of e with s T := He T .

For a matrix H, we will denote its rows by H i and its columns by H •,i .

The syndrome decoding (SD) problem

Problem 1. Given a matrix H and a vector s, both over F q , and a non-negative integer t; find a vector e ∈ F n q of weight t such that He T = s T .

This problem was proved to be NP-complete in 1978 [START_REF] Berlekamp | On the inherent intractability of certain coding problems[END_REF], but only for binary codes. In 1994, A. Barg proved that this result holds for codes over all finite fields ([3, in russian] and [START_REF] Barg | Complexity issues in coding theory[END_REF]Theorem 4.1].

Many cryptosystems are based on the the hardness of the SD problem. Among the best-known are the McEliece [START_REF] Mceliece | A public-key cryptosystem based on algebraic coding theory[END_REF] public key cryptosystem (PKC) and its dual, the Niederreiter [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF] PKC, as well as the Courtois-Finiasz-Sendrier (CFS) [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF] signature scheme.

There exist two generic attacks to solve the SD problem: Information Set Decoding (ISD) and Generalized Birthday Attacks (GBA). In this paper, we will present an efficiency improvement for the GBA. Our improved algorithm is not restricted to binary codes, it can be used for codes over F q , where q is a prime power.

Generalized Birthday algorithms

Generalized Birthday algorithms are used for some of the most efficient attacks against code-based cryptosystems. They have been proposed by Wagner in 2002 [START_REF] Wagner | A generalized birthday problem[END_REF], and they are named after the famous birthday paradox which allows to quickly find common entries in lists. In 2009, Minder and Sinclair proposed a further generalization of this algorithm [START_REF] Minder | The extended k-tree algorithm[END_REF] which allows to trade-off time and space efficiency. In this section we will review the basic principles of Generalized Birthday Attacks (GBA). GBA attempts to solve the SD problem stated above, i.e. for given parity check matrix H, syndrome s and integer t, to find a vector e of weight t such that He T = s T . In other words, find a set of columns of H whose weighted sum equals the given syndrome. For easier demonstration of the algorithm, let t = 2 a for some integer a. If this is not the case, the algorithm still works with a slight loss of efficiency. Let H be the parity check matrix of a [n, k] code, i.e. H has size r × n.

First, the algorithms sets up t lists L 1 1 , . . . , L 1 t , each of which consists of every column of H (in the q-ary case, also all non-zero multiples of these columns). Each list therefore consists of (q -1)n vectors in F r q . In the next step, pairs of lists are merged into new ones: For i ∈ [1, t/2], the lists L 1 2i-1 and L 1 2i are merged to form a new list L 2 i , with

L 2 i = L 1 2i-1 ⊕ L 1 2i
. This means that the new list is created by considering all pairs of one element from L 1 2i-1 and one from L 1 2i , and adding their sum to L 2 i . If an entry occurs more than once in a new list, it is removed to minimize the size of the lists. The maximum size of L 2 i is hence ((q -1)n) 2 . Following this, the lists L 2 i are merged to form L 3 i , and this merging step is repeated until exactly one list remains. This list contains the solution to the problem stated above. Often, a slight modification is introduced: The vector s is subtracted from each entry in the last list L 1 t , and the algorithm attempts to find a combination of entries that sum up to zero. In fact, the final list contains all possible solutions. The number of solutions can be quite large for certain applications, e.g. for attacks on signature schemes. This fact can be used to

L 1 1 L 1 2 L 1 3 L 1 4 ✲ ✛ ❄ ✲ ✛ ❄ L L L 2 1 L 2 2 ✲ ✛ ❄ L L 3 1 Fig. 1. Illustration of the GBA for a = 2.
further improve the attack, as shown by Wagner (and in a more general way, by Minder and Sinclair):

After each merge step, the lists are being reduced in size. This is done by forcing a certain, increasing number of bits to zero. Each forced bit reduces the expected list size by a factor of q, and the number of bits that are forced to zero in each step can be optimized with respect to the parameters [n, r] and t. The reduction of the list size is an improvement in space -less data needs to be storedwell as in time, since there are less elements that need to be manipulated. The time complexity of the GBA is in O(2 a+u ), where 2 u is the maximum expected list length and t = 2 a . See [START_REF] Minder | The extended k-tree algorithm[END_REF] for a detailed proof. This fact is the reason why GBA are usually most efficient when there are a large number of solutions. For example, an unpublished attack by D. Bleichenbacher against the CFS signature scheme [START_REF] Courtois | How to achieve a McEliece-based digital signature scheme[END_REF] was very efficient and required an increase in the CFS parameters to remain secure (the attack is described in [START_REF] Finiasz | Security bounds for the design of code-based cryptosystems[END_REF]).

Efficiency improvement

Since the size of the public key is one of the drawbacks of many code-based cryptosystems, there have been many proposals on how to reduce the key size, most recently quasi-cyclic (QC) codes [START_REF] Berger | Reducing key length of the McEliece cryptosystem[END_REF], quasi-dyadic (QD) codes [START_REF] Misoczki | Compact McEliece keys from Goppa codes[END_REF], QD-CFS signatures [START_REF] Barreto | Quasi-dyadic CFS signatures[END_REF], and the Fast Syndrome-Based (FSB) hash function [START_REF] Augot | A family of fast syndrome based cryptographic hash functions[END_REF]. In many cases, the key size reduction is achieved by restricting the cryptosystem to a class of highly structured codes which can be stored efficiently. In this chapter we will show how this structure can be exploited to improve Generalized Birthday Attacks.

Preliminaries

Our analysis is applicable in all cases where the underlying code has a parity check matrix of a certain structure:

The structure of the parity check matrix H is such that each row is a permutation of the first row. This is true, for example, for the cryptosystems based on QC and QD codes in [START_REF] Berger | Reducing key length of the McEliece cryptosystem[END_REF][START_REF] Misoczki | Compact McEliece keys from Goppa codes[END_REF][START_REF] Barreto | Quasi-dyadic CFS signatures[END_REF]. This means that we have permutations Θ i , i ∈ [2, r], such that the i-th row H i of H can be computed by

H i = Θ i (H i-1 ) for i ∈ [2, r].
We abuse notation and write, for integers a and b, Θ i (a) = b, to say that Θ i permutates the a-th entry to position b.

Definition 2. To efficiently address the list entries we note that for every entry x in the lists there are unique c 1 < c 2 < . . . < c k and h 1 , h 2 , . . . , h k , such that x was created by the weighted sum of columns of H:

x = k i=0 c i H •,h k .
We define index(x) := (c 1 , . . . , c k ; h 1 , . . . , h k ) and write

Θ i ((c 1 , . . . , c k ; h 1 , . . . , h k )) = (c 1 , . . . , c k ; Θ i (h 1 ), . . . , Θ i (h k )). ( 1
)
Since an index uniquely defines an element, we can associate the two and write for short y := index(x). For any vector x, let us denote its i-th entry by x[i]. Then

x[i] = Θ -1 i (index(x))[i -1]. (2)

Improved algorithm

We will describe our improved algorithm as a modification of the one by Minder and Sinclair [START_REF] Minder | The extended k-tree algorithm[END_REF]. We start with t = 2 a lists L 1 i . In our case, each lists contains n entries, the columns of H. However, due to the structure of H, we only need to store the first bit of each column. We let l i denote the number of bits that is forced to zero in the i-th merging step. For the moment we assume s = 0, i.e. we want to find t columns of H whose weighted sum is the zero vector. We will later relax this assumption. In the first merging step, we calculate the first bit of the entries in L 2 i by adding pairs of entries of L 1 2i-1 and L 1 2i . If l 1 = 0 we continue with the second merging step; again, only calculating the first bit of L 3 i . If l 1 > 0 we need to calculate the next l 1 -1 bits of each list entry to decide which ones to eliminate: We start by eliminating all vectors whose first bit is non-zero. If l 1 > 1 we continue with the second row. To calculate the second bit of each remaining vector, we apply equation [START_REF] Barg | Complexity issues in coding theory[END_REF]. If the list entry Θ -1 i (index(x)) cannot be found, we know that we have already eliminated it, i.e. Θ -1 i (index(x)) [START_REF] Augot | A family of fast syndrome based cryptographic hash functions[END_REF] = 0. Since we force the second row to zero as well, we eliminate x. After each row that has been calculated, we do not have to store the previous row anymore, since it is completely forced to zero. Hence, in each merging step j, we only have to store one row of the current lists L j i , plus one row of the lists currently being computed. After completing the computation of the first l 1 rows, we continue with the next merging step, this time calculating the l 1 -th bit of the new vectors. The following merge and elimination steps work as described above, where the j-th step forces bits [ j-1 i l i + 1, j i l i ] to zero and continues of the next step in row j i l i . The pseudo code of our algorithm is shown in Algorithm 2. The operand ⊕ i refers to the operation of creating the new list from sums of all pairs of the two parent lists, only computing and storing the i-th bit, as shown in Algorithm 1 (here, || refers to the concatenation operation):

Algorithm 1 Pseudo code for C := A ⊕ f B over F q 1: for all a ∈ A, b ∈ B do 2: C ← C||(a[f ] + b[f ] mod q) 3: end for
Remark 1. The GBA algorithm described above assumes s = 0. If s = 0, we can modify it similarly as Wagner proposed in [START_REF] Wagner | A generalized birthday problem[END_REF]: The rightmost list L 1 t does not get columns (H •,i ) of H, but (H •,i -s). This allows us to search for list elements that sum to zero, and the corresponding columns of H will sum to s. For the merging step of each rightmost list, we have to modify equation ( 2), since different rows use different bits of s as an offset: For given s :

x[i] = Θ -1 i (index(x))[i -1] + s[i -1] -s[i]. (3)
Remark 2. In practice, this modification can be implemented efficiently by using look-up tables for the Θ i , and by using a suitable data structure for the lists L j i .

Analysis of time and memory efficiency

Our modification to the GBA, using the structure of H, reduces the number of computations and memory access, as well as the total memory required. Table 2 shows the effect of our improvement. The number of computations and memory access refers to a single merge step of two lists. We will use the resulting list size ls as the complexity of the operation (as described in [START_REF] Minder | The extended k-tree algorithm[END_REF], for example). Let r be the length of the list entries in bits, and q the field size. The last table item shows the total memory required to store the lists. Let ls(x) denote the size of list x.

The second term of the required memory for the improved GBA refers the memory that is needed to temporarily store the new row of a list while it being computed, until the previous row can be deleted from memory.

Algorithm 2 Pseudo code of improved GBA algorithm

Input: A r ×n parity check matrix H, integer t = 2 a , integers l1, . . . , la with P i li ≤ r, vector s, a prime power q. Output: Index(es) index(x) such that the corresponding weighted sum equals s, or "No solution found". Setup: Add the first entry of all n columns of H to each list L 1 1 , . . . , L 1 t . Subtract s from all elements of L 1 t . Let f1 = f2 = 0. 1: for step ← 1 to a do 2:

f1 ← f2 3:

f2 ← f2 + lstep 4:

for j ← 1 to 2 a-step do 5:

L step+1 j = L step 2j-1 ⊕ f 1 L step 2j 6:
for row ← f1 + 1 to f2 do 7:

⊲ Compute row-th bit of all vectors x in L step+1 j using equations (3) 8:

(for j = 2 a-step and s = 0) and ( 2) (for all other lists) 9:

⊲ If not possible, delete current vector x 10:

⊲

i,j ls(L j i ) • r • log 2 (q) P i,j ls(L j i ) • log 2 (q) + maxi,j |ls(L j i )| • log 2 (q)
Proposition 1. Our modified GBA algorithm decreases the number of computations and memory access by a factor of r; the total memory required is reduced by a factor close to r, since the maximum list size is small compared to the sum of all list sizes.

In this paper we have shown how the time and memory efficiency of Generalized Birthday Attacks can be improved by a factor of r when applied to a structured matrix of size r × n. Our improvement can be applied to a wide range of possible structures including quasi-cyclic and quasi-dyadic matrices. Even if only part of the matrix is structured, as for the truncated quasi-cyclic matrices in the FSB hash function, we can apply the improvement, but the effect is smaller. The efficiency improvement is quite large, often in the range of 2 9 to 2 12 . While this does not completely break the attacked cryptosystem, it has to be taken into account when proposing secure parameters.

As further work we propose to analyze if and how other attacks, for example information set decoding, can exploit such structures. Furthermore, it would be interesting to transfer these results to other areas of cryptography, for example lattices-based schemes. Also, it would be interesting to analyze if the structure of the matrix can be exploited in case of a "Grover-improved GBA". In 1996, Bennett et al. [START_REF] Bennett | Strengths and weaknesses of quantum computing[END_REF] showed that a brute-force search on a quantum computer cannot be faster than O(2 n/2 ) operations compared to O(2 n ) in the classical case. This can be offset by a twicefold increase in the key size on large enough quantum computer exist. If structures as analyzed in our paper can also be exploited by a Grover-GBA, it would require an additional key size increase.

Table 1 .

 1 Examples showing the improvement of time and space complexity (written in log 2 ) for various cryptosystems.

	GBA	Improved GBA

Table 2 .

 2 Effect of the efficiency improvement.

		After each row has been computed, delete the previous row
	11:	end for
	12:	end for
	13: end for
	14: if |L a 1 | = 0 then
	15:	Return "No solution found"
	16: end if
	17: return index(L a 1 )
			GBA	Improved GBA
		Computations	ls • r	ls
		Memory access r/w	ls • r	ls
		Memory for a list	P


I Leonard

A Alfalou
email: ayman.al-falou@isen.fr

M Alam

Nonlinear Fringe-adjusted JTC Based Face Tracking Using an Adapted Decision Criterion

Keywords: correlation, Nonlinear Fringe-adjusted JTC, Face recognition

In this paper, we propose a new technique for rotation invariant recognition and tracking of the face of a target person in a given scene. We propose an optimized method for face tracking based on the Fringe-adjusted JTC architecture. To validate our approach, we used the PHPID data base containing faces with various in-plane rotations. To enhance the robustness of the proposed method, we used a three-step optimization technique: (1) utilized the fringe-adjusted filter (H FAF ) in the Fourier plane, (2) added nonlinearity in the Fourier plane after applying the H FAF filter, and (3) used a new decision criterion in the correlation plane by considering the correlation peak energy and five largest peaks outside the highest correlation peak. Several tests were made to reduce the number of reference images needed for fast tracking while ensuring robust discrimination and efficient of the desired target.

Introduction

Correlation is a robust and discriminative pattern recognition technique widely studied in the literature [START_REF] Alfalou | Understanding Correlation Techniques for Face Recognition: From Basics to Applications[END_REF]. Its principle consists in measuring the Degree of similarity between a target image (image to be recognized) and a reference image (belonging to a database). Two families of architectures are used by most researchers to implement the correlation technique: [START_REF] Alfalou | Understanding Correlation Techniques for Face Recognition: From Basics to Applications[END_REF] the VanderLugt Correlator (VLC) [START_REF] Vanderlugt | Signal detection by complex spatial filtering[END_REF] and [START_REF] Vanderlugt | Signal detection by complex spatial filtering[END_REF] the Joint Transform Correlator [START_REF] Weaver | A Technique for Optically Convolving Two Functions[END_REF].

In this paper, we consider only the second "JTC" correlation architecture for our proposed Face tracking system. This system must be robust to changes in in-plane rotation of the face and be discriminative. Our objective is to track a subject in a given scene. Before discussing our system, we recall the basic principle of JTC architecture. To enhance the performances of the proposed tracking system (robustness and discrimination) we use an optimized version of this architecture, namely the Fringe-adjusted JTC [START_REF] Alam | Fringe-adjusted joint transform correlation[END_REF]. In addition, nonlinearity is introduced in the Fourier plane of the JTC correlator. Special attention is given to establishing an optimized correlation decision criterion: an adapted version of the PCE (Peak-to-Correlation Energy) is proposed and validated.

Analytical Modeling

JTC correlation architecture is described in detail in the literature, but we briefly recall the principle of JTC architecture in this paper. For more information, we invite the reader to consult the many works proposed and validated in this area by several researchers and groups working in this field, such as [1.3-4].

The principle of the Joint transform correlator consists in displaying in the input plane of the correlator both the target image "i" (image to be recognized) and the reference image "r". This plane can be represented mathematically by function "f" described in Eq. (1). To simplify its mathematical representation, we consider only a shift distance (equal to "x 0 ") along the x axis between the target image and the reference image.

f(x, y) = i(x + x 0 , y) + r(x -x 0 , y) (1)
After an first Fourier transformation of the input plane, we obtain its joint spectrum after which a Fourier transformation of the latter gives us the correlation plane (output plane). This plane contains two important items of information: (1) a central autocorrelation peak, and (2) two intercorrelation peaks (the correlation between image "i" and image reference "r"). These two intercorrelation peaks are located on either side of the central peak at a distance proportional to "x 0 ". To optimize this basic architecture Alam et al [START_REF] Alam | Fringe-adjusted joint transform correlation[END_REF] proposed to introduce a fringe-adjusted filter H FAF, Eq. ( 2), in the Fourier plane of the correlator, such that

( ) ( ) ( ) ( ) 2 , , , , ν µ ν µ ν µ ν µ R A B H FAF + = (2)
Where "R" denotes the Fourier transform of the reference considered, "B" is a constant or a function for obtaining a gain greater than unity and "A" is a function for reducing the noise effect. Before discussing the results obtained with this FA_JTC architecture, we present the application considered in this paper. Our application consists in recognizing and tracking a face that changes according to different rotation angles Fig. [START_REF] Alfalou | Understanding Correlation Techniques for Face Recognition: From Basics to Applications[END_REF]. The system proposed in this paper should allow robust tracking and discrimination for a face turning in different in-plane rotation angles between -90 ° and 90 °. Figure [START_REF] Vanderlugt | Signal detection by complex spatial filtering[END_REF] presents the first results obtained with FA_JTC using a single image reference to construct the filter H FAF (the face of the subject presented in Fig. (1) without rotation). The Background is defined as information outside a square around the face in the reference image considered. Then we display in the target image part (half the input plane) the target faces from the database presented in Fig. [START_REF] Alfalou | Understanding Correlation Techniques for Face Recognition: From Basics to Applications[END_REF], one after the other in directions -90 °, ..., 0 ° ... +90°. It should be recalled that the input plane of a JTC is divided into two parts, one reserved for displaying the target image and the other for displaying the references. The aim is to track the face desired from one target image to another. We initialize the system with a known reference image, i.e. the subject's face (number 1) to be tracked; the position of his face is known. By comparing this reference face with the target image, we obtain two items of information: the presence or not of the subject number (1) in the target image and the position of the subject's face in the target image. Then, only information around the position of the face is selected in this target image. To do this, we multiply the target image with a filter equal to "1" around the position of the face found and "0" elsewhere. Afterwards, we introduce the processed image in the part reserved for references in the FA_JTC input plane. Then a new target image is diplayed, etc..

Fig. 2. Depicts results obtained with a classical FJTC using only one reference image position without any rotation in the H FAF Filter to define the background noise. We used the PCE criterion

With the various tests performed by using this algorithm, we have identified a tolerance rotation angle equal to 15° between the target image and reference image in which the correlation remains robust. Beyond this value between the reference and target images, the correlation becomes less robust and may lose track of the subject's face. With a tolerance angle equal to 15°, the tracking problem of a person with in-plane rotation (between -90 and +90°), consists in correlating "13" couples of images: (-90, -75) (-75 , 60), ..., (-15, -0), (0, +15) ... (+60, +75) (+75, +90). The tracking results of subject number (1) are shown in Figure (2) (blue curve). The PCE criterion (Peak-To-Correlation Energy) was used for decision-making in the correlation plane [START_REF] Horner | Metrics for assessing pattern-recognition performance[END_REF]. Figure ( 2) also shows the results when subject number (2) (undesirable subject) is presented in the input plane (False Alarm: red curve). Both curves show that the proposed FA_JTC system gives good results. However, the values of the two curves are too close for a discriminative and robust system.

To optimize the performance of our system, we propose to adapt the function used to manufacture the fringe-adjusted filter (H FAF ) [START_REF] Alam | Dynamic target tracking with fringe-adjusted joint transform correlation and template matching[END_REF]. The background noise is calculated for each reference. The results with this first adaptation are shown in Figure (3) which clearly shows that we increase the discrimination of our system, i.e. the difference between the two curves are greater. To further increase the performance of the proposed system, we propose to adapt the decision criterion. Moreover, we propose adding nonlinearity in the Fourier plane of the correlator. These optimizations will be discussed in the next paragraph.

Test Result

To increase the performance of our system we carried out two other optimizations: 1) We begin this section by proposing an adaptation of the PCE decision criterion used. To do this, we propose to take into account the correlation peak as well as the five highest peaks outside of the area correlation peak. Mathematically, this criterion can be defined by: 1), it can easily be seen that we have succeeded in increasing the discrimination of our system. Indeed the difference between the two curves (red and blue) is larger.

Conclusion

In this paper we proposed and validated a first version of a robust and discriminative tracking system based on FA_JTC architecture. By choosing a tolerance in-plane rotation angle of 15° (rotation between the target image and the reference image), we considerably reduced the number of correlations necessary and therefore increased the speed of the system. Moreover, the adaptation of the decision criterion to be used in the output plane, allowed taking into account and minimizing the effect of the false correlation peaks in the correlation plane. This reduced the false alarms. Finally the addition of nonlinearity in the Fourier plane makes it possible to adapt or find a compromise between the robustness and discrimination of our tracking system by changing the value of K.

Fig. 1 .

 1 Fig. 1. Example of a face (in-plane rotation [-90 ° to +90 °]). Subject number (1), Base PHPID [6].

Fig. 3 .

 3 Fig. 3. Results obtained with FJTC ; we adapt the H FAF filter for each reference image

Figure ( 4 )

 4 Figure[START_REF] Alam | Fringe-adjusted joint transform correlation[END_REF] shows the different simulation results obtained with our tracking system based on an optimized FA_JTC correlator. By comparing the two curves presented in Figure[START_REF] Alam | Fringe-adjusted joint transform correlation[END_REF] with those presented in Figure[START_REF] Alfalou | Understanding Correlation Techniques for Face Recognition: From Basics to Applications[END_REF], it can easily be seen that we have succeeded in increasing the discrimination of our system. Indeed the difference between the two curves (red and blue) is larger.

Fig. 4 .

 4 Fig. 4. Results obtained with a non-linearity in the Fourier plane of the FA-JTC and the new criterion