Xuyun Nie
email: xynie@uestc.edu.cn

Albrecht Petzoldt

Johannes Buchmann

Cryptanalysis of 2-layer Nonlinear Piece In Hand Method

Keywords: Multivariate Cryptography, Quadratic Polynomial, Algebraic Cryptanalysis, Linearization Equation, Piece in Hand

Piece in Hand method is a security enhancement method for Multivariate Public Key Cryptosystems (MPKCs). Since 2004, many types of this method have been proposed. In this paper, we consider the 2-layer nonlinear Piece in Hand method as proposed by Tsuji et al. in 2009. The key point of this method is to introduce an invertible quadratic polynomial map on the plaintext variables to construct perturbation of the original MPKC. Through our analysis, we find that the security of the enhanced scheme is mainly relying on the quadratic polynomials of this auxiliary map. The two examples proposed by Tsuji et al. for this map can not resist the Linearization Equation attack. Given a valid ciphertext, we can easily get a public key which is equivalent to the original MPKC. If there is an algorithm that can recover the plaintext corresponding to a valid ciphertext of the original MPKC, we can construct an algorithm that can recover the plaintext corresponding to a valid ciphertext of the enhanced MPKC.

Introduction

Multivariate Public Key Cryptosystems (MPKCs) are promising candidates to resist the quantum computer attack [START_REF]Post-Quantum Cryptography[END_REF]. The security of these schemes is based on the difficulty of solving systems of multivariate quadratic (MQ) equations over a finite field, which is an NP-hard problem in general.

Since 1988, many MPKCs have been proposed, such as MI [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signature verification and message encryption[END_REF], HFE [START_REF] Patarin | Hidden field equations (HFE) and isomorphism of polynomials (IP): Two new families of asymmetric algorithms[END_REF], MFE [START_REF] Wang | A Medium-Field Multivariate Public key Encryption Scheme[END_REF], TTM [START_REF] Moh | A fast public key system with signature and master key functions[END_REF], Rainbow [START_REF] Ding | Rainbow, a new multivariate public key signature scheme[END_REF], MQQ [START_REF] Gligoroski | Multivariate Quadratic Trapdoor Functions Based on Multivariate Quadratic Quasigroups[END_REF]etc. However, many of these schemes have shown to be insecure [START_REF] Patarin | Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt[END_REF][START_REF] Faugère | Algebraic Cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF][START_REF] Ding | High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems[END_REF][START_REF] Nie | Breaking A New Instance of TTM Cryptosystem[END_REF][START_REF] Billet | Cryptanalysis of Rainbow. Security and Cryptography for Networks -SCN[END_REF][START_REF] Mohamed | Algebraic Attack on the MQQ Public Key Cryptosystem[END_REF]. In order to enhance the security of MPKCs, many enhancement methods were proposed. There are plus/minus [START_REF] Patarin | 𝐶 * -+ and HM: variations around two schemes of[END_REF][START_REF] Patarin | Flash, a fast multivariate signature algorithm[END_REF], internal perturbation [START_REF] Ding | A new variant of the Matsumoto-Imai cryptosystem through perturbation[END_REF][START_REF] Ding | Cryptanalysis of HFEV and the internal perturbation of HFE[END_REF], Extended Multivariate public key Cryptosystems (EMC) [START_REF] Wang | Extended multivariate public key cryptosystems with secure encryption function[END_REF] etc. All of these methods are subjected to different levels of attacks [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF][START_REF] Dubois | Practical Cryptanalysis of SFLASH[END_REF][START_REF] Fouque | Differential Cryptanalysis for Multivariate Schemes Advances in Cryptology -EUROCRYPT 2005[END_REF][START_REF] Dubois | Cryptanalysis of HFE with Internal Perturbation[END_REF][START_REF] Nie | Cryptanalysis of Hash-based Tamed Transformation and Minus Signature Scheme[END_REF].

Piece in Hand (PH) method is another security enhancement method introduced and studied in a series of papers [START_REF] Tsujii | Piece in Hand concept for enhanceing the security of multivariate type public key cryptosystem: public key without containing all the information of secret key[END_REF][START_REF] Tsujii | Proposal for piece in hand matrix ver.2: General concept for enhancing security of multivariate pulic key cryptosystem[END_REF][START_REF] Fujita | Nonlinear piece in hand perturbation vector method for enhancing security of multivariate public key cryptosystems[END_REF][START_REF] Tsujii | Security Enhancement of Various MPKCs by 2-layer Nonlinear Piece in Hand Method[END_REF]. In [START_REF] Tsujii | Security Enhancement of Various MPKCs by 2-layer Nonlinear Piece in Hand Method[END_REF], Tsuji et al. proposed the 2-layer nonlinear Piece in Hand method. For this, they introduced two vectors of polynomials: an auxiliary polynomial vector and a perturbation polynomial vector. The perturbation polynomial vector is used to add perturbation to the underlying MPKC, whereas the auxiliary polynomial vector is constructed to be efficiently invertible which will be used during the decryption process. Since the information of the auxiliary polynomial vector is part of the public key, the security of the whole scheme relies on the structure of this vector. In their paper [START_REF] Tsujii | Security Enhancement of Various MPKCs by 2-layer Nonlinear Piece in Hand Method[END_REF], the authors gave two examples for this vector, called H 1 and H 2 .

In this paper we show that both H 1 and H 2 satisfy Linearization Equations (LEs) of the form

∑ 𝑎 𝑖𝑗 ⋅ 𝑥 𝑖 ⋅ 𝑦 𝑗 + ∑ 𝑏 𝑖 ⋅ 𝑥 𝑖 + ∑ 𝑐 𝑗 ⋅ 𝑦 𝑗 + 𝑑 = 0, (1)
where 𝑥 𝑖 are the plaintext variables and 𝑦 𝑗 are the ciphertext variables.

After finding all the LEs and substituting a valid ciphertext into these equations, we can get a system of linear equations in the plaintext variables. By solving this system, we can represent some of the plaintext variables by linear combinations of the other plaintext variables. Hence, we can do elimination on the public key. And we can perform a similar analysis on the eliminated public key to check if there are Linearization Equations satisfied by the simplified public key.

In the case of H 1 , given a valid ciphertext, we can, after two eliminations on the public key, find a public key equivalent to that of the original MPKC. In the case of H 2 , given a valid ciphertext, we can achieve the same goal using three eliminations on the public key. This means that Piece in Hand method using these two auxiliary polynomial vectors can not enhance the security of the underlying MPKC. So, we must be very careful when designing the auxiliary polynomial vector of PH method.

The rest of this paper is organized as follows. In Section 2 we give a brief description of MPKCs and Linearization Equations. Section 3 introduces the 2-layer nonlinear Piece in Hand method. In Section 4, we present our cryptanalysis of the enhanced scheme and present the results of our computer experiments. Finally, in Section 5, we conclude the paper.

Multivariate Public Key Cryptography

To build a multivariate public key cryptosystem (MPKC), one starts with an easily invertible map ℱ : 𝔽 𝑛 → 𝔽 𝑚 (central map). To hide the structure of ℱ in the public key, one combines it with two invertible affine maps 𝒯 : 𝔽 𝑚 → 𝔽 𝑚 and 𝒰 : 𝔽 𝑛 → 𝔽 𝑛 . Therefore the public key has the form

ℰ : 𝔽 𝑛 → 𝔽 𝑚 , y = (𝑦 1 , . . . , 𝑦 𝑚 ) = ℰ(𝑥 1 , . . . , 𝑥 𝑛 ) = 𝒯 ∘ ℱ ∘ 𝒰(𝑥 1 , . . . , 𝑥 𝑛 ). ( 2
)
The private key consists out of the three maps 𝒯 , ℱ and 𝒰 and therefore allows to invert the public key.

Linearization Equations

For MPKCs, a Linearization Equation (LE) is an equation in the , we can substitute it into equation (3) to get a linear equation in the plaintext variables. By finding all these equations we get a linear system which can be solved by Gaussian Elimination. After having found a solution, we can do elimination on the public key.

2-layer Piece In Hand Method

We use the same notation as in [START_REF] Tsujii | Security Enhancement of Various MPKCs by 2-layer Nonlinear Piece in Hand Method[END_REF]. Let ℰ : 𝔽 𝑛 → 𝔽 𝑚 be the public map of a multivariate public key encryption scheme with {𝑥 1 , . . . , 𝑥 𝑛 } and {𝑦 1 , . . . , 𝑦 𝑚 } being the plaintext and ciphertext variables repectively and 𝑙 be a positive integer. To enhance the security of the MPKC, the inventors of the 2-layer nonlinear Piece in Hand method introduced an auxiliary polynomial vector H of 𝑙 components and a perturbation polynomial vector J . The elements of the auxiliary polynomial vector H are products of two random linear polynomials ℎ 𝑖 and ℎ 𝑗 , where the functions ℎ 𝑖 are given by ℎ 𝑖 = ∑ 𝑛 𝑗=1 𝑠 𝑖𝑗 ⋅ 𝑥 𝑗 (𝑖 = 1, . . . , 𝑙) with 𝑠 𝑖𝑗 ∈ 𝑅 𝔽. The perturbation polynomial vector J is a vector with 𝑙(𝑙 -1)/2 components constructed from the polynomials ℎ 𝑖 ⋅ ℎ 𝑗 (1 ≤ 𝑖 < 𝑗 ≤ 𝑙). Note that the polynomial components of the vector H are designed to be easily invertible for decryption. Therefore, one can use the vector H to compute the values of ℎ 𝑖 (𝑖 = 1, . . . , 𝑙) and sequentially calculate the value of the vector J . By the above construction, one gets an enhanced public key Ẽ : 𝔽 𝑛 → 𝔽 𝑚+𝑙 of the form

Ẽ(𝑥 1 , . . . , 𝑥 𝑛 ) = 𝐵 ( ℰ(𝑥 1 , . . . , 𝑥 𝑛 ) + 𝐷J 𝐶H ) ( 5
)
where 𝐵 is an (𝑚 + 𝑙) × (𝑚 + 𝑙) invertible matrix over 𝔽, 𝐷 is an 𝑚 × 𝑙⋅(𝑙-1) 2 matrix over 𝔽, and 𝐶 is an 𝑙 × 𝑙 invertible matrix over 𝔽.

Secret key: The secret key includes -the secret key of the underlying MPKC -the matrices 𝐵, 𝐶 and 𝐷 -the auxiliary polynomial vector H and -the perturbation polynomial vector J .

Public key:

The 𝑚 + 𝑙 components of the function Ẽ.

Encryption: Given a plaintext x ′ = (𝑥 ′ 1 , . . . , 𝑥 ′ 𝑛 ), compute y ′ = (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+𝑙 ) = Ẽ(𝑥 ′ 1 , . . . , 𝑥 ′ 𝑛 ).
Decryption: Given a valid ciphertext y ′ = (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+𝑙 ), decryption includes the following steps:

1. Compute v ′ = (𝑣 ′ 1 , . . . , 𝑣 ′ 𝑚+𝑙 ) = 𝐵 -1 (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+𝑙 ) 𝑇 ; 2. Compute H = 𝐶 -1 (𝑣 ′ 𝑚+1 , . . . , 𝑣 ′ 𝑚+𝑙 ) 𝑇
and get the values of ℎ 𝑖 (𝑖 = 1, . . . , 𝑙); 3. Compute the value of J by substituting the values of ℎ 𝑖 (𝑖 = 1, . . . , 𝑙) into its components; 4. Compute

x ′ = (𝑥 ′ 1 , . . . , 𝑥 ′ 𝑛 ) = ℰ -1 (𝑣 ′ 1 -𝑑𝑗 1 , . . . , 𝑣 ′ 𝑚 -𝑑𝑗 𝑚 )
, where (𝑑𝑗 1 , . . . , 𝑑𝑗 𝑚 ) 𝑇 = 𝐷J.

Examples for the auxiliary vector H and the perturbation vector J

In [START_REF] Tsujii | Security Enhancement of Various MPKCs by 2-layer Nonlinear Piece in Hand Method[END_REF], the authors gave two examples for the choice of the auxiliary vector H, denoted by H 1 and H 2 , respectively. For arbitrary 𝑙, the vector H 1 is given by

H 1 = (𝑢 1 , . . . , 𝑢 𝑙 ) 𝑇 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ℎ 1 ℎ 2 + 𝛼 1 ℎ 2 ℎ 3 + 𝛼 2 ℎ 3 ℎ 1 + 𝛼 3 ℎ 1 ℎ 4 + 𝛼 4 ℎ 1 ℎ 5 + 𝛼 5 . . . ℎ 1 ℎ 𝑙-1 + 𝛼 𝑙-1 ℎ 1 ℎ 𝑙 + 𝛼 𝑙 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . ( 6
)
with 𝛼 1 , . . . , 𝛼 𝑙 ∈ 𝑅 𝔽. For our experiments (see Subsection 4.3) we use the value 𝑙 = 8. Apparently, given the value of the vector (𝑢 1 , . . . , 𝑢 𝑙 ), we can get from the first three equations of ( 6)

ℎ 1 = ( (𝑢 1 -𝛼 1 )(𝑢 3 -𝛼 3 ) (𝑢 2 -𝛼 2 ) ) 1 2 (7)
and then get the values of ℎ 2 , ℎ 3 , . . . , ℎ 𝑙 in turn.

For the auxiliary map H 2 , the value 𝑙 is fixed to 15. We have

H 2 = (𝑢 1 , . . . , 𝑢 15 ) 𝑇 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ℎ 1 ℎ 2 + 𝛼 1 ℎ 2 ℎ 3 + 𝛼 2 ℎ 3 ℎ 4 + 𝛼 3 ℎ 4 ℎ 5 + 𝛼 4 ℎ 5 ℎ 1 + 𝛼 5 ℎ 2 6 + ℎ 1 ℎ 3 + 𝛼 6 ℎ 2 7 + ℎ 3 ℎ 5 + 𝛼 7 ℎ 2 8 + ℎ 5 ℎ 2 + 𝛼 8 ℎ 2 9 + ℎ 2 ℎ 4 + 𝛼 9 ℎ 2 10 + ℎ 4 ℎ 1 + 𝛼 10 ℎ 1 ℎ 10 + ℎ 6 ℎ 11 + 𝛼 11 ℎ 2 ℎ 9 + ℎ 7 ℎ 12 + 𝛼 12 ℎ 3 ℎ 8 + ℎ 8 ℎ 13 + 𝛼 13 ℎ 4 ℎ 7 + ℎ 9 ℎ 14 + 𝛼 14 ℎ 5 ℎ 6 + ℎ 10 ℎ 15 + 𝛼 15 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (8)
where 𝛼 𝑖 ∈ 𝑅 𝔽 (𝑖 = 1, . . . , 𝑙). Similarly to H 1 , H 2 can be easily inverted. The perturbation vector J used in [START_REF] Tsujii | Security Enhancement of Various MPKCs by 2-layer Nonlinear Piece in Hand Method[END_REF] is given as follows:

J = (𝑗 1 , 𝑗 2 , . . . , 𝑗 𝑙(𝑙-1)/2 ) = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ℎ 1 ℎ 2 + 𝛽 1 ℎ 1 ℎ 3 + 𝛽 2 . . . ℎ 1 ℎ 𝑙 + 𝛽 𝑙-1 ℎ 2 ℎ 3 + 𝛽 𝑙 . . . ℎ 2 ℎ 𝑙 + 𝛽 2𝑙-3 ℎ 3 ℎ 4 + 𝛽 2𝑙-2 . . . ℎ 𝑙-1 ℎ 𝑙 + 𝛽 𝑙(𝑙-1)/2 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (9)
where 𝛽 𝑖 ∈ 𝑅 𝔽 (𝑖 = 1, . . . , 𝑙(𝑙 -1)/2).

Cryptanalysis of the 2-layer PH Method

Although the perturbation map J can hide the weak point of the underlying MPKC scheme, the security of the enhanced scheme depends mainly on the design of the auxiliary map H. Bad design of the vector H will bring some new security problems to the scheme. Both vectors H 1 and H 2 of [START_REF] Tsujii | Security Enhancement of Various MPKCs by 2-layer Nonlinear Piece in Hand Method[END_REF] are not properly chosen to enhance the security of the underlying scheme, since they satisfy Linearization Equations.

In this section, we present our cryptanalysis of the 2-layer PH method with auxiliary polynomial vector H 1 and H 2 , respectively. Given a valid ciphertext y ′ = (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+𝑙 ) 𝑇 , our goal is to find the corresponding plaintext. Namely, we have to solve the system

⎧  ⎨  ⎩ 𝑦 ′ 1 = Ẽ1 (𝑥 1 , . . . , 𝑥 𝑛 ) . . . 𝑦 ′ 𝑚+𝑙 = Ẽ𝑚+𝑙 (𝑥 1 , . . . , 𝑥 𝑛 ) . ( 10
)

Case of H 1

Through theoretical analysis, we find that the system Ẽ satisfies Linearization Equations, which are brought in by the vector H 1 . Given a valid ciphertext we can, after finding all FOLEs, recover the corresponding plaintext easily.

Linearization Equations

In the expression of the polynomial vector H 1 (see ( 6)), we have

𝑢 1 = ℎ 1 ℎ 2 + 𝛼 1 and 𝑢 2 = ℎ 2 ℎ 3 + 𝛼 2 .
Hence we get

ℎ 3 (𝑢 1 -𝛼 1 ) = ℎ 1 (𝑢 2 -𝛼 2 ). ( 11
)
Since the matrices 𝐵 and 𝐶 are invertible, the elements 𝑢 𝑖 (𝑖 = 1, . . . , 𝑙) can be expressed by linear equations in the ciphertext variables, namely 𝑢 𝑖 = ∑ 𝑚+𝑙 𝑗=1 𝑡 𝑖𝑗 ⋅ 𝑦 𝑗 (𝑖 = 1, . . . , 𝑙). Analogously we get ℎ 𝑖 = ∑ 𝑛 𝑗=1 𝑠 𝑖𝑗 ⋅ 𝑥 𝑗 (𝑖 = 1, . . . , 𝑙). Hence equation [START_REF] Faugère | Algebraic Cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF] implies that the plaintext variables {𝑥 1 , . . . , 𝑥 𝑛 } and ciphertext variables {𝑦 1 , . . . , 𝑦 𝑚+𝑙 } satisfy an equation of the form:

𝑛 ∑ 𝑖=1 𝑚+𝑙 ∑ 𝑗=1 𝑎 𝑖𝑗 ⋅ 𝑥 𝑖 ⋅ 𝑦 𝑗 + 𝑛 ∑ 𝑖=1 𝑏 𝑖 ⋅ 𝑥 𝑖 + 𝑚+𝑙 ∑ 𝑗=1 𝑐 𝑗 ⋅ 𝑦 𝑗 + 𝑑 = 0. ( 12
)
This equation is exactly a FOLE. Similarly, from each of the pairs

ℎ 𝑗 (𝑢 𝑖 -𝛼 𝑖 ) = ℎ 𝑖 (𝑢 𝑗 -𝛼 𝑗 ) (1 ≤ 𝑖 < 𝑗 ≤ 𝑙, 𝑖 ∕ = 2
) and the pair ℎ 1 (𝑢 2 -𝛼 2 ) = ℎ 2 (𝑢 3 -𝛼 3 ), we can get an additional FOLE. Hence there exist at least (𝑙 -2)(𝑙 -1)/2 + 1 linear independent Linearization Equations of type [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF].

To find these FOLEs, we randomly generate 𝐷 1 ≥ 𝑛(𝑚 + 𝑙) + 𝑛 + 𝑚 + 𝑙 + 1 plaintext/ciphertext pairs and substitute them into equation [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF]. By doing so, we get a system of 𝐷 1 linear equations in the 𝑛(𝑚 + 𝑙) + 𝑛 + 𝑚 + 𝑙 + 1 unknowns 𝑎 𝑖𝑗 , 𝑏 𝑖 , 𝑐 𝑗 and 𝑑 which can be solved by Gaussian Elimination. We denote the solution space by 𝑉 and its dimension by 𝐷. Hence, we derive 𝐷 linearly independent equations of type [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF] in the plaintext and ciphertext variables.

The work above depends only on the public key and can be done once for a given public key.

By substituting the given ciphertext y ′ = (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+𝑙 ) into the Linearization Equations found above we get 𝐷 linear equations in the plaintext variables. Let's assume that 𝑡 1 of these equations are linearly independent.

First Elimination

By substituting the 𝑡 1 equations found above into the public key Ẽ of the 2-layer nonlinear PH scheme, we can eliminate 𝑡 1 equations from Ẽ. By doing so, we get a simplified public key Ẽ′ of the form

{ 𝑦 ′ 𝑗 = Ẽ′ 𝑗 (𝑤 1 , . . . , 𝑤 𝑛-𝑡1 ) 1 ≤ 𝑗 ≤ 𝑚 + 𝑙 . ( 13
)

Second Elimination

In the practical setting of [START_REF] Tsujii | Security Enhancement of Various MPKCs by 2-layer Nonlinear Piece in Hand Method[END_REF], the characteristic of the underlying field 𝔽 was chosen to be 2. Using this property, we can find another type of Linearization Equations satisfied by the simplified public key Ẽ′ .

We denote by 𝑢 ′ 𝑖 (𝑖 = 1, . . . , 𝑙) the value of 𝑢 𝑖 corresponding to the given ciphertext y ′ = (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+𝑙 ). Such we get

⎧            ⎨            ⎩ 𝑢 ′ 1 = ℎ 1 ℎ 2 + 𝛼 1 𝑢 ′ 2 = ℎ 2 ℎ 3 + 𝛼 2 𝑢 ′ 3 = ℎ 3 ℎ 1 + 𝛼 3 𝑢 ′ 4 = ℎ 1 ℎ 4 + 𝛼 4 𝑢 ′ 5 = ℎ 1 ℎ 5 + 𝛼 5 . . . 𝑢 ′ 𝑙-1 = ℎ 1 ℎ 𝑙-1 + 𝛼 𝑙-1 𝑢 ′ 𝑙 = ℎ 1 ℎ 𝑙 + 𝛼 𝑙 . ( 14
)
According to FOLEs similar to equation ( 11), we find

⎧            ⎨            ⎩ ℎ 2 = 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 1 ℎ 3 = 𝑢 ′ 2 -𝛼2 𝑢 ′ 1 -𝛼1 ℎ 1 ℎ 4 = 𝑢 ′ 4 -𝛼4 𝑢 ′ 1 -𝛼1 ⋅ 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 1 ℎ 5 = 𝑢 ′ 5 -𝛼5 𝑢 ′ 1 -𝛼1 ⋅ 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 1 . . . ℎ 𝑙 = 𝑢 ′ 𝑙 -𝛼 𝑙 𝑢 ′ 1 -𝛼1 ⋅ 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 1 . ( 15
)
By substituting ( 15) into ( 6), we get

⎧              ⎨              ⎩ 𝑢 1 = 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 2 1 + 𝛼 1 𝑢 2 = 𝑢 ′ 2 -𝛼2 𝑢 ′ 1 -𝛼1 ⋅ 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 2 1 + 𝛼 2 𝑢 3 = 𝑢 ′ 2 -𝛼2 𝑢 ′ 1 -𝛼1 ℎ 2 1 + 𝛼 3 𝑢 4 = 𝑢 ′ 4 -𝛼4 𝑢 ′ 1 -𝛼1 ⋅ 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 2 1 + 𝛼 4 𝑢 5 = 𝑢 ′ 5 -𝛼5 𝑢 ′ 1 -𝛼1 ⋅ 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 2 1 + 𝛼 5 . . . 𝑢 𝑙 = 𝑢 ′ 𝑙 -𝛼 𝑙 𝑢 ′ 1 -𝛼1 ⋅ 𝑢 ′ 2 -𝛼2 𝑢 ′ 3 -𝛼3 ℎ 2 1 + 𝛼 𝑙 . ( 16
)
Due to 𝑢 𝑖 = ∑ 𝑚+𝑙 𝑗=1 𝑡 𝑖𝑗 ⋅ 𝑦 𝑗 (𝑖 = 1, . . . , 𝑙) and ℎ 𝑖 = ∑ 𝑛 𝑗=1 𝑠 𝑖𝑗 ⋅ 𝑥 𝑗 (𝑖 = 1, . . . , 𝑙) and using the fact that squaring is a linear operation on a field of characteristic 2, we have at least one equation satisfied by ciphertext variables and the remaining plaintext variables of the form

{ ∑ 𝑚+𝑙 𝑗=1 ã𝑗 ⋅ 𝑦 ′ 𝑗 + ∑ 𝑛-𝑡1 𝑖=1 b𝑖 ⋅ 𝑤 2 𝑖 + c = 0 ∀𝑤 1 , . . . , 𝑤 𝑛-𝑡1 ∈ 𝔽 . ( 17
)
It is easy to solve the above linear system for the ã𝑖 , b𝑗 and c. Let {ã

(𝜌) 1 , ⋅ ⋅ ⋅ , ã(𝜌) 𝑚+𝑙 , b(𝜌) 1 , ⋅ ⋅ ⋅ , b(𝜌) 𝑛-𝑡1 , c(𝜌) , 1 ≤ 𝜌 ≤ 𝑟} be a basis of the solution space of the system (17). Set ⎧ ⎨ ⎩ 𝑛-𝑡1 ∑ 𝑗=1 ( b(𝜌) 𝑗 ) 1/2 ⋅ 𝑤 𝑗 + ( 𝑚+𝑙 ∑ 𝑖=1 ã𝑖 (𝜌) ⋅ 𝑦 ′ 𝑖 + c(𝜌) ) 1/2 = 0 1 ≤ 𝜌 ≤ 𝑟 . ( 18
)
For any vector w = (𝑤 1 , . . . 𝑤 𝑛-𝑡1 ), w and the corresponding ciphertext (𝑦 1 , . . . , 𝑦 𝑚+𝑙 ) = Ẽ′ (w) satisfy equation [START_REF] Nie | Cryptanalysis of Hash-based Tamed Transformation and Minus Signature Scheme[END_REF]. Therefore we can represent at least one variable of the set {𝑤 1 , . . . , 𝑤 𝑛-𝑡1 } as a linear equation in the remaining variables. Denote the remaining variables by 𝑣 1 , . . . , 𝑣 𝑛-𝑡1-1 . Substituting this linear expression into the system (13), we can get a new public key with (𝑛 -𝑡 1 -1) unknowns, denoted as

{ 𝑦 ′ 𝑗 = Ẽ′′ 𝑗 (𝑣 1 , . . . , 𝑣 𝑛-𝑡1-1 ) 1 ≤ 𝑗 ≤ 𝑚 + 𝑙 . ( 19
)

Eliminating Perturbation

Furthermore, after two eliminations, the vector J becomes a constant vector, namely, the perturbation of Piece in Hand method is eliminated. The reason for this is shown as follows. From ( 16), we get

ℎ 1 = ( (𝑢 ′ 1 -𝛼 1 )(𝑢 ′ 3 -𝛼 3 ) 𝑢 ′ 2 -𝛼 2 ) 1/2 . ( 20
)
Substituting ( 20) and ( 15) into ( 9), the vector J becomes a constant vector on 𝔽. For example,

𝑗 1 = ℎ 1 ℎ 2 + 𝛽 1 = 𝑢 ′ 1 -𝛼 1 + 𝛽 1 , 𝑗 𝑙+1 = ℎ 2 ℎ 4 + 𝛽 𝑙+1 = ( (𝑢 ′ 2 -𝛼 2 )(𝑢 ′ 4 -𝛼 4 ) 𝑢 ′ 3 -𝛼 3 ) + 𝛽 𝑙+1 .
Hence, the public key Ẽ′′ of equation ( 19) is equivalent to the public key of the underlying MPKC scheme.

If there exists an algorithm which recovers the plaintext corresponding to a valid ciphertext for the underlying MPKC scheme, we can therefore find the values of the variables 𝑣 1 , . . . , 𝑣 𝑛-𝑡1-1 corresponding to the valid ciphertext y ′ . Using the linear equations found during the two eliminations above, we can recover the values of the remaining plaintexts variables.

Case of H 2

Let 𝑦 ′ = (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+15 ) be a valid ciphertext of the Piece in Hand MPKC with auxiliary map H 2 . Again we want to find the corresponding plaintext 𝑥 ′ = (𝑥 ′ 1 , . . . , 𝑥 ′ 𝑛 ) by solving the system [START_REF] Fujita | Nonlinear piece in hand perturbation vector method for enhancing security of multivariate public key cryptosystems[END_REF].

Similarly to the case of H 1 , from the first five equations in (8), we can get five FOLEs between 𝑢 𝑖 and ℎ 𝑖 (1

≤ 𝑖 ≤ 5) by ⎧     ⎨     ⎩ ℎ 3 (𝑢 1 -𝛼 1 ) = ℎ 1 (𝑢 2 -𝛼 2 ) ℎ 4 (𝑢 2 -𝛼 2 ) = ℎ 2 (𝑢 3 -𝛼 3 ) ℎ 5 (𝑢 3 -𝛼 3 ) = ℎ 3 (𝑢 4 -𝛼 4 ) ℎ 1 (𝑢 4 -𝛼 4 ) = ℎ 4 (𝑢 5 -𝛼 5 ) ℎ 2 (𝑢 5 -𝛼 5 ) = ℎ 5 (𝑢 1 -𝛼 1 )
.

Apparently, these five equations are linearly independent. Hence, we can get at least five Linearization Equations satisfied by plain-and ciphertext variables of the form [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF]. Using the same method as in Subsection 4.1, we do the first elimination on the system [START_REF] Fujita | Nonlinear piece in hand perturbation vector method for enhancing security of multivariate public key cryptosystems[END_REF]. Suppose we eliminated 𝑡 1 ≥ 4 variables in the system. Denote the remaining plaintext variables by 𝑤 1 , . . . , 𝑤 𝑛-𝑡1 and let

{ 𝑦 ′ 𝑗 = Ẽ′ 𝑗 (𝑤 1 , . . . , 𝑤 𝑛-𝑡1 ) 1 ≤ 𝑗 ≤ 𝑚 + 15 (21)
be the simplified public key. Using a similar method as in Subsection 4.1, we can perform two additional eliminations on the system [START_REF] Patarin | Flash, a fast multivariate signature algorithm[END_REF]. Due to the limitation of paper size, we omit the details of this part here. We will present them in the full version of this paper. But we should point out the following facts.

For the public key Ẽ′ 𝑗 (𝑤 1 , . . . , 𝑤 𝑛-𝑡1 ), plain-and ciphertext variables satisfy equations of the form

𝑚+𝑙 ∑ 𝑗=1 ã𝑗 ⋅ 𝑦 𝑗 + 𝑛-𝑡1 ∑ 𝑖=1 b𝑖 ⋅ 𝑤 2 𝑖 + c = 0. ( 22
)
By substituting the ciphertext y ′ into these equations and using the fact that squaring is a linear function over fields of characteristic 2, we can find 𝑡 2 ≥ 6 linear equations in the plaintext variables. We can therefore eliminate 𝑡 2 variables from the public key. After this elimination, the simplified public key has the form

{ 𝑦 ′ 𝑗 = Ẽ′′ 𝑗 (𝑣 1 , . . . , 𝑣 𝑛-𝑡1-𝑡2 ) 1 ≤ 𝑗 ≤ 𝑚 + 15 . ( 23
)
The public key Ẽ′′ satisfies equations of the form

𝑚+15 ∑ 𝑗=1 ã𝑗 ⋅ 𝑦 𝑗 + 𝑛-𝑡1-𝑡2 ∑ 𝑖=1 b𝑖 ⋅ 𝑣 𝑖 + c = 0. (24)
By substituting the ciphertext y ′ into these equations, we can find 𝑡 3 ≥ 5 linear equations in the variables 𝑣 1 , . . . , 𝑣 𝑛-𝑡1-𝑡2 . Therefore, we can eliminate 𝑡 3 variables from the system [START_REF] Tsujii | Piece in Hand concept for enhanceing the security of multivariate type public key cryptosystem: public key without containing all the information of secret key[END_REF] and get a new public key Ẽ′′′ of the form

{ 𝑦 ′ 𝑗 = Ẽ′′′ 𝑗 (𝑢 1 , . . . , 𝑢 𝑛-𝑡1-𝑡2-𝑡3 ) 1 ≤ 𝑗 ≤ 𝑚 + 15 . ( 25
)
For the public key Ẽ′′′ , the perturbation vector J becomes a constant vector. Hence, Ẽ′′′ is equivalent to the public key of the underlying MPKC. Analogously to Subsection 4.1 we can therefore, under the assumption that there exists an algorithm which, for the underlying MPKC, finds for a given ciphertext the corresponding plaintext, construct an algorithm which, for any given ciphertext y ′ = (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+15 ), recovers the corresponding plaintext x ′ = (𝑥 ′ 1 , . . . , 𝑥 ′ 𝑛 ).

Complexity and Experimental Verification

In our concrete attack scenario we set 𝔽 = 𝐺𝐹 (256) and 𝑚 = 𝑛 = 25. As the underlying MPKC we used the 𝐶 ★ scheme of Matsumoto and Imai. We implemented the Piece in Hand cryptosystem in two different ways using H 1 (with 𝑙 = 8) and H 2 as auxiliary matrix respectively. For our attack we chose randomly a valid ciphertext y ′ = (𝑦 ′ 1 , . . . , 𝑦 ′ 𝑚+𝑙 ) ∈ 𝔽 𝑚+𝑙 . Our goal was to find the corresponding plaintext x ′ = (𝑥 ′ 1 , . . . , 𝑥 ′ 𝑛 ) ∈ 𝔽 𝑛 .

Case of 𝑯 1

In the first step we computed 900 (> 𝑛(𝑚+𝑙)+𝑛+𝑚+𝑙 +1 = 884) plaintext/ciphertext pairs and substituted them into the Linearization Equation of type [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF]. We did Gaussian Elimination on this linear system and found a basis of all FOLEs. The complexity of the Gaussian Elimination is equal to (𝑛(𝑚 + 𝑙) + 𝑛 + 𝑚 + 𝑙 + 1) 3 operations on the finite field 𝔽. In our experiments, (𝑛(𝑚 + 𝑙) + 𝑛 + 𝑚 + 𝑙 + 1) 3 = 884 3 ≤ 2 30 .

We found that the dimension of the space spanned by all FOLEs is 𝐷 = (𝑙 -2)(𝑙 -1)/2 = 22.

Computing the plaintext/ciphertext pairs and solving this large linear system proved to be the most time-consuming step of our attack. In our experiments, it took about 70 seconds, where it took about 68 seconds on generating the plaintext/ciphertext pairs and about 2 seconds on the Gaussian Elimination. This step is independent of the given ciphertext y ′ and has to be done for a given public key only once. After substituting the ciphertext y ′ into these equations we obtained 7 linear equations in the plaintext variables.

In the second step we computed 100 plaintext/ciphertext pairs and substituted them into the Linearization Equation of type [START_REF] Nie | Breaking A New Instance of TTM Cryptosystem[END_REF]. By doing so, we got 15 linearly independent equations of the form [START_REF] Nie | Breaking A New Instance of TTM Cryptosystem[END_REF]. By evaluating equation ( 18), we got 1 linear equation in the plaintext variables.

We substituted the 8 linear equations found in the previous steps into the public key and obtained a new public key Ẽ′′ of 33 equations in 17 variables, which proved to be of the form of a 𝐶 ★ public key (i.e. the perturbation was eliminated).

In the last step of the attack, we attacked the new public key Ẽ′′ with the Linearization Equation attack of Patarin [START_REF] Patarin | Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt[END_REF]. We computed 500 plaintext/ciphertext pairs and substituted them into the Linearization Equation of type [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF]. By doing so, we got 25 linear independent equations of type [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF]. After substituting the ciphertext 𝑦 ′ we obtained 17 linear equations in the plaintext variables which enabled us to reconstruct the plaintext x ′ . The running time of the whole attack was about 90 seconds.

Case of 𝑯 2

In the first step we computed 1100 (> (𝑛(𝑚+15)+𝑛+𝑚+15+1) = 1066) plaintext/ciphertext pairs and substituted them into the Linearization Equation of type [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF]. We solved the resulting linear system for the variables 𝑎 𝑖𝑗 , 𝑏 𝑖 , 𝑐 𝑗 and 𝑑 to find a basis of all FOLEs. By doing so, we found 5 linear independent Linearization Equations. After substituting the ciphertext y ′ into these equations we obtained 4 linear equations in the plaintext variables. The complexity of this step is equal to 1066 3 ≤ 2 31 . It took about 104 seconds in our experiments, where it took about 102 seconds on generating the plaintext/ciphertext pairs and about 2 second on the Gaussian Elimination. This step has to be performed for each public key only once.

In the second step we computed 100 plaintext/ciphertext pairs and substituted them into the Linearization Equation of type [START_REF] Patarin | 𝐶 * -+ and HM: variations around two schemes of[END_REF]. By doing so, we got 14 linear independent equations of form [START_REF] Patarin | 𝐶 * -+ and HM: variations around two schemes of[END_REF]. After substituting the ciphertext y ′ , we got 6 linear equations in the plaintext variables.

In the third step we computed again 100 plaintext/ciphertext pairs and substituted them into the Linearization Equation of type [START_REF] Tsujii | Proposal for piece in hand matrix ver.2: General concept for enhancing security of multivariate pulic key cryptosystem[END_REF]. We obtained 25 linear independent equations. By substituting the ciphertext y ′ into these equations, we got 5 linear equations in the plaintext variables. We substituted the 15 linear equations found in the previous steps into the public key and obtained a new public key Ẽ′′′ of 40 equations in 10 variables, which proved to be of the form of a 𝐶 ★ public key (i.e. the perturbation was eliminated).

In the last step of the attack, we attacked the new key Ẽ′′′ with the Linearization Equation attack of Patarin [START_REF] Patarin | Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt[END_REF]. We computed 500 plaintext/ciphertext pairs and substituted them into the Linearization Equation of type [START_REF] Faugère | Cryptanalysis of the Hidden Matrix Cryptosystem[END_REF]. By doing so, we obtained 25 linear independent equations. After substituting the ciphertext y ′ we got 10 linear equations in the plaintext variables which enabled us to reconstruct the plaintext x ′ . The running time of the whole attack was about 127 seconds.

All experiments were performed on a server with 24 AMD Opteron processors and 128 GB RAM. However, for our experiments we used only a single core. The attack was programmed in Magma code and required about 120 MB of memory.

Conclusion

In this paper, we presented the cryptanalysis of two examples of the 2-layer nonlinear Piece in Hand method. As we showed, both examples do not enhance the security of the underlying MPKC because they can not resist Linearization Equation attacks. From this paper, we find that the security of the 2-layer nonlinear Piece in Hand method depends mainly on the construction of the auxiliary polynomial vector H. We should therefore design the auxiliary polynomial vector H in such a way that it resists existing attacks.

  are polynomial functions in the ciphertext variables. The highest degree of 𝑔 𝑗 , 1 ≤ 𝑗 ≤ 𝑙 is called the order of the LE.

	For example, a First Order Linearization Equation (FOLE) looks like
	𝑛 ∑	𝑚 ∑	𝑎 𝑖𝑗 ⋅ 𝑥 𝑖 ⋅ 𝑦 𝑗 +	𝑛 ∑	𝑏 𝑖 ⋅ 𝑥 𝑖 +	𝑚 ∑	𝑐 𝑗 ⋅ 𝑦 𝑗 + 𝑑 = 0.	(4)
	𝑖=1	𝑗=1		𝑖=1		𝑗=1
	Note that, given a valid ciphertext y ′ = (𝑦 ′ 1 , 𝑦 ′ 2 , . . . , 𝑦 ′ 𝑚 )

𝑛 + 𝑚 plaintext/ciphertext variables 𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑛 , 𝑦 1 , 𝑦 2 , . . . , 𝑦 𝑚 of the form 𝑛 ∑ 𝑖=1 𝑡 ∑ 𝑗=1 𝑎 𝑖𝑗 ⋅ 𝑥 𝑖 ⋅ 𝑔 𝑗 (𝑦 1 , 𝑦 2 , . . . , 𝑦 𝑚 ) + 𝑙 ∑ 𝑗=1 𝑐 𝑗 ⋅ 𝑓 𝑗 (𝑦 1 , 𝑦 2 , . . . , 𝑦 𝑚 ) + 𝑑 = 0. (

3

)

where 𝑓 𝑗 (1 ≤ 𝑗 ≤ 𝑙), 𝑔 𝑗 (1 ≤ 𝑗 ≤ 𝑙),

Acknowledgements

We want to thank the anonymous reviewers for their comments which helped to improve the paper. The first author is supported by the National Key Basic Research Program of China (2013CB834203), the National Natural Science Foundation of China (No. 61103205), the Fundamental Research Funds for the Central Universities under Grant ZYGX2010J069. The second author thanks the Horst Görtz Foundation for financial support.


Christian Hanser

Christian Wagner

Speeding Up the Fixed-Base Comb Method for Faster Scalar Multiplication on Koblitz Curves

Keywords: ECC, scalar multiplication, Lim-Lee method, comb method, Koblitz curves, Frobenius endomorphism, τ -adic representation

Scalar multiplication is the most expensive arithmetical operation on elliptic curves. There are various methods available, which are optimized for different settings, such as high speed, side-channel resistance and small memory footprint. One of the fastest methods for fixed-base scalar multiplications is the so-called fixed-base comb scalar multiplication method, which is due to Lim and Lee. In this paper, we present a modification to this method, which exploits the possibility of exchanging doublings for much cheaper applications of the Frobenius endomorphism on binary Koblitz curves. We have implemented the findings in software and compare the performance of the implementation to the performance of the reference WTNAF implementation and the performance of the conventional comb multiplication methods. For single scalar multiplications, we are able to achieve performance improvements over the WTNAF method of up to 25% and of up to 42% over the conventional comb methods. Finally, we emphasize that the implementation of the τ -comb method is straight-forward and requires only little effort. All in all, this makes it a good alternative to other fixed-base multiplication methods.

Introduction

In 1985, Neal Koblitz [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF] and Victor S. Miller [START_REF] Miller | Use of elliptic curves in cryptography[END_REF] both discovered independently that elliptic curves over finite fields can be used for public key cryptography. By now, elliptic curves have become an important concept within public key cryptography. This is mainly due to small key sizes compared to other public key cryptosystems, such as RSA, which lower the requirements for CPUs as well as the memory footprint. Elliptic curves have a group structure and their cryptographic security relies on the difficulty of solving the elliptic curve discrete logarithm problem (ECDLP).

The most expensive, yet, at the same time most important operation, on elliptic curves is the scalar multiplication. There are plenty of different techniques achieving optimizations for different settings, such as high speed through the reduction of group operations, side-channel resistance and small memory footprint. In this paper we are focusing solely on the performance aspects of scalar multiplication. Koblitz curves allow trading the doubling operation for another operation, that is, the application of the so-called Frobenius endomorphism, which is inexpensive compared to point doubling. In the context of Koblitz curves, many multiplication methods relying on a non-adjacent form (NAF), such as windowed non-adjacent form (WNAF), interleaved simultaneous point multiplication, etc., have been adapted, so that doublings can be replaced by far more efficient applications of the Frobenius endomorphism. Yet, to the best of our knowledge, no such modification to the fixed-base comb method, which is also referred to as Lim-Lee method [START_REF] Lim | More flexible exponentiation with precomputation[END_REF], has been proposed until now. This algorithm achieves very high speed at the cost of precomputations and increased memory usage due to lookup tables.

Contribution

In this paper, we are going to introduce an improvement of the fixed-base comb method on Koblitz curves. In this context, we show how point doublings can be traded for applications of the Frobenius endomorphism. To do so, we use scalar recoding to obtain an unsigned τ -adic representation of scalars, which allows us to exchange the doubling steps within the comb methods for the application of the Frobenius endomorphism. We detail the scalar recoding algorithm and describe the modified fixed-base comb method. Furthermore, we have implemented this method as well as the WTNAF method in software. We give a detailed performance comparison and illustrate the performance gains we have achieved with respect to the WTNAF and the conventional fixed-base comb methods. In the former case, we achieve performance improvements of up to 25% and in the latter case improvements of up to 42%.

Outline

In Section 2, we are going to talk about elliptic curves in general, binary Koblitz curves and the fixed-base comb multiplication methods. Section 3 discusses the improvements we have achieved and Section 4 details the implementation, presents the benchmark results and compares the findings to the conventional comb multiplier variants. At last, Section 5 concludes the paper.

Preliminaries

An elliptic curve over a field K is a plane, smooth curve described by the Weierstrass equation:

E : Y 2 + a 1 XY + a 3 Y = X 3 + a 2 X 2 + a 4 X + a 6 , (1)
where a 1 , a 2 , a 3 , a 4 , a 6 ∈ K. The set E(K) of points (x, y) ∈ K 2 satisfying Equation (1) plus the point at infinity O = (0 : 1 : 0), which is the neutral element, forms an additive Abelian group. The addition of points on an elliptic curve is achieved using the chord-and-tangent method [START_REF] Silverman | The Arithmetic of Elliptic Curves[END_REF].

For cryptographic purposes, one is interested in elliptic curves over finite fields F q , especially in curves over fields F 2 m with m being prime and F p with p being a large prime number. The security of elliptic curve cryptography is based on the assumption that in general there is no subexponential-time algorithm to solve the discrete logarithm problem in elliptic curve groups (ECDLP). Given P, Q ∈ E(F q ) with P being a generator of a subgroup of E(F q ) of large prime order n, the ECDLP constitutes the problem of finding a scalar k ∈ Z n such that Q = k • P . In the following, we use E(F q )[n] to denote this n-order subgroup of E(F q ).

In cryptography, we usually use non-supersingular curves, as supersingular curves turned out to be susceptible to the MOV attack [START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF], which reduces the ECDLP to the DLP on finite fields for which an efficient subexponential-time algorithm is known. Non-supersingular curves defined over F 2 m , are described using the following short form of Equation (1):

Y 2 + XY = X 3 + a 2 X 2 + a 6 , (2)
where a 2 , a 6 ∈ F 2 m and a 6 = 0.

The most important and at the same time most expensive operation on elliptic curves is the scalar multiplication, that is, computing k • P from some point P ∈ E(F q ) and some scalar k ∈ Z n . For this purpose, many different algorithms for different goals, such as small or even constant memory footprint, high speed or side-channel resistance, have been invented.

Basic algorithms for scalar multiplication are the double-and-add and the NAF method. In the former case, one is given an unsigned binary representation of the scalar and per bit of the scalar a doubling is performed, where for bits set to 1 an additional point addition is carried out. In the latter, the unsigned scalar representation is replaced by a signed representation, i.e., bits can now take values in {0, ±1}, where for negative bit values point subtractions instead of additions have to be performed. This way, the Hamming weight of the scalar can be reduced to 1/3, which gives a major speedup by reducing the number of additions. Further speed-ups can be achieved by reducing the number of additions, which is done by the windowed-NAF (WNAF) method at the expense of some precomputations (cf. [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF][START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF]).

Subsequently, we are dealing with so-called fixed-base comb multipliers, which are very fast methods for multiplications with some fixed-point P (mostly a fixed generator of E(F q )[n]), and with scalar multiplications on Koblitz curves, for which enormous speed improvements exist already.

Fixed-Base Comb Multiplication

The fixed-base comb multiplier is due to Lim and Lee [START_REF] Lim | More flexible exponentiation with precomputation[END_REF] and is one of the fastest scalar multiplication methods available. As it requires intense precomputations, it is only used for multiplications with a fixed point, which is in most cases a generator of an elliptic curve (sub-)group.

In the fixed-base comb method, the bit representation of a scalar k of maximum bitsize t (where t is the curve's group order in bits) is prepended with 0s, such that the length of k is a multiple of the window size w and then split into w blocks K i with 0 ≤ i < w of size d = t/w , so that

k = K w-1 • • • K 1 K 0 .
Each bitstring K i represents one row of a binary matrix with w rows and d columns:

        K 0 . . . K i . . . K w-1         =         K 0,d-1 • • • K 0,0 . . . . . . K i,d-1 • • • K i,0 . . . . . . K w-1,d-1 • • • K w-1,0         =         k d-1 • • • k 0 . . . . . . k (i+1)d-1 • • • k id . . . . . . k wd-1 • • • k (w-1)d         (3)
Here, K j,i denotes the i-th bit of the bitstring K j and k i denotes the i-th bit of the unsigned binary representation of the scalar k. The columns of this matrix are then processed one at a time. By precomputing the points

[a w-1 , . . . , a 2 , a 1 , a 0 ] 2 P = a w-1 2 (w-1)d P + • • • + a 2 2 2d P + a 1 2 d P + a 0 P,
for all possible bitstrings (a w-1 , . . . , a 1 , a 0 ) the actual computation can be accelerated. This method is summarized in Algorithm 1. The Multiply step of

Q = O. 3: for i = d -1 downto 0 do 4: Q = 2Q 5: Q = Q + [Kw-1,i, . . . , K1,i, K0,i]2P = Q + T w-1 j=0 K j,i 2 j
6: end for 7: return Q Algorithm 1 has an expected running time of

2 w -1 2 w d -1 A + (d -1)D, (4)
where A and D stand for the costs of a (mixed) point addition and a point doubling, respectively. Inside the main loop, the fixed-base comb method has the same number of point additions and point doublings. To reduce the number of point doublings by half, the so-called fixed-base comb method with two tables has been introduced, which makes use of an additional table of the same size as the first table. This method gives a benefit over the conventional comb method whenever w is chosen such that

2 w-1 (w -2) 2 w -w -1 ≥ A D , (5)
For instance, in case of López-Dahab coordinates, w ≥ 6 must hold for the two-table comb method to be faster than the comb method, since A/D ≈ 2 [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF].

Koblitz Curves

Binary Koblitz curves are defined by Equation ( 2), where the curve equation is defined over F 2 , that is a 2 ∈ {0, 1} and a 6 = 1. The group of these curves is defined over F 2 m with m prime. For cryptographic purposes, E(F 2 m ) is required to have almost prime group order, meaning that E(F 2 m ) = hn, where n is a large prime and the cofactor h ≤ 4. On Koblitz curves, the map τ : E(F 2 m ) → E(F 2 m ) with:

P → (x 2 , y 2 ) if P = (x, y), and
O if P = O,
is an endomorphism, which is called Frobenius endomorphism. It can be used to achieve tremendous speedups for scalar multiplications on this curve type. Note that all of the remaining techniques in this section are being discussed in detail by Solinas [START_REF] Solinas | Efficient arithmetic on Koblitz curves[END_REF]. The characteristic polynomial of τ is τ 2 -µτ + 2 with µ = (-1) 1-a2 . Thus, the relation 2P = µτ (P ) -τ 2 (P ) holds for all P ∈ E(F 2 m ). Since squaring is inexpensive in binary fields, the costs of applying τ are insignificant compared to other operations, such as point doubling, which suggests trading point doublings for applications of τ within multiplications by some scalar k. This way, one can trade 3M + 5S required for a doubling on Koblitz curves in López-Dahab coordinates ( [START_REF] Lange | A note on López-Dahab coordinates[END_REF][START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF][START_REF] Higuchi | A fast addition algorithm for elliptic curve arithmetic in GF(2 n ) using projective coordinates[END_REF]) for 3S required for one evaluation of τ , where M stands for the costs of one multiplication and S for the costs of one squaring. However, to be able to do so, k needs to be converted to a value k = l-1 i=0 u i τ i ∈ Z[τ ], which is said to be in τ -adic representation.

The τ -adic Representation: Now, in order to convert scalars from base 2 to base τ , we need to introduce the norm function on Z[τ ]. The norm of an element α = a 0 + a 1 τ ∈ Z[τ ] (note that every element of Z[τ ] can be written this way) is the integer product of α and its complex conjugate ᾱ = a 0 + a 1 τ ∈ Z[τ ], i.e., N :

Z[τ ] → Z with N (a 0 + a 1 τ ) = a 2 0 + µa 0 a 1 + 2a 2 1 .
The ring Z[τ ] is Euclidean with respect to N (•), i.e., it is possible to perform division with remainder in Z[τ ] so that the norm of the remainder is smaller than the norm of the divisor. In particular, an element α = a 0 + a 1 τ ∈ Z[τ ] is divisible by τ if and only if a 0 is even. If so, then α/τ = (a 1 + µa 0 /2) -(a 0 /2)τ . Note that this also enables us to repeatedly divide k ∈ Z by τ , which is necessary to derive the τ -adic representation k = l-1 i=0 u i τ i of a scalar k. As N (τ ) = 2, the remainder in the i-th division u i is either an element of {0, ±1} in case of signed representations or an element of {0, 1} in case of unsigned representations.

So far, there is, however, one problem with this representation, namely, the length of the resulting τ -adic representation is twice the length of the corresponding base 2 representation. In case of the NAF, this means that replacing NAF(k) by the τ -adic NAF (also known as TNAF) will eliminate one doubling for two applications of τ , but will double the number of additions in the scalar multiplication method. To overcome this problem, Solinas introduced the reduced τ -adic NAF in [START_REF] Solinas | Efficient arithmetic on Koblitz curves[END_REF], leading to a τ -adic NAF representation half the length of the original representation and, therefore, of roughly the size of an ordinary NAF representation. Here, an element ρ ∈ Z[τ ] of smallest possible norm so that ρ ≡ k mod δ with δ = τ m -1 τ -1 is computed. Then, for all points P ∈ E(F 2 m )[n] it holds that kP = ρP . From the resulting value ρ, the TNAF representation TNAF(ρ) is derived, where the length of TNAF(ρ) is bounded by m + a 2 .

In practice, often a partial reduction (cf. [START_REF] Solinas | Efficient arithmetic on Koblitz curves[END_REF]) is being performed in order to avoid multiprecision integer divisions. Here, one computes an element ρ ∈ Z[τ ] that is congruent to k modulo δ, but does not necessarily have the smallest possible norm. After the partial reduction, the length of TNAF(ρ ) is bounded by m + a 2 + 3 and is, in general, the same as the length of TNAF(ρ).

The Windowed τ -adic NAF Method: The windowed τ -adic NAF or WT-NAF method is the τ -adic analogue of the ordinary width-w NAF (WNAF). The goal of this method, is to replace doublings by evaluations of the map τ and at the same time to reduce the number of additions through windowing. We do not discuss this method in detail here, but refer the reader to [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF][START_REF] Solinas | Efficient arithmetic on Koblitz curves[END_REF].

As with the WNAF, a representation of the scalar, having at most one nonzero coefficient among w consecutive coefficients, is derived. Like before, a scalar k ∈ Z is (partially) reduced modulo δ = τ m -1 τ -1 , and thereby an element ρ ∈ Z[τ ] is obtained. For w > 1, ρ can be expressed in the form ρ = l-1 i=0 u i τ i where u l-1 = 0 and u i ∈ {0} ∪ {±α u : α u ∈ π} with π = {α u ≡ u mod τ w : u = 1, 3, . . . , 2 w-1 -1}. Thus, the number of additions in the multiplication step is reduced in favor of the precomputation of the points α u P for α u ∈ π. As in case of the fixed-base comb methods, these points can be computed beforehand for points known a priori, such as generators. In this case, the WTNAF method has the following expected costs:

l w + 1 A + lT, (6)
where T denotes the cost of one evaluation of τ .

Fixed-base Comb Method on Koblitz Curves

We now show how the fixed-base comb multiplier can be modified to take advantage of the Frobenius endomorphism on Koblitz curves, i.e., how in this context doublings can be traded for evaluations of the map τ . Subsequently, we refer to this method as fixed-base τ -comb method. Both the precomputation and multiplication step benefit tremendously from this measure. See Section 4 for more details on the achieved performance improvements.

In order to combine the advantages of Koblitz curves with the fast fixedbased comb method, the scalar representation has to be modified. Obviously, it is necessary to obtain an unsigned τ -adic representation of scalar k, that is k = l-1 i=0 u i τ i , with u i ∈ {0, 1}. This representation can be obtained with a small modification to the TNAF algorithm specified by Solinas in [START_REF] Solinas | Efficient arithmetic on Koblitz curves[END_REF], which is summarized in Algorithm 2, where we only allow u i to be 1 in Step 4. As with TNAF, the size of this representation is approximately twice the size of the ordinary binary representation. This is why we need to perform a reduction by δ = τ m -1 τ -1 beforehand, in order to reduce the size of the resulting representation. As we have obtained an unsigned τ -adic scalar representation, the doublings in Algorithm 2 Computing the unsigned τ -adic representation

Input: κ = r0 + r1τ ∈ Z[τ ] Output: κ represented as bitstring u = (ut-1, . . . , u1, u0)τ . 1: i = 0 2: while (r0 = 0 ∨ r1 = 0) do 3: if r0 ≡ 1 mod 2 then 4: ui = 1, r0 = r0 -1 5: else 6: ui = 0 7: end if 8: tmp = r0, r0 = µr0, r0 = r1 + r0/2, r1 = -tmp/2 9:
i = i + 1 10: end while 11: return (ui-1, ui-2, . . . , u1, u0) the precomputation need to be replaced by evaluations of τ , i.e., [a w-1 , . . . , a 2 , a 1 , a 0 ] τ P = a w-1 τ (w-1)d (P ) + • • • + a 2 τ 2d (P ) + a 1 τ d (P ) + a 0 P.

Algorithm 3 shows the fixed-base τ -comb multiplier, where doublings are replaced by evaluations of the Frobenius endomorphism τ .

We note that due to the small costs for τ , the right hand-side of Equation ( 5) gets large, and, thus, the two-table τ -comb method does not give an advantage over Algorithm 3 for window sizes used in practice.

Algorithm 3 Fixed-base comb method on Koblitz curves

Precompute: Input: Window width w, d = t/w , P ∈ E(Fq). Output: Table T holding [aw-1, . . . , a0]τ P for all length w bitstrings (aw-1, . . . , a0).

Multiply:

Input: Window width w, d = t/w , k = (kt-1, . . . , k1, k0)τ , lookup table T generated via Precompute with respect to P ∈ E(Fq). Output: kP .

1: If necessary, pad k on the left with 0s, interpret k as Kw-1 • • • K1 K0, where each Kj is a length d bitstring, where Kj,i denotes the i-th bit of Kj.

2: Q = O. 3: for i = d -1 downto 0 do 4: Q = τ Q 5: Q = Q + [Kw-1,i, . . . , K1,i, K0,i]τ P = Q + T w-1 j=0 K j,i 2 j
6: end for 7: return Q

Implementation Results

In this section, we are detailing the implementation of the τ -comb multiplication algorithm and contrast its performance to the reference implementations of the WTNAF method and the conventional comb method.

Implementation Details

We have implemented the NIST-recommended elliptic curves K-163, K-233, K-283, K-409 and K-571 [START_REF] Gallagher | FIPS PUB 186-3 federal information processing standards publication digital signature standard[END_REF] in Java. We are using fast reductions for the underlying binary fields and long-arrays for values thereof, which are in polynomial representation. We perform squarings in linear time complexity using table lookups [START_REF] Schroeppel | Fast key exchange with elliptic curve systems[END_REF] and multiplications using the windowed left-to-right comb multiplier, which works with precomputed multiplication lookup tables and is also due to Lim and Lee (cf. [START_REF] López | High-speed software multiplication in F2m[END_REF][START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]). For field multiplications, we use windows of size w = 4 and cache these lookup tables for recurring intermediate values in the addition/doubling formulas. Furthermore, we use partial reductions to derive the unsigned τ -adic representations (see Section 2.2). We use López-Dahab coordinates [START_REF] López | Improved algorithms for elliptic curve arithmetic in GF(2 n )[END_REF] with the fast formulas given by Lange and Doche in [START_REF] Lange | A note on López-Dahab coordinates[END_REF][START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF] as well as Higuchi and Takagi in [START_REF] Higuchi | A fast addition algorithm for elliptic curve arithmetic in GF(2 n ) using projective coordinates[END_REF] and perform mixed additions in all implementations. Using this coordinate type, mixed additions take 8M + 5S, where the multiplication lookup tables for two intermediate values can be used twice, lowering the costs to 6M + 2m + 5S. The evaluation of τ takes 3S and point doublings take 3M + 5S, which are necessary for the conventional comb methods.

Finally, we emphasize that the implementation of the τ -comb method is straight-forward and requires only little effort, which makes it a good alternative to other fixed-base multiplication methods.

Estimated Costs and Timings

Here, we present rough estimates for the scalar multiplication costs of the discussed scalar multiplication algorithms and the corresponding timings of our software implementations. As test platform served an Intel Core i5-2540M running Ubuntu Linux 12.10/amd64 and OpenJDK 7u15/amd64 in server mode.

Table 1 lists the costs of squarings and multiplications with already precomputed lookup tables in relation to the costs of multiplications on the test platform. Thus, on the test platform, we get at most A = 8.2M, D = 3.5M and T = 0.3M per mixed addition, per doubling and per evaluation of τ , respectively.

F 2 163 F 2 233 F 2 283 F 2 409 F 2 571 1S = 0.094M 0.080M 0.077M 0.061M 0.055M 1m = 0.643M 0.717M 0.761M 0.829M 0.939M
Table 1: Costs of squarings in relation to multiplications, where S denotes the cost of one squaring, M the cost of a multiplication and m the cost of a multiplication using cached precomputation tables of window size w = 4.

In the following, we give some rough estimates of point multiplication costs of the WTNAF and the τ -comb method based on the relative costs given in Table 1. So, for instance, on curve K-233 with w = 7 the WTNAF method has expected costs of 284.09M, whereas the τ -comb method has expected costs of 264.36M giving an advantage of 7.46%. For w = 8, the expected runtime of the WTNAF method on K-283 is 314.00M, whereas the τ -comb method requires only 283.72M resulting in a performance gain of 10.67%. For w = 9 and curve K-233, we have 238.45M compared to 201.45M resulting in a speed-up of 18.37% and on curve K-409 with w = 9 we get 400.53M compared to 365.85M giving a speed-up of 9.48%.

Table 2 compares the timings of one fixed-base scalar multiplication of the τ -comb method with the WTNAF method and the conventional comb method. As Table 2 shows, in the former case, we achieve performance improvements of up to 25% and in the latter case improvements of up to 42%.

Conclusions

In this paper we have presented a modification to the fixed-base comb method, which allows us to benefit from speedups available on Koblitz curves, i.e., the possibility of replacing point doublings with applications of the far more efficient Frobenius endomorphism τ . In order to do so, one has to perform scalar recoding from base 2 to an unsigned base τ representation, for which we presented the respective algorithm. We have implemented the findings in Java, which allowed us to draw a detailed performance comparison. The implementation timings showed a speedup of up to 42% for single scalar multiplications over the conventional comb method and of up to 25% over the WTNAF method. Finally, we emphasize that the implementation of the τ -comb method is straight-forward and requires only little effort. All in all, this makes it a good alternative to other fixed-base multiplication methods.

Table 2 :

 2 Comparison of the multiplication timings of the comb, the τ -comb and the WTNAF methods.

Related and Future Work

The authors of [2] showed how τ -adic representations can be optimized using telescopic sums in combination with a single point halving operation giving a speedup of ≈ 12.5% over the conventional TNAF method. Later on, this approach was refined in [3] resulting in about 25% less group operations. In [1], the authors study how the Frobenius endomorphism τ can be efficiently combined with the GLV-method by using powers of τ . This way, they are able to decompose scalars and apply interleaved point multiplication on the decomposed smaller scalars, setting new speed records using a low-level implementation. Implementing the aforementioned approaches and drawing comparisons to the method proposed in this paper are issues for future work.

The authors of [15] proposed a new, fast fixed-base comb method, which combines the Lim-Lee and the Tsaur-Chou method [19]. Future work includes adapting this new fixed-base comb multiplier to work with the Frobenius endomorphism.


Kishan Chand Gupta
email: kishan@isical.ac.in

Indranil Ghosh Ray
email: indranilr@isical.ac.in

On Constructions of MDS Matrices from Companion Matrices for Lightweight Cryptography

Keywords: Diffusion, Companion matrix, MDS matrix, MixColumn operation, minimal polynomial

Maximum distance separable (MDS) matrices have applications not only in coding theory but also are of great importance in the design of block ciphers and hash functions. It is highly nontrivial to find MDS matrices which could be used in lightweight cryptography. In a crypto 2011 paper, Guo et. al. proposed a new MDS matrix Serial(1, 2, 1, 4) 4 over F 2 8 . This representation has a compact hardware implementation of the AES MixColumn operation. No general study of MDS properties of this newly introduced construction of the form Serial(z0, . . . , z d-1 ) d over F2n for arbitrary d and n is available in the literature. In this paper we study some properties of MDS matrices and provide an insight of why Serial(z0, . . . , z d-1 ) d leads to an MDS matrix. For efficient hardware implementation, we aim to restrict the values of zi's in {1, α, α 2 , α + 1}, such that Serial(z0, . . . , z d-1 ) d is MDS for d = 4 and 5, where α is the root of the constructing polynomial of F2n . We also propose more generic constructions of MDS matrices e.g. we construct lightweight 4 × 4 and 5 × 5 MDS matrices over F2n for all n ≥ 4. An algorithm is presented to check if a given matrix is MDS. The algorithm follows from the basic properties of MDS matrix and is easy to implement.

Introduction

Claude Shannon, in his paper "Communication Theory of Secrecy Systems" [START_REF] Shannon | Communication Theory of Secrecy Systems[END_REF], defined confusion and diffusion as two properties, required for the design of block ciphers. In [START_REF] Heys | The Design of Substitution-Permutation Networks Resistant to Differential and Linear Cryptanalysis[END_REF][START_REF] Heys | The Design of Product Ciphers Resistant to Differential and Linear Cryptanalysis[END_REF][START_REF] Heys | Avalanche Characteristics of Substitution-Permutation Encryption Networks[END_REF], Heys and Tavares showed that the replacement of the permutation layer of Substitution Permutation Networks (SPNs) with a diffusive linear transformation improves the avalanche characteristics of the block cipher which increases the cipher's resistance to differential and linear cryptanalysis. Thus the main application of MDS matrix in cryptography is in designing block ciphers and hash functions that provide security against differential and linear cryptanalysis. MDS matrices offer diffusion properties and is one of the vital constituents of modern age ciphers like Advanced Encryption Standard (AES) [START_REF] Daemen | The Design of Rijndael:AES -The Advanced Encryption Standard[END_REF], Twofish [START_REF] Schneier | Twofish: A 128-bit block cipher[END_REF][START_REF] Schneier | The Twofish encryption algorithm[END_REF], SHARK [START_REF] Rijmen | The cipher SHARK[END_REF] and Square [START_REF] Daemen | The block cipher SQUARE[END_REF]. MDS matrices are also used in the design of hash functions. Hash functions like Maelstrom [START_REF] Filho | The Maelstrom-0 Hash Function[END_REF], Grφstl [START_REF] Gauravaram | Grφstl a SHA-3 Candidate[END_REF] and PHOTON family light weight hash functions [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF] use MDS matrices as main part of their diffusion layers.

Nearly all ciphers use predefined MDS matrices for incorporating diffusion property. Although in some ciphers the possibility of random selection of MDS matrices with some constraint is provided [START_REF] Youssef | On the Design of Linear Transformations for Substitution Permutation Encryption Networks[END_REF]. In this context we would like to mention that in papers [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF][START_REF] Gupta | On Constructions of Involutory MDS Matrices[END_REF][START_REF] Junod | Perfect Diffusion Primitives for Block Ciphers Building Efficient MDS Matrices[END_REF][START_REF] Lacan | Systematic MDS erasure codes based on vandermonde matrices[END_REF][START_REF] Sajadieh | On construction of involutory MDS matrices from Vandermonde Matrices in GF (2 q ), Designs, Codes and Cryptography[END_REF][START_REF] Youssef | On the Design of Linear Transformations for Substitution Permutation Encryption Networks[END_REF], new constructions of MDS matrices are provided. In [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF], authors construct lightweight MDS matrices from companion matrices by exhaustive search. In [START_REF] Gupta | On Constructions of Involutory MDS Matrices[END_REF], authors construct new involutory MDS matrices using properties of Cauchy matrices over additive subgroup of F 2 n and have shown its equivalence with Vandermonde matrices based construction under some constraints. In [START_REF] Junod | Perfect Diffusion Primitives for Block Ciphers Building Efficient MDS Matrices[END_REF], authors construct efficient 4 × 4 and 8 × 8 matrices to be used in block ciphers. In [START_REF] Lacan | Systematic MDS erasure codes based on vandermonde matrices[END_REF][START_REF] Sajadieh | On construction of involutory MDS matrices from Vandermonde Matrices in GF (2 q ), Designs, Codes and Cryptography[END_REF], authors constructed involutory MDS matrices using Vandermonde matrices. In [START_REF] Youssef | On the Design of Linear Transformations for Substitution Permutation Encryption Networks[END_REF], authors construct new involutory MDS matrices using properties of Cauchy matrices.

Authors of [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF] defined Serial(z 0 , . . . , z d-1 ), which is the companion matrix of z 0 + z 1 x + z 2 x 2 + . . . + z d-1 x d-1 + x d . Their objective was to find suitable candidates so that Serial(z 0 , . . . , z d-1 ) d is an MDS matrix. In [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF], authors proposed an MDS matrix Serial(1, 2, 1, 4) 4 over F 2 8 for AES MixColumn operation which has compact and improved hardware footprint [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF]. It is to be noted that in Serial(1, 2, 1, 4), z 0 = z 2 = 1, z 1 = 2 = α and z 3 = 4 = α 2 , where α is the root of the irreducible polynomial x 8 + x 4 + x 3 + x + 1. The proper choice of z 0 , z 1 , z 2 and z 3 (preferably of low Hamming weight) improves the hardware implementation of AES MixColumn transformation. It may be noted that Mix-Column operation in [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF] is composed of d (d = 4 for AES) applications of the matrix Serial(z 0 , . . . , z d-1 ) to the input column vector. More formally, let X = (x 0 , . . . , x d-1 ) T be the input column vector of Mix-Column and Y = (y 0 , . . . , y d-1 ) T be the corresponding output. Then we have Y

= A d × X = (A × (A × (A × . . . × (A d times ×X)))) . . .), where A = Serial(z 0 , . . . , z d-1
). So the hardware circuitry will depend on companion matrix A and not on the MDS matrix A d . Note that authors of [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF] used MAGMA [START_REF] Bosma | The Magma Algebra System I: The User Language[END_REF] to test all possible values of z 0 , z 1 , z 2 and z 3 and found Serial(1, 2, 1, 4) to be the right candidate, which raised to the power 4 gives an MDS matrix. Authors of [START_REF] Sajadieh | Recursive Diffusion Layers for Block Ciphers and Hash Functions[END_REF][START_REF] Wu | Recursive Diffusion Layers for (Lightweight) Block Ciphers and Hash Functions[END_REF] proposed new diffusion layers (d × d MDS matrices) based on companion matrices for smaller values of d. In this paper we provide some sufficient conditions for such constructions but our approach is different from [START_REF] Sajadieh | Recursive Diffusion Layers for Block Ciphers and Hash Functions[END_REF][START_REF] Wu | Recursive Diffusion Layers for (Lightweight) Block Ciphers and Hash Functions[END_REF]. We also propose new and more generic constructions of d × d MDS matrices for d = 4 and 5.

For efficient implementation, we aim to restrict the values of z i 's in the set {1, α, α 2 , α + 1}, such that Serial(z 0 , . . . , z d-1 ) d is MDS, where α is the root of the constructing polynomial of F 2 n . It may be noted that multiplication by 1, which is the unit element of F 2 n , is trivial. When α is the root of the constructing polynomial of F 2 n , the multiplication by α can be implemented by a shift by one bit to the left and a conditional XOR with a constant when a carry bit is set (multiplication by α is often denoted as xtime). Multiplication by α + 1 is done by a multiplication by α and one XOR operation. Multiplication by α 2 is done by two successive multiplication by α. We also explore some properties of MDS matrices and based on that we provide an algorithm to check whether the matrix is MDS. This algorithm is easy to implement. We implemented the algorithm and ran it for upto 8 × 8 matrices over F 2 24 .

In general we also study the cases where we restrict the values of z i 's in the set {1, β, β 2 , β + 1} for any non zero β ∈ F 2 n , such that Serial(z 0 , . . . , z d-1 ) d is MDS.

The paper is organized as follows: In Section 2 we provide definitions and preliminaries. In Section 3, we discuss a few relevant properties of MDS matrices and provide an algorithm to check if a given square matrix is MDS. In Section 4 and Subsections therein, we study Serial(z 0 , z 1 , z 2 , z 3 ) 4 . In Appendix F we study few more MDS matrices of the form Serial(z 0 , z 1 , z 2 , z 3 ) 4 . In Appendix G, we study MDS properties of Serial(z 0 , z 1 , z 2 , z 3 , z 4 ) 5 and propose new constructions of 5 × 5 MDS matrices. We conclude the paper in Section 5.

Definition and Preliminaries

Let F 2 = {0, 1} be the finite field with two elements and F 2 n be the finite field with 2 n elements. We will often denote a matrix by ((a i,j )), where a i,j is the (i, j)-th element of the matrix. The Hamming weight of an integer i is the number of non zero coefficients in the binary representation of i and is denoted by H(i). For example H(5) = 2, H(8) = 1.

A cyclotomic coset C s modulo (2 n -1) is defined as [14, page 104]

C s = {s, s • 2, • • • , s • 2 ns-1 }
where n s is the smallest positive integer such that s ≡ s2 ns (mod 2 n -1). Using the notation of [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF], we define Serial(z 0 , . . . , z d-1 ) as follows.

Serial(z0, . . . , z

d-1 ) =        0 1 0 0 . . . 0 0 0 1 0 . . . 0 . . . . . . . . . . . . . . . 0 0 0 0 . . . 1 z0 z1 . . . . . . . . . z d-1       
, where z 0 , z 1 , z 2 , . . . , z d-1 ∈ F 2 n for some n. Note that this matrix is a companion matrix of the polynomial z 0 + z 1 x + z 2 x 2 + . . .

+ z d-1 x d-1 + x d .
We note that,

Serial(z0, . . . , z d-1 ) -1 =       
       . (1)
It is to be noted that like encryption, decryption can also be implemented by repeated use (d times) of Serial(z 0 , . . . , z d-1 ) -1 , and also whenever z 0 = 1, the hardware footprint for decryption is as good as that of encryption circuitry.

Definition 1. Let F be a finite field and p and q be two integers. Let x → M × x be a mapping from F p to F q defined by the q × p matrix M . We say that it is an MDS matrix if the set of all pairs (x, M × x) is an MDS code, i.e. a linear code of dimension p, length p + q and minimal distance q + 1.

An MDS matrix provides diffusion properties that have useful applications in cryptography. The idea comes from coding theory, in particular from maximum distance separable codes (MDS codes). In this context we state two important theorems of Coding Theory.

Theorem 1. [14, page 33] If C is an [n, k, d] code, then n -k ≥ d -1.
Codes with n -k = d -1 are called maximum distance separable codes, or MDS codes for short.

Theorem 2. [14, page 321] An [n, k, d] code C with generator matrix G = [I|A],
where A is a k × (n -k) matrix, is MDS if and only if every square submatrix (formed from any i rows and any i columns, for any i = 1, 2, . . . , min{k, n -k}) of A is nonsingular.

The following fact is another way to characterize an MDS matrix.

Fact: 1 A square matrix A is an MDS matrix if and only if every square submatrices of A are nonsingular.

Fact: 2 All entries of an MDS matrix are non zero.

Few Properties Of MDS Matrices

In this Section we develop some tools for studying Serial(z 0 , z 1 , . . . , z d-1 ) d , z i ∈ F 2 n for d = 4, 5. We also use these tools to provide an algorithm (Algorithm 1) at the end of this Section to check whether a matrix is MDS. It may be noted that from the entries of the inverse of a d × d nonsingular matrix, it can be checked whether all its (d -1) × (d -1) submatrics are nonsingular or not. In this direction we state the following Lemma which will be used in Algorithm 1.

Lemma 1. All entries of inverse of MDS matrix are non zero.

Proof. Let M = ((m i,j )) be a d × d MDS matrix. We know that M -1 = Adj(M)/det(M), where Adj(M) = ((M i,j )) and M i,j is co-factor of m j,i in M which is the determinant of (d -1) × (d -1) submatrix obtained by omitting j'th row and i'th column of M. Since M is an MDS matrix, all its (d -1) × (d -1) submatrices are nonsingular. Thus all M i,j values are non zero.

Corollary 1. Any 2 × 2 matrix over F 2 n is MDS matrix if and only if it is a full rank matrix and all entries of its inverse is non zero.

Proof. Proof is given in the Appendix A.

Fact: 3 It may be noted that if all the entries of the inverse of a d × d nonsingular matrix are non zero, then all its (d -1) × (d -1) submatrics are nonsingular.

Corollary 2. Any 3 × 3 matrix over F 2 n with all non zero entries is an MDS matrix if and only if it is a full rank matrix and all entries of its inverse are non zero.

Proof. Proof is given in the Appendix B.

In the next Proposition we study the necessary and sufficient condition for any 4 × 4 matrix to be MDS. This Proposition will be referred to at many places throughout the paper. Proposition 1. Any 4 × 4 matrix over F 2 n with all entries non zero is an MDS matrix if and only if it is a full rank matrix with the inverse matrix having all entries non zero and all of its 2 × 2 submatrices are full rank.

Proof. Let M = ((m i,j )) be a 4×4 matrix satisfying the conditions of this proposition. Since its inverse matrix has all non zero entries, therefore by Fact 3, all (4-1)×(4-1) i.e. 3×3 submatrices of M are full rank matrices. Also inverse matrices of all 2 × 2 submatrices are full rank. Therefore all square submatrices of ((m i,j )) are full rank. Thus the matrix is MDS. The other direction of the proof is immediate.

We close this Section by providing an algorithm to check if a d × d matrix is MDS. The algorithm directly follows from Lemma 1, Fact 1, Fact 2 and Fact 3. We implemented the algorithm and ran it for up to 8 × 8 matrices over F 2 24 .

One approach of checking if a d × d matrix M is an MDS is to use [I|M ] as a generator matrix and check if the code produced is MDS code. Note, if the underlying field is F 2 n , the number of code words will be 2 nd and finding the minimum weight non zero code word is NP-complete.

For testing if a matrix is MDS, a naive approach may be to check for non singularity of all its square submatrices. The number of computations in this case will be n if (((inv M atrixi,j)) does not exist or any entry of ((inv M atrixi,j)) is zero) : b mds = f alse; 11:

if (b mds = f alse) : break the loop and go to 13; 12:

t ← t -2; 13: Set b mds as output; 2 6 ×352 computations. So the ratio of number of computations required by the naive method with number of computations required by our method is approximately 2. Note that this ratio is independent of n. When n = 20 and d = 8, number of computations by the naive method is 20 2 × 988416 and that by our method is 20 2 × 489728 and the ratio is approximately 2.

MDS Properties of

Serial(z 0 , z 1 , z 2 , z 3 ) 4
In this Section we consider low Hamming weight candidates z 0 , z 1 , z 2 , z 3 ∈ F 2 n for arbitrary n, such that Serial(z 0 , z 1 , z 2 , z 3 ) 4 is MDS. Low Hamming weight coefficients are desirable for better hardware implementation. So we restrict the values of z i 's to 1, α, α 2 , 1+α and also try to maximize the occurrence of 1', where α is the root of constructing polynomial of F 2 n . Now we provide cases (from Lemma 2 to Lemma 7) for which matrices of the form Serial(z 0 , z 1 , z 2 , z 3 ) 4 are non MDS except for one special case of Lemma 6 (see Remark 4). In Subsection 4.1, Subsection 4.2 and Appendix F, we will construct lightweight 4 × 4 MDS matrices and in Appendix G we will construct lightweight 5 × 5 MDS matrices of the form Serial(z 0 , z 1 , z 2 , z 3 , z 4 ) 5 .

Lemma 2. Serial(z 0 , z , z 2 , z 3 ) 4 is never an MDS matrix when any three or all of z 0 , z 1 , z 2 and z 3 are 1.

Proof. Proof is given in Appendix C. Remark 1. If 1 is allowed in any three or more places of z 0 , z 1 , z 2 , and z 3 , then the matrix Serial(z 0 , z 1 , z 2 , z 3 ) 4 is not MDS (from Lemma 2). We next study the possibility of having MDS matrices which are of the form Serial(z 1 , z 2 , z 3 , z 4 ) 4 when any two out of z 0 , z 1 , z 2 , and z 3 are 1 and restrict the other two values to be from the set {α, α 2 , α+1} for efficient implementation. Note that there are 6 such cases. It is easy to check that out of these 6 cases, Serial(z 0 , z 1 , 1, 1) 4 and Serial(z 0 , 1, z 2 , 1) 4 will never be MDS. So we concentrate on remaining four cases, i.e. Serial(1, 1, z 2 , z 3 ) 4 , Serial(1, z 1 , z 2 , 1) 4 , Serial(1, z 1 , 1, z 3 ) 4 and Serial(z 0 , 1, 1, z 3 ) 4 . Lemma 3. Let S = Serial(1, 1, z 2 , z 3 ) and z 2 , z 3 ∈ {α, α 2 } or z 2 , z 3 ∈ {α, α + 1}, which are defined over F 2 n , where α is the root of constructing polynomial of F 2 n . Then S 4 is non MDS matrix. Lemma 4. Let S = Serial(1, z 1 , z 2 , 1) and and z 1 , z 2 ∈ {α, α 2 } or z 1 , z 2 ∈ {α, α + 1}, which are defined over F 2 n , where α is the root of constructing polynomial of F 2 n . Then S 4 is non MDS matrix. Remark 2. Note that Serial(1, 1, z 2 , z 3 ) 4 and Serial(1, z 1 , z 2 , 1) 4 over F 2 n become MDS if elements other than 1 are distinct and are from the set {α + 1, α 2 }, for higher values of n (See in Appendix F). Lemma 5. Let A = Serial(1, α, 1, α 2 ) and A = Serial(1, α 2 , 1, α) which are defined over F 2 n , where 1 ≤ n ≤ 4 and α is the root of constructing polynomial of F 2 n . Then A 4 and A 4 are non MDS matrix.

Proof.

A 4 =     1 α 1 α 2 α 2 α 3 + 1 α 2 + α α 4 + 1 α 4 + 1 α 5 + α 2 + α α 4 + α 3 α 6 + α α 6 + α α 7 + α 4 + α 2 + 1 α 6 + α 5 + α 2 α 8 + α 4     (2)
and

A -4 =     α 4 + α 2 α 4 + α 3 + α α 5 + α 4 + α 2 + 1 α 3 + α 2 α 3 + α 2 α 3 + α 2 α 4 + α 2 + α α 2 + 1 α 2 + 1 α 2 + α α 3 + 1 α α 1 α 2 1     (3)
Note that three irreducible polynomials of degree 4 are x 4 + x + 1, x 4 + x 3 + 1 and

x 4 + x 3 + x 2 + x + 1. It is easy to observe that A 4 [2][1] = 5 + α 2 + α = α(α 4 + α + 1), A 4 [3][2] = α 6 + α 5 + α 2 = α 2 (α 4 + α 3 + 1) and A 4 [3][0] = α 6 + α = α(α 5 + 1) = α(α + 1)(α 4 + α 3 + α 2 + α + 1).
So, when the minimal polynomial of α is x 4 + x + 1 or x 4 + x 3 + 1 or

x 4 + x 3 + x 2 + x + 1, A 4 [2][1] or A 4 [3][2] or A 4 [3]
[0] will be 0 respectively. Thus A 4 is a non MDS matrix for n = 4.

Similarly,

A -4 [0][1] = α 4 + α 3 + α = α(α 3 + α 2 + 1) and A -4 [1][2] = α 4 + α 2 + α = α(α 3 + α + 1)
. So, when the minimal polynomial of α is

x 3 + x 2 + 1 or x 3 + x + 1, A -4 [0][1] or A 4 [1]
[2] will be zero respectively. Thus A 4 is a non MDS matrix for n = 3.

Again

A 4 [1][1] = α 3 + 1 = α(α 2 + α + 1) which is zero when the minimal polynomial of α is x 2 + x + 1. Thus A 4 is a non MDS matrix for n = 2.
Lastly, when n = 1, α is 1, making A = Serial(1, 1, 1, 1) and from Lemma 2, A 4 will be a non MDS matrix.

Similarly it can be proved that A 4 is non MDS matrix.

Remark 3. Serial(1, α, 1, α + 1) 4 , defined over F 2 n , is non MDS for 1 ≤ n ≤ 3.
The proof is similar to Lemma 5. In Proposition 4 of Section 4, we will show that Serial(1, α, 1, α + 1) 4 is MDS for all n ≥ 4. Proof. The proof technique is similar to that used in the proof of Lemma 5.

Lemma 6. Let B = Serial(α, 1, 1, α 2 ) and B = Serial(α 2 ,
So far we have mainly considered the cases for which the constructed matrices are non MDS. Now we consider the cases for which the matrices are MDS.

Lightweight MDS matrix of the

Serial(1, z 1 , 1, z 3 ) 4
In this Subsection, we study the MDS property of the matrices of the form Serial(1, z 1 , 1, z 3 ) 4 . We concentrate on z 1 , z 3 ∈ {α, α 2 , α + 1} for better hardware implementation, where α is the root of constructing polynomial of F 2 n for different n. Here z 0 = 1. Serial(1, z 1 , 1, z 3 ) -1 is as defined in equation 1 with d = 4. So the hardware footprint for decryption is as good as that of encryption circuit in Substitution Permutation Networks (SPNs). In this Subsection we will construct MDS matrices for better hardware footprint by letting z 1 , z 3 ∈ {α, α 2 } or z 1 , z 3 ∈ {α, α + 1} and ignore the case when z 0 , z 3 ∈ {α 2 , α + 1}. Proposition 2. Let A = Serial(1, α, 1, α 2 ) be a 4 × 4 matrix over the finite field F 2 n and α is the root of the constructing polynomial of F 2 n . Then, A 4 is MDS for all n ≥ 5 except when n = 6 and α is the root of

x 6 + x 5 + x 4 + x + 1 = 0. Proof. Proof is given in Appendix E.
Remark 5. It is easy to check that when n = 8 and α is the root of irreducible polynomial x 8 + x 4 + x 3 + x + 1, we get the MDS matrix Serial(1, α, 1, α 2 ) 4 , which is proposed in [START_REF] Guo | The PHOTON Family of Lightweight Hash Functions[END_REF]. Now we study Serial(1, β, 1, β 2 ) 4 for any non zero β ∈ F 2 n in Proposition 3. So far, we restricted β to be the root of the constructing polynomial of F 2 n . It is easy to note that β = γ i for some integer i, where γ is any primitive element in F 2 n . These propositions resembles the earlier propositions of this Subsection and proof techniques are also similar. Proposition 3. Let A = Serial(1, β, 1, β 2 ) be a 4 × 4 matrix over the finite field F 2 n . Also let γ be any primitive element of F 2 n and β = γ i such that i ∈ C s . Then if |C s | ≥ 5 then A 4 is always an MDS matrix except when |C s | = 6 and the minimal polynomial of β is x 6 + x 5 + x 4 + x + 1. Remark 6. Note, Proposition 2 is a particular case of Proposition 3 by taking β = α, where α is the root of the constructing polynomial of F 2 n . In canonical representation of F 2 n , MDS matrix construction from Proposition 2 is more efficient. Now we study Serial(1, β, 1, β + 1) 4 for any non zero β ∈ F 2 n . Proposition 4. Let A = Serial(1, β, 1, β + 1) be a 4 × 4 matrix over the finite field F 2 n . Also let γ be any primitive element of F 2 n and β = γ i such that i ∈ C s . Then if |C s | ≥ 4 then A 4 is always an MDS matrix. 7. Similar to Remark 6, if we take β = α in Proposition 4, where α is the root of the constructing polynomial of F 2 n , we get another efficient MDS matrix Serial(1, α, 1, α + 1) 4 in canonical representation of F 2 n . We observe that if Serial(1, β, 1, β 2 ) 4 is an MDS matrix, then the matrices Serial(1, β, 1, β 2 ) -4 and Serial(1, β 2 , 1, β) 4 are also MDS. We record this in Lemma 8 and Lemma 9

Lemma 8. If Serial(1, β, 1, β 2 ) 4 is an MDS matrix for some β ∈ F 2 n , then so is the matrix Serial(1, β, 1, β 2 ) -4 . Lemma 9. If Serial(1, β, 1, β 2 ) 4 is an MDS matrix for some β ∈ F 2 n , then so is the matrix Serial(1, β 2 , 1, β) 4 .

4.2

Lightweight MDS matrix of the form Serial(z 0 , 1, 1, z 3 ) 4

In the Subsection 4.1, we study the MDS property of the matrices of the form given by Serial(1, z 1 , 1, z 3 ) 4 for z i 's in {α, α 2 , α + 1}, where α is the root of constructing polynomial of F 2 n for arbitrary n. In this Subsection we study matrices of the form Serial(z 0 , 1, 1, z 3 ) 4 over F 2 n for arbitrary n, where z 0 , z 3 ∈ {α, α 2 }. Note that if z 0 , z 3 ∈ {α, α + 1}, then the matrices will be non MDS (see Lemma 7). Also for better hardware footprint we omit the case when z 0 , z 3 ∈ {α 2 , α + 1}. We observe that no MDS matrix exits of the form Serial(α, 1, 1, α 2 ) 4 over F 2 n , where 1 ≤ n ≤ 3. In the next Proposition we consider matrices of the form Serial(β,

B 4 =     α 1 1 α 2 α 3 α 2 + α α 2 + 1 α 4 + 1 α 5 + α α 4 + α 3 + 1 α 4 + α 2 + α + 1 α 6 + 1 α 7 + α α 6 + α 5 + α + 1 α 6 + α 4 + α 3 α 8 + α 4 + α + 1     (4)
also

B -4 = 1 α 4     α 3 + α 2 + α + 1 α 3 + α 2 + 1 α 6 + α α 4 + 1 α 5 + α α 4 + α 3 + α 2 + α α 4 + α 3 + α 2 α 2 + α α 3 + α 2 α 5 + α 2 α 4 + α 3 α 2 α 3 α 3 α 5 α 3     (5)
The list of determinants of all 36, 2 × 2 submatrices of B 4 are α 2 , α, α, α+1, α 3 +1, α 2 +1, α 4 , α 3 +α 2 , α 3 +α, α 3 +α 2 +α,

α 5 + α 2 + 1, α 4 + α 3 + α 2 + 1, α 6 + α 2 , α 5 + α 4 + α, α 5 + α 3 + α 2 + α, α 5 + α 4 + α 3 + α + 1, α 7 + α 4 + α 3 + α 2 + α + 1, α 6 + α 5 + α 4 + α + 1, α 2 , α 4 + α, α 3 + α, α 3 + α 2 + α + 1, α 3 + α 2 + α + 1, α 5 + α, α 4 + α 2 , α 6 + α 3 + α, α 5 + α 4 + α 3 + α, α 5 + α 4 + α 3 + α 2 + α + 1, α 5 + α 4 + α 3 + 1, α 7 + α 2 + α + 1, α 4 + α 2 , α 4 + α 3 + α 2 + α, α 6 + α 2 , 1, α 4 + α 3 , α 4 + 1.
There are three irreducible polynomials with coefficients from F 2 and degree 4, namely x 4 + x + 1, x 4 + x 3 + 1 and x 4 + x 3 + x 2 + x + 1. It is easy to observe that B 4 [START_REF] Daemen | The block cipher SQUARE[END_REF][1] = α 4 + α 3 + 1 and B 4 [START_REF] Daemen | The Design of Rijndael:AES -The Advanced Encryption Standard[END_REF][1] = α 6 + α 5 + α + 1 = (α + 1) 2 (α 4 + α 3 + α 2 + α + 1). Thus, when the minimal polynomial of α is x 4 +x 3 +1 or x 4 +x 3 +x 2 +x+1, B 4 [START_REF] Daemen | The block cipher SQUARE[END_REF][1] or B 4 [START_REF] Daemen | The Design of Rijndael:AES -The Advanced Encryption Standard[END_REF][1] will be 0 respectively. Also note that no polynomial in the above list or in the entries of B 4 or its inverse is a multiple of α 4 + α + 1. Thus B 4 is a non MDS matrix for n = 4 except when the minimal polynomial of α is

x 4 + x + 1, It is easy to observe that B 4 [3][2] = α 6 + α 4 + α 3 = α 3 (α 3 + α + 1) and B 4 [2][2] = α 4 + α 2 + α + 1 = (α + 1)(α 3 + α 2 + 1). So, when the minimal polynomial of α is x 3 + x + 1 or x 3 + x 2 + 1, B 4 [3][2] or B 4 [2][2]
will be zero respectively. Thus B 4 is a non MDS matrix for n = 3.

Again B 4 [2][3] = α 6 + 1 = (α + 1) 2 (α 2 + α + 1) 2 which is zero when the minimal polynomial of α is x 2 + x + 1. Thus B 4 is a non MDS matrix for n = 2.
Lastly, when n = 1, α is 1, making B = Serial(1, 1, 1, 1) and from Lemma 2, B 4 will be non MDS matrix.

Similarly it can be proved that B 4 is non MDS matrix.

E Proof of Proposition 2

Proof. The minimal polynomial of α be of degree n ≥ 5. From equation 2 and equation 3, we get A 4 and A -4 . It is easy to check that

A 4 [2][1] = α 5 + α 2 + α = α(α 4 + α + 1) = 0, A 4 [2][3] = A 4 [3][0] = α 6 + α = α(α + 1)(α 4 + α 3 + α 2 + α + 1) = 0, A 4 [3][2] = α 6 + α 5 + α 2 = α 2 (α 4 + α 3 + 1) = 0, A 4 [3][3] = α 8 + α 4 = α 4 (α + 1) 4 = 0, A -4 [0][2] = α 5 + α 4 + α 2 + 1 = (α + 1)(α 4 + α + 1) = 0.
Out of all polynomials in α that are occurring in the entries of A 4 and its inverse, the above polynomials are of degree more than 5 and rest of the entries are of degree less than 5 except

A 4 [3][2] = α 7 + α 4 + α 2 + 1 = (α + 1)(α 6 + α 5 + α 4 + α + 1). So A 4 [3][2] = 0 if n = 6
and α is the root of x 6 + x 5 + x 4 + x + 1 = 0. Thus all entries of A 4 and its inverse are non zero for n ≥ 5 except when n = 6 and α is root of x 6 + x 5 + x 4 + x + 1 = 0.

It is easy to check that the number of 2 × 2 submatrices of A 4 is 36. Determinants of all these 2 × 2 submatrices of

A 4 are 1, α, 1, α 2 +1, α 2 +α, α 3 +1, α 2 , α 3 +1, α 2 +α, α 4 +α 2 +α, α 4 + α 3 + α 2 , α 5 + α, α 4 + 1, α 5 + α 2 + α, α 4 + α 3 , α 6 + α 4 + α 3 + α 2 + 1, α 6 + α 5 + α 4 + α 2 , α 7 , 1, α 2 + α, α 3 + 1, α 3 + α 2 , α 4 + α 2 , α 4 + α 2 , α 2 + α, α 4 +α 3 +α 2 , α 5 +α, α 5 +α 4 +α 3 +α, α 6 +α 4 +α 2 +1, α 6 +α 2 , α 3 + 1, α 4 + α 2 , α 4 + α 2 , α 5 , α 3 + α, α 6 + α 3 .
It is evident that these polynomials in this list which are of degree less than 5 are non zero. Rest of the polynomials in the list having degree ≥ 5 are α 5 + α, α 5 + α 2 + α, α 6 + α 4 + α 3 + α 2 + 1, α 6 + α 5 + α 4 + α 2 , α 7 , α 5 + α, α 5 + α 4 + α 3 + α, α 6 + α 4 + α 2 + 1, α 6 + α 2 , α 5 , α 6 + α 3 . It is easy to check that these values are all non zero as all can be factored into polynomials of degree less than 5. Thus from Proposition 1, A 4 is an MDS matrix. -Serial(1, 1, α + 1, α 2 ) 4 is MDS for all n ≥ 5 except for the case when n = 5 and the minimal polynomial of α is x 5 + x 3 + 1 or x 5 + x 4 + x 3 + x + 1. -Serial(1, 1, α 2 , α + 1) 4 is MDS for all n ≥ 4 except for the case when n = 5 and the minimal polynomial of α is x 5 + x 2 + 1 or x 5 + x 4 + x 3 + x + 1 or when n = 4 and the minimal polynomial of α is x 4 + x 3 + 1 or x 4 + x + 1.

Serial(1, α 2 , α + 1, 1) 4 is MDS for all n ≥ 5 except for the case when n = 5 and the minimal polynomial of α is x 5 + x 3 + 1 or x 5 + x 4 + x 3 + x + 1. -Serial(1, α + 1, α 2 , 1) 4 is MDS for all n ≥ 4 except for the case when n = 5 and the minimal polynomial of α is x 5 + x 2 + 1 or x 5 + x 4 + x 3 + x + 1 or when n = 4 and the minimal polynomial of α is x 4 + x 3 + 1 or x 4 + x + 1.

G

Lightweight 5×5 MDS matrix of the form Serial(1, z 1 , 1, 1, z 4 ) 5

In this Subsection we study Serial(z 0 , z 1 , z 2 , z 3 , z 4 ) 5 , where the elements z 0 , z 1 , z 2 , z 3 , z 4 ∈ F 2 n . As mentioned in Remark 1, we restrict values of z i 's to 1, α, α 2 , α + 1 and try to maximize the occurrence of 1's in the matrix Serial(z 0 , z 1 , z 2 , z 3 , z 4 ) for better hardware implementation. If 1 is allowed in all four or more places of z 0 , z 1 , z 2 , z 3 and z 4 , the matrix Serial(z 0 , z 1 , z 2 , z 3 , z 4 ) 5 is not MDS (similar to Lemma 2). We next study the possibility of having MDS matrices of the form Serial(z 0 , z 1 , z 2 , z 3 , z 4 ) 5 when any three out of z 0 , z 1 , z 2 , z 3 and z 4 are 1. Note that there are 10 such cases. We have the following propositions similar to Proposition 2. Proposition 6. Let A = Serial(1, α, 1, 1, α 2 ) which is defined over F 2 n , where α is the root of the constructing polynomial of F 2 n . Then A 5 is MDS for all n ≥ 7 except when n = 8 and α is the root of x 8 + x 7 + x 6 + x 4 + x 3 + x 2 + 1 = 0 or n = 7 and α is the root of x 7 + x 3 + x 2 + x + 1 or x 7 +x 6 +x 5 +x 2 +1 or x 7 +x 6 +x 5 +x 4 +1 or x 7 +x 6 +x 5 +x 4 +x 3 +x 2 +1.

Remark 10. Serial(1, α, 1, 1, α 2 ) 5 of Proposition 6 is MDS when n = 6 and minimal polynomial of α is x 6 + x 5 + 1 or x 6 + x 4 + x 3 + x + 1 Proposition 7. Let A = Serial(1, α 2 , 1, 1, α) which is defined over F 2 n , where α is the root of the constructing polynomial of F 2 n . Then A 5 is MDS for all n ≥ 8 except when n = 8 and α is the root of x 8 + x 7 + x 6 + x 4 + x 3 + x 2 + 1 = 0.

Remark 11. We observe that Serial(z 0 , z 1 , z 2 , z 3 , z 4 ) 5 does not give MDS matrices when any three of z 0 , z 1 , z 2 , z 3 and z 4 are set as 1 and rest two are restricted in {α, α 2 , α + 1} except the cases mentioned in Proposition 6 and Proposition 7.

3 .

 3 It is easy to check that the number of computations of our algorithm is n 2 d/2 i=1 d 2i 2 (2i) 3 for d even and n 2 d/2 i=1 d 2i+1 2 (2i + 1) 3 for d odd. For example, when n = 8 and d = 4, number of computations by the naive method is 2 6 × 800. In the same context, our algorithm takes only Algorithm 1 Checking if a d × d matrix ((a i,j ))over F 2 n is an MDS matrix Input n > 1, irreducible polynomial π(x) of degree n, the d × d matrix ((ai,j))over F2n . Output Outputs a boolean variable b mds which is true if ((ai,j)) is an MDS matrix, else is false. 1: b mds = true. 2: Compute inverse of ((ai,j)) in ((bi,j)); If inverse does not exist, set b mds = f alse and goto 13; 3: check if all d 2 entries of ((ai,j)) and ((bi,j)) are non zero. If not, set b mds = f alse; 4: if (d = 3) : Go to 13; 5: t ← d -2; 6: while (t > 1 & b mds = true) do 7:List all d t 2 submatrices of dimension t × t in a list list submatrices;8:for (e = 0 ; e < d t 2 ; e = e + 1) do9:Find inverse of list submatrices[e] in ((inv M atrixi,j)); 10:

F Few More Lightweight 4 × 4

 44 MDS matricesHere we provide few more 4 × 4 MDS matrices which are of the form Serial(1, 1, z 2 , z 3 ) 4 and Serial(1, z 1 , z 2 , 1) 4 .

  The subscript s is the smallest integer in C s and is called the coset leader of C s . Note that n s is the size of the coset C s which will also be denoted by |C s |. When n s = n, we call it a full length coset and when n s < n,

	we call
	it a smaller coset. The set of all coset leaders modulo (2 n -1) is denoted
	by Υ (n). The computations in cosets are performed in Z 2 n -1 , the ring of
	integers modulo (2 n -1). For n = 4 the cyclotomic cosets modulo 2 4 -1 =
	15 are: C 0 = {0}, C 1 = {1, 2, 4, 8}, C 3 = {3, 6, 12, 9}, C 5 = {5, 10}, C 7 =
	{7, 14, 13, 11}. Note |C 5 | = 2, |C 1 | = 4 and Υ (4) = {0, 1, 3, 5, 7}.
	Let β ∈ F p n , p being a prime number. The minimal polynomial [14,
	page 99] over F p of β is the lowest degree monic polynomial, say M (x),
	with coefficients from F p such that M (β) = 0. It is easy to check that the
	minimal polynomial is irreducible [14, page 99]. If f (x) is any polynomial
	over F p such that f (β) = 0, then M (x)|f (x) [14, page 99].

  which are defined over F 2 n , where α is the root of the constructing polynomial of F 2 n . Then A 4 and A 4 are non MDS matrices.

1, 1, α) which are defined over F 2 n , where 1 ≤ n ≤ 4 and α is the root of the constructing polynomial of F 2 n . Then B 4 is non MDS for all n such that 1 ≤ n ≤ 4 except when n = 4 and α is a root of x 4 + x + 1. Also B 4 is non MDS for all n such that 1 ≤ n ≤ 4.

Proof. Proof is given in Appendix D. Remark 4. Note for n = 4, if the Galois field F 2 4 is constructed by x 4 + x + 1 then we can construct an MDS matrix Serial(α, 1, 1, α 2 ) 4 where α is the root of x 4 + x + 1. Lemma 7. Let A = Serial(α, 1, 1, α + 1) and A = Serial(α + 1, 1, 1, α)

  1, 1, β 2 )4 for any non zero β ∈ F 2 n . Proposition 5. Let B = Serial(β, 1, 1, β 2 ) be defined over F 2 n . Also let γ be the primitive element of F 2 n and β = γ i such that i ∈ C s . Then if |C s | ≥ 4 then B 4 is always an MDS matrix except when |C s | = 4 and the minimal polynomial of β is x 4 + x 3 + x 2 + x + 1 or x 4 + x 3 + 1 and also when |C s | = 7 and the minimal polynomial of β is x 7 + x 6 + x 5 + x 4 + 1.Remark 8. Similar to Remark 6, if we take β = α in Proposition 5, where α is the root of the constructing polynomial of F 2 n , we get another efficient MDS matrix Serial(α, 1, 1, α 2 ) 4 in canonical representation of F 2 n . Remark 9. Note if Serial(β, 1, 1, β 2 ) 4 is an MDS matrix, then not necessarily Serial(β, 1, 1, β 2 ) -4 and Serial(β 2 , 1, 1, β)4 are MDS (See Lemma 8 and Lemma 9).

Acknowledgements: We wish to thank Professor Palash Sarkar who motivated the problem. We also wish to thank Subhabrata Samajder, Sumit Kumar Pandey and anonymous reviewers for providing several useful and valuable suggestions.

In this Section we found values z ∈ F 2 n which are of low hamming weight, such that Serial(1, z, 1, z 2 ) 4 and Serial(1, z 2 , 1, z) 4 are MDS matrices for all n ≥ 5 and Serial(z, 1, 1, z 2 ) 4 is MDS matrix for all n ≥ 4. It may be checked that for n = 3 no Serial(z 0 , z 1 , z 2 , z 3 ) 4 is an MDS having two of its entries as one; though for n = 3, many such MDS matrices of the form Serial(z 0 , z 1 , z 2 , z 3 ) 4 exist where exactly one of its entries is one. Take for example Serial(1, α, α 5 , α) 4 , where α is the root of x 3 + x 2 + 1. For n = 2 and 1, no MDS matrix of the form Serial(z 0 , z 1 , z 2 , z 3 ) 4 exists.

Conclusion

In this paper, we developed techniques to test if a given d × d matrix over F 2 n is an MDS matrix. We propose a simple algorithm (Algorithm 1) based on some basic properties of MDS matrix. We run the algorithm for up to n = 24 and d = 8. It might be of interest to explore how further properties related to MDS matrix can be used to develop more efficient algorithm for checking whether a given matrix is MDS.

We developed theories to justify why matrices of the form given by Serial(z 0 , z 1 , z 2 , z 3 ) 4 and Serial(z 0 , z 1 , z 2 , z 3 , z 4 ) 5 over F 2 n are MDS for different values n for low Hamming weight choices of values of z i 's, preferably within the set {1, α, α 2 , α + 1}. This leads to new constructions of 4 × 4 MDS matrices over F 2 n for all n ≥ 4 and and 5 × 5 MDS matrices over F 2 n for all n ≥ 8. We tried to generalize such results for Serial(z 0 , . . . , z d-1 ) so that Serial(z 0 , . . . , z d-1 ) d is d × d MDS matrix for d > 5. In doing so, we tried to explore the properties of a companion matrix and its corresponding characteristic polynomial. We use the property that eigen values of a matrix A (in our case A = Serial(z 0 , . . . , z d-1 )) are precisely the roots of the characteristic polynomial (in our case it is z 0 + z 1 x + z 2 x 2 + . . . + z d-1 x d-1 + x d ); Together with the property that if λ is an eigen value of A, then f (λ) is the eigen value of f (A) (in our case f (x) = x d ) [START_REF] Rao | Linear Algebra, Second Edition[END_REF]. But with this simple technique, finding sufficient conditions seem difficult for arbitrary d. It may be interesting to carry out more research to construct d × d MDS matrix Serial(z 0 , . . . , z d-1 ) k for arbitrary d and k ≥ d.

A

Proof of Corollary 1

Proof. Let ((a i,j )) be a 2 × 2 full rank matrix and let all entries of its inverse be non zero. Let its inverse matrix be

. Since all entries of ((b i,j )) are non zero, all entries of ((a i,j )) are also non zero. So ((a i,j )) is MDS. The other direction of the proof is immediate.

B Proof of Corollary 2

Proof. Let M = ((m i,j )) be a 3 × 3 full rank matrix with all non zero entries, such that its inverse matrix also has got all non zero entries. So, all 2×2 submatrices of M are nonsingular. Note that all 1×1 submatrices, which are nothing but the elements m i,j 's, are also non zero. Thus the matrix is MDS matrix. The other direction of the proof is immediate.

C Proof of Lemma 2

Proof. It is easy to check that,

Since some entries of Serial(1, 1, 1, 1) 4 are zero, so from Fact 2, clearly Serial(1, 1, 1, 1) 4 is not an MDS matrix. Similarly it can be shown that when any three of z 0 , z 1 , z 2 and z 3 are 1, some entries of the matrix Serial(z 0 , z 1 , z 2 , z 3 ) 4 are zero. Hence the result.

D

Proof of Lemma 6