Danilo Gligoroski
email: danilog@item.ntnu.no

Rune Steinsmo Ødegård

Rune Erlend Jensen

Ludovic Perret
email: ludovic.perret@lip6.fr

Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Svein Johan Knapskog
email: knapskog@q2s.ntnu.no

Smile Markovski

MQQ-SIG An Ultra-Fast and Provably CMA Resistant Digital Signature Scheme

Keywords: Public Key Cryptography, Ultra-Fast Public Key Cryptography, Multivariate Quadratic Polynomials, Quasigroup String Transformations, Multivariate Quadratic Quasigroup

We present MQQ-SIG, a signature scheme based on "Multivariate Quadratic Quasigroups". The MQQ-SIG signature scheme has a public key consisting of n 2 quadratic polynomials in n variables where n = 160, 192, 224 or 256. Under the assumption that solving systems of n 2 MQQ's equations in n variables is as hard as solving systems of random quadratic equations, we prove that in the random oracle model our signature scheme is CMA (Chosen-Message Attack) resistant.

From efficiency point of view, the signing and verification processes of MQQ-SIG are three orders of magnitude faster than RSA or ECDSA. Compared with other MQ signing schemes, MQQ-SIG has both advantages and disadvantages. Advantages are that it has more than three times smaller private keys (from 401 to 593 bytes), and the signing process is an order of magnitude faster than other MQ schemes. That makes it very suitable for implementation in smart cards and other embedded systems. However, MQQ-SIG has a big public key (from 125 to 512 Kb) and it is not suitable for systems where the size of the public key has to be small.

Introduction

Multivariate quadratic schemes (MQ schemes) are an active research area since their introduction more than 26 years ago in the papers of Matsumoto and Imai [START_REF] Imai | Algebraic Methods for Constructing Asymmetric Cryptosystems[END_REF][START_REF] Matsumoto | Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption[END_REF]. They have a lot of performance advantages over classical public key schemes based on integer factorization (RSA) and on the discrete logarithm problem in the additive group of points defined by elliptic curves over finite fields (ECC), but they have also one additional advantage: there are no known quantum algorithms that would break MQ schemes faster than generic brute force attacks.

We can say that MQ schemes can be generally divided in five types of schemes that conceptually differ in the construction of the nonlinear quadratic part of the scheme. There is a nice (but a little bit older survey from 2005) [START_REF] Wolf | Taxonomy of public key schemes based on the problem of multivariate quadratic equations[END_REF] that covers the first four classes of multivariate quadratic public key cryptosystems: MIA [START_REF] Imai | Algebraic Methods for Constructing Asymmetric Cryptosystems[END_REF], STS [START_REF] Shamir | Efficient Signature Schemes Based on Birational Permutations[END_REF][START_REF] Moh | A public key system with signature and master key functions[END_REF][START_REF] Goubin | Cryptanalysis of the TTM Cryptosystem[END_REF], HFE [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms[END_REF] and UOV [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF].

The fifth scheme MQQ was introduced in [START_REF] Gligoroski | Public key block cipher based on multivariate quadratic quasigroups[END_REF][START_REF] Gligoroski | Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups[END_REF] in 2008. MQQ is based on the theory of quasigroups and quasigroup string transformations. Since it had interesting performance characteristics, it immediately attracted the attention of cryptographers trying to attack it. It was first successfully cryptanalysed independently by Perret [START_REF] Perret | Personal e-mail communication with Danilo Gligoroski[END_REF] using Gröbner basis approach, and Mohamed et al. using MutantXL [START_REF] Mohamed | Algebraic Attack on the MQQ Public Key Cryptosystem[END_REF]. Later, improved cryptanalysis by Faugère et al. in [START_REF] Faugère | Analysis of the MQQ Public Key Cryptosystem[END_REF] explained exactly why the MQQ systems are so easy to solve in practice.

In this paper we describe a digital signature variant of MQQ (called MQQ-SIG). To thwart previous successful attacks, we propose to use the minus modifier, i.e. to remove some equations of the public key. More specifically, we remove 1 2 of the public equations of the original MQQ public key algorithm. We also present numerical (experimental) evidence that gives us arguments to believe that Gröbner bases approach (and having in mind that MutantXL approach is equivalent) is ineffective in solving the remaining known equations.

Thus, based on the assumption that solving n 2 quadratic MQQ's equations with n variables is as hard as solving systems of random quadratic equations, we show that in the random oracle model our signature scheme is provably CMA resistant.

The properties of MQQ-SIG digital signature scheme can be briefly summarized as:

• In the random oracle model it is provably CMA resistant under the assumption that solving n 2 MQQ's quadratic equations with n variables is as hard as solving systems of random equations;

• Its conjectured security level is at least 2 n 2 ;

• The length of the signature is 2n bits where (n = 160, 192, 224 or 256); • The size of the private key is between 401 and 593 bytes.

• The size of the public key is between 125 and 512 Kb.

• In software, its signing speed is in the range of 300-3,500 times faster than the most popular public key schemes, and 5 to 20 times faster than other multivariate quadratic schemes with equivalent security parameters; • Its verification speed is comparable to the speed of other multivariate quadratic PKCs;

• In hardware, its signing or verification speed can be more than 10,000 times faster than the most popular public key schemes; • In 8-bit MCUs, smart cards and RFIDs, it is hundreds or thousands times faster than the most popular public key signature schemes;

2 Preliminaries -Quasigroups and Multivariate Quadratic Quasigroups

Here we give a brief overview of quasigroups and quasigroup string transformations. A more detailed explanation can be found in [START_REF] Belousov | Osnovi teorii kvazigrup i lup[END_REF][START_REF] Denes | Latin squares and their applications[END_REF][START_REF] Smith | An introduction to quasigroups and their representations[END_REF].

Definition 1. A quasigroup (Q, * ) is a groupoid satisfying the law

(∀u, v ∈ Q)(∃!x, y ∈ Q) u * x = v & y * u = v. ( 1
)
This implies the cancelation laws

x * y = x * z =⇒ y = z, y * x = z * x =⇒ y = z.
Note also that the equations a * x = b, y * a = b have unique solutions x, y for each a, b ∈ Q. Given a quasigroup (Q, * ) five so called "parastrophes" (or "conjugate operations") can be adjoint to * . Here, we use only two of themdenoted by \ and /, -defined by

x * y = z ⇐⇒ y = x \ z ⇐⇒ x = z/y (2)
Then (Q, \) and (Q, /) are quasigroups too and the algebra (Q, * , \, /) satisfies the identities

x \ (x * y) = y, (x * y)/y = x, x * (x \ y) = y, (x/y) * y = x (3)
Conversely, if an algebra (Q, * , \, /) with three binary operations satisfies the identities (3), then (Q, * ), (Q, \), (Q, /) are quasigroups and (2) holds.

In what follows we will work with finite quasigroups of order 2 d i.e. where |Q| = 2 d . To define a multivariate quadratic PKC for our purpose, we will use the following result. (

) 4
Recall that each k-ary Boolean function f (x 1 , . . . , x k ) can be represented in a unique way by its algebraic normal form (ANF), i.e., as a sum of products

ANF(f ) = α 0 + k i=1 α i x i + 1≤i<j≤k α i,j x i x j + 1≤i<j<s≤k α i,j,s x i x j x s + . . . ,
where the coefficients α 0 , α i , α i,j , . . . are in the set {0, 1} and the addition and multiplication are in the field GF [START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF].

The ANFs of the functions f i defined in Lemma 1 give us information about the complexity of the quasigroup (Q, * ) via the degrees of the Boolean functions f i . In general, for a randomly generated quasigroup of order 2 d , d ≥ 4, the degrees are higher than 2. Such quasigroups are not quadratic and thus are not suitable for our construction of multivariate quadratic PKC.

Definition 2. A quasigroup (Q, * ) of order 2 d is called Multivariate Quadratic Quasigroup (MQQ) of type Quad d-k Lin k if exactly d -k of
the polynomials f i are of degree 2 (i.e., are quadratic) and k of them are of degree 1 (i.e., are linear), where 0 ≤ k < d.

In [START_REF] Gligoroski | Public key block cipher based on multivariate quadratic quasigroups[END_REF][START_REF] Gligoroski | Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups[END_REF] the authors give sufficient conditions a quasigroup to be a MQQ as well as an algorithm for finding MQQs up to the order of 2 5 . That work was later extended in [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] for constructing MQQs of order 2 d for any d. The common characteristic of the MQQs produced by those two methods is that the quasigroups are bilinear. Namely, the equations (4) describing a multivariate quadratic quasigroup (Q, * ) can be expressed in the following form:

A 1 • (y 1 , . . . , y d ) T + b 1 ≡ A 2 • (x 1 , . . . , x d ) T + b 2 (5)
where

A 1 = [f ij ] d×d is a d × d matrix and b 1 = [u i ] d×1 is a d × 1 vector
x * y ≡ B • U(x) • A 2 • y + B • A 1 • x + c (6)
where x = (x 1 , . . . , x d ), y = (y 1 , . . . , y d ), the matrices A 1 , A 2 and B are nonsingular of size d × d in GF (2), the vector c is a random d-dimensional vector with elements in GF (2) and all of them are generated by a uniformly random process. The matrix U(x) is an upper triangular matrix with all diagonal elements equal to 1, and the elements above the main diagonal are linear expressions of the variables of x = (x 1 , . . . , x d ). It is computed by the following expression:

U(x) = I + d-1 i=1 U i • A 1 • x, (7)
where the matrices U i have all elements 0 except the elements in the rows from {1, . . . , i} that are strictly above the main diagonal. Those elements can be either 0 or 1 generated by a uniformly random process. Additionally, we require the quasigroups to satisfy the following two conditions:

∀i ∈ {1, . . . , d}, Rank(B fi ) ≥ 2d -4, (8a) ∃j ∈ {1, . . . , d}, Rank(B fj ) = 2d -2 ( 8 b )
where the matrices B fi are 2d×2d Boolean matrices defined from the expressions

f i as B fi = [b j,k ], b j,d+k = b d+k,j = 1, iff x j y k is a term in f i . ( 9
)
The reasons why we need the additional conditions (8a) and (8b) will be explained in the beginning of the Section 5.

Proposition 1. For d = 8, a multivariate quadratic quasigroup that satisfies the conditions (6), . . . , [START_REF] Bouillaguet | Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial with One Secret Problem[END_REF] can be encoded in a unique way with 81 bytes.

3 Description of the MQQ-SIG Digital Signature Scheme

Our scheme can be expressed as a ( 12 ) truncation of a typical multivariate quadratic system:

S • P • S : {0, 1} n → {0, 1} n ,
where S = S • x + v (i.e. S is a bijective affine transformation), S is a nonsingular linear transformation, and P : {0, 1} n → {0, 1} n is a central bijective multivariate quadratic mapping defined in Table 1. It is graphically presented in Fig. 1.

x=(x 1 , x 2 , …, x n ) Input ) ( x x x P ' ' 1
Private: S' S' -1 Hidden part The graphical presentation of the construction of the central mapping P using the quasigroup operation * is shown in Fig. 2, and its inverse P -1 constructed with the parastrophe operations \ and / is shown in Fig. 3.

D ) , , , ( ) , , , ( 2 1
X 1 X 2 X 3 … X n/8 -1 X n/8 * * * * * Y 1 Y 2 Y 3 … Y n/8 -1 Y n/8
Fig. 2. A graphical presentation of the construction of the central bijective multivariate quadratic mapping

P … Y 1 Y 2 Y 3 Y n/8 -1 Y n/8 \ / \ / \ X 1 X 2 X 3 X n/8 -1 X n/8 … \ / \ / \
Fig. 3. A graphical presentation of the construction of the inverse central mapping P -1 with parastrophe operations

The generation of the public and private key is defined in Table 2.

Let us denote by D(y) the composition of inverse operations S -1 , P -1 and S -1 on vector y i.e. D(y) ≡ S -1 (P -1 (S -1 (y))). Also, let us denote by E(x) the mapping of a vector x with the public polynomials P i (x 1 , . . . , x n ) i = 1+ n 2 , . . . , n. Both signing and verification for MQQ-SIG are graphically presented on Fig. 4 while the algorithmic steps for the signing procedure are presented in details in Table 3, and the verification steps in Table 4.

Design Rationale

Nonsingular Boolean Matrices in MQQ-SIG

The nonsingular Boolean matrices that are used in MQQ-SIG are generated in a specific way. In general, we need n 2 bits to store a randomly generated

(σ 0 0 , σ 1 0 , * ). M M Q Q | S MQQ-SIG Verification Hash(M) h= h 0 || h 1 I G E(x 0 ) || E(x 1 ) M Signature 0 || 1 s i g h 0 || h 1 y 1 = r 1 || h 1 y 0 = r 0 || h 0 n i n Compare x 1 =D(y 1 ) x 0 =D(y 0 ) h= h || h Hash(M)
Signature=(x 0 , x 1 ) The idea of reducing the size of the keys in MQ schemes by using circulant matrices has been applied previously in several works [START_REF] Yang | Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems[END_REF][START_REF] Singh | Public key cryptography using permutation ppolynomials over finite fields[END_REF][START_REF] Petzoldt | Cyclicrainbow -a multivariate signature scheme with a partially cyclic public key based on rainbow[END_REF]. Instead of using one circulant matrix, we use two. The rationale why and how we construct the private linear (affine) transformations from them is given in what follows.

g h= h 0 || h 1
In order to compress the private information for the linear and affine transformations we define nonsingular matrices S by the following expression:

S -1 = n 16 i=0 I σ 0 i ⊕ n 16 +3 i=0 I σ 1 i , ( 10
)

Table 3. Digital signing

Signing with a private key (σ 0 0 , σ 1 0 , * ) Input. A document M to be signed.

Output.

A signature sig = (x0, x1).

Compute the pair

h = h0||h1 ← Hash(M),
where Hash() is the standardized hash function.

Here we assume that the output of the hash function is n bits, and that h0 and h1 are n 2 bits long. 2. Set y0 = r0||h0 and y1 = r1||h1, where the values r0 and r1 are n 2 -bit values chosen uniformly at random. where

I σ 0 i , i = {0, 1, 2, . . . , n 16 } and I σ 1 i , i = {0, 1, 2, .
. . , n 16 + 1} are permutation matrices of size n, the operation ⊕ is a "bitwise exclusive or" of the elements in the permutation matrices and permutations σ 0 i and σ 1 i are permutations on n elements. They are defined by the following expressions:

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ σ 0 0 -random permutation on {1, 2, . . . n}, σ 0 i = RotateLef t(σ 0 i-1 , 8), for i = 1, . . . , n 16 , σ 1 0 -random permutation on {1, 2, . . . n}, σ 1 i = RotateLef t(σ 1 i-1 , 8), for i = 1, . . . , n 16 + 1, (11)
We chose the permutations σ 0 0 and σ 1 0 such that the expression [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] gives a non-singular matrix S -1 (and S = (S -1 ) -1 ). From S we will obtain the affine transformation

S (x) = S • x + v, (12)
where the vector v = (v 1 , v 2 , . . . , v n ) is an n-dimensional Boolean vector defined from the values of the permutation σ 1 0 = (s 1 , s 2 , . . . , s n ) by the following expression:

v i = ⎛ ⎝ ⎛ ⎝ s 1+ i-1 8 mod 16 × 16 2 (8-i) mod 8 ⎞ ⎠ + s 65+ i-1 8 2 (8-i) mod 8 ⎞ ⎠ mod 2. ( 13
)
In words: we construct the bits of the vector v by constructing two arrays. The first array is constructed by taking the four least significant bits of the values s 1 , . . . , s n 8 and each of them is shifted by four positions to the left. The second array is just simple extraction of the values s 65 , . . . , s 65+ n 8 . Finally we XOR respectively those two arrays of values in order to produce the vector v of n bits. Although the expression [START_REF] Ding | Invertible Cycles for Ultivariate Uadratic (q) Public Key Cryptography[END_REF] looks complex, it is chosen specifically to be very fast in software and hardware. Proposition 2. The linear transformation S -1 can be encoded in a unique way with 2n bytes.

The reasons why we decided to use two permutations σ 0 0 and σ 1 0 in order to define the matrix S -1 as in [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] are due to the fact that the inverse matrix of any circulant matrix is again circulant [START_REF] Davis | CirculantMatrices[END_REF]. Thus, if we would use a circulant matrix S -1 , its inverse S that is used in the production of the public key would be also circulant. From a cryptographic point of view, we wanted to avoid the circular property of S since its strong regularity. This strong regularity might affect the randomness of the multivariate quadratic expressions in the public key. We have made a tradeoff between the totaly non-circulant matrix S generated completely by a uniformly distributed random process which will cost a lot in terms of space, and the regular circulant matrices, by using two circulant matrices that are combined as it is described in the expression [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF]. The obtained S from S -1 is without the circulant regularity, and still we can store it in just 2n bytes.

To illustrate our technique for producing non-circulant matrices S -1 and S we give the following baby example with n = 16 and where rotations to the left are performed by 2 positions.

Let σ 0 0 = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 6 2 5 15 8 11 12 1 9 14 3 10 7 4 13 and σ 1 0 = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12 5 14 2 6 7 9 0 10 11 8 4 1 15 13 3 . Since this is a baby example, we have to adopt the expression [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] for this smaller value of n. The adopted expression is:

S -1 = 2 i=0 I σ 0 i ⊕ 3 i=0 I σ 1 i and we get S -1 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ and S = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1

1 0 1 1 1 0 1 1 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Note that S is not a circulant matrix.

Choosing the Order and Characteristics of Quasigroups

In the original MQQ proposal [START_REF] Gligoroski | Public key block cipher based on multivariate quadratic quasigroups[END_REF][START_REF] Gligoroski | Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups[END_REF], the authors used several different multivariate quasigroups of order 2 5 . That design decision was mainly done because the authors did not know how to construct MQ quasigroups of bigger order. In the meantime, Chen et al., in [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] and Samardjiska et al., in [START_REF] Samardjiska | Multivariate quasigroups defined by t-functions[END_REF] have found ways how to construct MQQs of arbitrary order 2 d . Thus, we have decided to use quasigroups of order 2 8 . That decision was made in order to match the byte size of 8 bits. This enables efficient implementations of MQQ-SIG even on tiny industrial 8-bit MCUs, as well as on high end systems (PCs or workstations). The left and right parastrophes can be pre-computed each taking 64KBytes. These pre-computed parastrophes can speedup the signing phase at least 10 times, but using pre-computed parastrophes of size 2 d where d > 8 simply becomes too costly.

Without going into details of the different characteristics of MQQs produced by methods described in [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] and [START_REF] Samardjiska | Multivariate quasigroups defined by t-functions[END_REF] we can say that for encoding MQQs as described in [START_REF] Samardjiska | Multivariate quasigroups defined by t-functions[END_REF] we need 256 bytes, while for MQQs from [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] we need just 81 bytes (see Proposition 1). This is due to the fact that MQQs in [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] have bi-linear nature, while MQQs constructed in [START_REF] Samardjiska | Multivariate quasigroups defined by t-functions[END_REF] are based on T-functions and generally are not bi-linear.

We have performed experiments with both types of MQQs and after removing n 2 MQQ's expressions from the public key, we have not observed any security consequences of using the bi-linear MQQs from [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF]. That fact combined with the fact that the knowledge of MQQ is a part of the private key, and that the encoding of MQQs from [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF] needs just 81 bytes (versus 256 bytes for MQQs from [START_REF] Samardjiska | Multivariate quasigroups defined by t-functions[END_REF]), was the decisive argument in favor of MQQs defined in [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF].

In our design we use affine transformation S instead of the linear one S, and we also use a non-zero vector c in the quasigroup construction. The reasons for this is that without S our scheme would have the zeroth vector as a fixed point and the same is true for a quasigroup that has c = 0. We consider that these properties are unnecessary and easily avoidable weaknesses.

Security Analysis of the Algorithm

In this section we will describe all the security analysis we have performed during the design of MQQ-SIG. First we want to emphasize that MQQ-SIG similarly as the original MQQ is still resistant against the well know attacks such as: Patarin's chosen plaintext attack on MIA scheme [START_REF] Patarin | Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt 98[END_REF], the attacks with differential cryptanalysis that were proposed by Fouque, Granboulan and Stern in [START_REF] Fouque | Differential Cryptanalysis for Multivariate Schemes[END_REF], solving the isomorphism of polynomials with one secret done by Perret and others in [START_REF] Perret | A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem[END_REF][START_REF] Faugère | Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects[END_REF][START_REF] Bouillaguet | Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial with One Secret Problem[END_REF] and MinRank attacks. For the resistance against MinRank attacks we want to note that the minimal rank r of the matrices B fi for the nonlinear part of our scheme have to fulfil the conditions (8a, 8b), thus at least one of the ranks is 14 and all of the ranks are at least 12. Additionally, it is not known how to extend the MinRank attack to our scheme, since some equations of the public-key have been removed. In [START_REF] Bettale | Cryptanalysis of Multivariate and Odd-Characteristic HFE Variants[END_REF], it has been proved that the attack can be extended when 1 equation is removed in HFE. However, the attack can not be applied in our context when n 2 equations are removed. We suggest the reader to see [START_REF] Gligoroski | Public key block cipher based on multivariate quadratic quasigroups[END_REF][START_REF] Gligoroski | Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups[END_REF] for the arguments why MQQ-SIG is resistant against these attacks.

Experiments with Gröbner Bases

The public key encryption algorithm MQQ introduced in [START_REF] Gligoroski | Public key block cipher based on multivariate quadratic quasigroups[END_REF][START_REF] Gligoroski | Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups[END_REF] was quickly shown to be weak against algebraic cryptanalysis. It was broken both by Perret [START_REF] Perret | Personal e-mail communication with Danilo Gligoroski[END_REF] using Gröbner basis approach, and by Emam Mohamed et al [START_REF] Mohamed | Algebraic Attack on the MQQ Public Key Cryptosystem[END_REF] using MutantXL. Later Faugère et al [START_REF] Faugère | Analysis of the MQQ Public Key Cryptosystem[END_REF] explained why the MQQ systems are so easy to solve in practice. To understand their results we must first introduce to concept of degree of regularity.

As explained in [START_REF] Faugère | Analysis of the MQQ Public Key Cryptosystem[END_REF], the complexity of computing a Gröbner basis of an ideal depends on the maximum degree of the polynomials appearing during the computation. This degree, called degree of regularity, is the key parameter for understanding the complexity of a Gröbner basis computation [START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]. Indeed, the complexity of the computation is polynomial in the degree of regularity D reg , more precisely the complexity is:

O(n ωDreg ), (14)
which basically correspond to the complexity of reducing a matrix of size ≈ n Dreg .

Here 2 < ω ≤ 3 is the "linear algebra constant", and n the number of variables of the system. Note that D reg is a function of n and also of the number of equations m. The relation between D reg , n and m depends on the specific system of equations. This relation is well understood for regular (and semi-regular) systems of equations [START_REF] Bardet | Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie[END_REF][START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]. However, as soon as the system has some kind of structure, this degree is much more difficult to predict.

In [START_REF] Faugère | Analysis of the MQQ Public Key Cryptosystem[END_REF], the authors showed that the degree of regularity of the original public key algorithm MQQ was bounded from above by a small constant. Having in mind the successful and very efficient way how Gröbner bases and XL methods are solving the full systems of MQQ equations, we want to ensure that MQQ-SIG does not have a similar small bound on the degree of regularity. A classical way to avoid this is to remove some equations of the system. Indeed, an under-defined system of equations (n > m) will have an exponential number of solutions. This is an issue since the complexity of Gröbner bases is also related to the number of solutions [START_REF] Faugère | Efficient computation of zerodimensional Gröbner bases by change of ordering[END_REF]. To circumvent this problem, a solution is to fix nm variables (or more [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]). However, as soon as sufficiently many variables were fixed, we observed that the new system behaved as a "random" system of equations of the same size. This has been also observed and used in the hybrid approach [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF].

To confirm this behavior in our context, we have performed experiments on MQQ-SIG equations systems of reduced sizes. The observed degree of regularity is compared to the expected degree of regularity for a random multivariate system of the same size. The strategy for choosing S has changed during the course of our experiments. The experiments where performed with random Boolean matrices. However, from a security against Gröbner bases attack point of view, the most important feature is that we ensure that the 8 linear expressions are removed from the equations set. Below is our experimental strategy for small-scale version of MQQ-SIG equation systems in n variables: Table 5. The average degree of regularity for a MQQ signature system in V variables with R equations removed. In parentheses, the expected degree of regularity for a random system of size V -R. We have performed 100 experiments for 16, 24,32 and 40 variables. Due to the complexity, the experiments have only been repeated 10 times for 48 variables and just once for 56 and 64 variables. For 56 and 64 variables many of the instances either required more than the 1TB RAM our system has, or did not finish after about 1 month of computation. These instances are marked with a • in the table. We also experienced that 72 variables with 36 equations removed did not finish after about a month of computation. The experiments were done with Magma 2.17-3's implementation [START_REF] Magma | High performance software for algebra, number theory, and geometry -a large commercial software package[END_REF] of the F 4 [START_REF] Faugere | A new efficient algorithm for computing Gröbner basis[END_REF] algorithm on a workstation with 32 cores based on Intel Xeon 2.27GHz, with 1TB of RAM memory. The results of these experiments are listed in Table 5. In the table the expected degree of regularity for a random system of equations over GF (2) in V -R variables are also listed in parentheses. These numbers have been calculated using the formula provided in [START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF]. From the table we see that the bigger percentage of equations we remove from the system, the closer the measured degree of regularity is to a random system of equations. The reason for this is that we are removing crucial relations among terms, thus rendering the remaining sets of equations as random sets of multivariate equations. It is then natural to formulate the following conjecture: Conjecture 1. For every full set of public key equations produced by MQQ as defined in steps 1-3 in Table 2, removing n 2 of the equations, makes the remaining set of n 2 multivariate quadratic equations to act as a set of n 2 random multivariate quadratic equations with n 2 variables in GF (2).

The Size of the Pool of MQQs of Order 2 8

It is very important to address the question of the size of the set of MQQs of order 2 8 that we use in our MQQ-SIG scheme. In [START_REF] Chen | Multivariate quadratic quasigroups (MQQs): Construction, bounds and complexity[END_REF], Chen et al., gave a lower bound on the number of MQQs of order 2 8 . That number is projected to 2 273 . However, we are using additional conditions [START_REF] Bettale | Cryptanalysis of Multivariate and Odd-Characteristic HFE Variants[END_REF]. By a heuristical measuring we have obtained that approximately one in 2 7 randomly generated MQQs of order 2 8 complies with the conditions [START_REF] Bettale | Cryptanalysis of Multivariate and Odd-Characteristic HFE Variants[END_REF]. That means that the lower bound of the size of the pool of MQQs of order 2 8 is 2 266 .

Secret Key Leakage Scenarios

Originally this attack was presented to us by an anonymous reviewer of an earlier variant of our scheme submitted to WCC 2011. We would like to express big acknowledgement to that anonymous reviewer.

In a previous version of our scheme instead of y = r 0 ||h 0 , the value y = h obtained as the output of the hashing procedure is n bits long, and the signature part is x = D(y). The following Chosen Message Attack could then be launched. An attacker asks for signatures of 1+n+ n 2 +O(1) messages i.e. he will have the triplets (M i , x i , y i ≡ Hash(M i )). He will then attempt to recover the missing n 2 equations in the public key. Given the missing equations he can successfully launch an efficient Gröbner bases attack.

Consider the extraction of the first missing equation y 1 = P 1 (x 1 , . . . , x n ), which can be expressed in a general form as:

y1 = d0 +d1x1 +d2x2 +. . .+dnxn +dn+1x1x2 +. . .+d2n+1x2x3 +. . .+d 1+n+( n 2 ) xn-1xn. ( 15
)
Since the attacker knows the values of 1 + n + n 2 + O( 1) triplets (M i , x i , y i ), from the equation [START_REF] Faugère | Efficient computation of zerodimensional Gröbner bases by change of ordering[END_REF], with high probability, he can obtain a full rank linear system of equations with 1 + n + n 2 unknown variables d j . Additionally and most importantly he knows the corresponding values y (i) 1 for every of the values y i = (y

(i) 1 , . . . , y (i)
n ). Thus, by solving the obtained linear system of equations he can recover the values of the coefficients d j i.e. he can recover the first missing equation. The extraction of other hidden equations is similar.

This attack is easily mitigated by our strategy to construct the values y 0 = r 0 ||h 0 and y 1 = r 1 ||h 1 where r 0 and r 1 are strings of n 2 randomly generated bits with every signing invocation, and h = h 0 ||h 1 is the hash output that is digesting the message M .

We formulate the previous discussion about the leakage of the private key in the non-randomized MQQ-SIG and its prevention by the following two lemmas: Lemma 2. For any MQQ signature scheme with K expressions removed, if the signatures for the messages M are obtained as x = D(y), where y = Hash(M ), the extraction of the removed part has complexity of O(Kn 2 ). Lemma 3. For the MQQ-SIG signature scheme as defined in steps 1-3 in Table 2, by removing n 2 of the expressions, an attack for extraction of the removed part as in Lemma 2 has complexity of O(2 n 3 ).

Proof. Since the signature for a message M has two parts x 0 and x 1 that are computed as x 0 = D(r 0 ||h 0 ) and x 1 = D(r 1 ||h 1 ) where h = h 0 ||h 1 = Hash(M ), and the values r 0 and r 1 are n 2 -bit values chosen uniformly at random for every particular procedure of signing, the extraction technique from Lemma 2 can give the correct extraction of the hidden part if and only if for all O(n 2 ) queries, the random values r 0 and r 1 are known to the attacker. Having in mind that for every produced signature the values r 0 and r 1 are unknown, fresh, uniformly distributed random values, the probability of guessing their values is 2

-n 2 × 2 -n 2 = 2 -n . For all O(n 2
) queries this gives us a total probability of (2 -n ) n 2 = 2 -n 3 , i.e. the complexity for extracting the hidden part is O(2 n 3 ).

MQQ-SIG Is Provably CMA Resistant

We will use the following definition of security against chosen message attack [27]: Definition 3. Signature scheme (Gen, Sign, Vrfy) is existentially unforgeable under a chosen-message attack if for all probabilistic, polynomial-time adversaries A, the success probability of A in the following experiment is negligible (as a function of k):

1. The key-generation algorithm Gen (1 k ) is run to obtain a pair of keys (pk, sk) 2. A is given pk and allowed to interact with a signing oracle Sign sk (•), requesting signatures on as many messages as it likes. Let M denote the set of messages queried to the signing oracle by A.

Eventually, A outputs (m, σ)

4. A succeeds if Vrfy pk (m, σ) = 1 and m / ∈ M
It is well known that solving multivariate quadratic polynomials is an NPcomplete problem (see for instance [START_REF] Garey | Computers and Intractability. A guide to the theory of NP-Completeness[END_REF]). This theorem is repeated below.

Theorem 1 ([20]

). Let P i (x 1 , . . . , x n ), 1 ≤ i ≤ m be a collection of polynomials over GF [START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF]. In what follows we give a sketch of the proof and the ideas how to use the fact that the verification of the MQQ-SIG signatures depends on the values h 0 and h 1 that are each n 2 bits long. This fact implies that a chosen message attack on MQQ-SIG would need either at least 2 n to find a collision of the used hash function or to solve the system of n 2 random multivariate quadratic equations with n variables. A formal proof showing the strict reduction from the CMA-resistance of the scheme to the assumption that solving n 2 MQQ equations with n variables is as hard as solving systems of n 2 random multivariate quadratic equations with n variables will be given in the extended version of this paper.

Proof. (sketch) The security parameter input to the generating algorithm is k = n 2 , which controls the number of equations over GF [START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF] and is directly connected with the value n: the output size of the hash function.

Given the assumption that solving n 2 MQQ equations with n variables is as hard as solving systems of n 2 random multivariate quadratic equations, there are no structural weaknesses of the MQQ equations that can be exploited to solve the system faster then solving n 2 random multivariate quadratic equations. This means the adversary has basically three strategies of breaking MQQ-SIG:

1. To find a collision in the hash digest (h 0 ||h 1 ) of length n = 2k. 2. To solve two systems of n 2 MQ equations with n Boolean variables. 3. Some combination of the two above.

Strategy 1: Breaking with the strategy 1 means finding a collision for a random oracle with a n = 2k bit output. Interacting with the signing oracle will not help the adversary for this instance, since he is only interested in the output of the random oracle. By the generic birthday attack the adversary needs O(2 k ) queries to the random oracle to find a collision for the whole digest. The probability for a polynomial time adversary to break the signature scheme by finding a collision in the digest is therefore negligible in k.

Strategy 2:Under the assumption that solving the n 2 MQQ equations in n variables is as hard as solving k MQ equations in k variables, we know by Theorem 1 that the probability the adversary solves either of the equations with the strategy 2 is negligible in k. However, to prove that the signature scheme is CMA, we must also show that querying the signing oracle gives the adversary no significant advantage in solving the equations. There are two ways the signing oracle might leak information.

(a) Signing leaks information about the hidden equations:

In Lemma 3 we proved that extracting information about the removed part has complexity O(2 n 3 ). With our security parameter of k = n 2 this is out of reach for a polynomially bound adversary. (b) Signing leaks some other information that can help solve the equation system: Consider the following game where the adversary does not have access to the random oracle. The adversary asks for a signature for a chosen message M . The signing oracle then flips a coin. I If the coin land on heads the signing oracle outputs the digest H(M ) = (h 0 ||h 1 ), and the corresponding signature (x 0 , x 1 ).

II If the coin lands on tails the signing oracle outputs the evaluation of the encryption function in some random numbers (E(r 0 ), E(r 1 )), and the corresponding random numbers (r 0 , r 1 ). The adversary is then asked if the coin is heads or tails.

Since by the definition of random oracles the output of H(M ) is independent of M , it should be clear that the adversary has no way of winning the game above. This illustrates that from the adversary point of view, there is no difference between querying the signing oracle and evaluating the known equations on random inputs. The fact that the adversary actually has access to the random oracle does not change this conclusion because the adversary has no control over the output of the random oracle.

To summarize this means that signing reveals no information about the hidden equations, and leaks no other information that can be used to solve the equations. The signature scheme is therefore CMA with respect to the strategy number 2.

Strategy 3: First note that finding a kl, 1 ≤ l ≤ k, bit collision in, for instance h 0 , will not help computing the corresponding x 0 . The reason for this is the nature of the random MQ equations, where the solution to the system will drastically change by just flipping one output bit. Namely, each output bit depends on average on k(k-1) 2 combination of all pairs of variables. This means that the best for the adversary in strategy attack number 3 is to find a collision in either h 0 or h 1 , and to solve the equation system for the part that a solution is not known. This requires "just" O(2 k 2 -1 ) calls to the random oracle. However, the adversary still needs to solve a system of k equations in 2k variables, proven to be CMA resistant by the arguments under the attack strategy number 2.

Non-applicability of Successful Attacks against STS on MQQ-SIG

An anonymous reviewer for IMACC 2011 (to whom we express big acknowledgement) has pointed out an interesting comment that MQQ-SIG scheme looks similar as STS schemes and thus the successful attacks that have broken STS schemes may also break MQQ-SIG. Here we explain the crucial and essential differences between STS and MQQ-SIG schemes and the non-applicability of successful attacks against STS on MQQ-SIG. The Stepwise Triangular Scheme was introduced by Wolf et al., [START_REF] Wolf | On the security of stepwise triangular systems[END_REF] as a generalization of earlier multivariate quadratic schemes, such as [START_REF] Shamir | Efficient Signature Schemes Based on Birational Permutations[END_REF][START_REF] Moh | A public key system with signature and master key functions[END_REF][START_REF] Goubin | Cryptanalysis of the TTM Cryptosystem[END_REF][START_REF] Kasahara | A construction of public key cryptosystem for realizing ciphertext of size 100 bit and digital signature scheme[END_REF]. The main purpose of the generalization in [START_REF] Wolf | On the security of stepwise triangular systems[END_REF] was to show how all these schemes, and the whole STS family in general, is either insecure or impractical. The general attacks presented exploit the chain of kernels introduced by the triangular structure of the hidden polynomials.

There are at least two important reasons why this attack is not applicable on MQQ-SIG. First, even tough the kernel of two adjacent sub-blocks share half of each others variables, the triangular structure of the hidden polynomials does not result in a chain of kernels. The production of the public key in MQQ-SIG is essentially parallel and chained for the whole n-dimentional space, while the We want to emphasize that recently Samardjiska and Chen in [START_REF] Samardjiska | Construction of multivariate quadratic quasigroups (mqqs) in arbitrary galois fields[END_REF] have proposed extension of their algorithms for construction of MQQs over arbitrary finite fields and that by their construction it is possible to reduce the huge public key size of MQQ-SIG to be in the range 2.3 -8.8 Kbytes.

Performance of the Software Implementation of the MQQ-SIG Algorithm

We have implemented MQQ-SIG in C for the SUPERCOP benchmarking system [START_REF]eBACS: ECRYPT benchmarking of cryptographic systems[END_REF] and tested it together with the corresponding RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] and ECC [START_REF] Miller | Use of Elliptic Curves in Cryptography[END_REF][START_REF] Koblitz | Elliptic Curve Cryptosystems[END_REF] (actually ECDSA) and several other multivariate quadratic systems such as: Rainbow [START_REF] Ding | New Differential-Algebraic Attacks and Reparametrization of Rainbow[END_REF], enhanced TTS [START_REF] Yang | Building Secure Tame-like Multivariate Public-Key Cryptosystems: The New TTS[END_REF] and 3ICP [START_REF] Ding | Invertible Cycles for Ultivariate Uadratic (q) Public Key Cryptography[END_REF]. In Table 6 we give the comparison of the mentioned signatures schemes where the measurements were performed in 64-bit mode of operation on Intel Core i7 920X machine running at 2 GHz. Although, our C code is not yet optimized for the key generation part, we expect that the performance of key generation part to be the most time consuming part of our algorithm.

From the Table 6 it is clear that in signing of 59 bytes MQQ-SIG is faster than RSA in the range from 300 up to 3500 times, and is faster than ECDSA in the range from 140 up to 200 times. If we exclude the time for hashing the messages, signing operations in MQQ-SIG in Table 6 take from 2,500 up to 5,000 cycles. MQQ-SIG is also significantly faster than other multivariate methods such as Rainbow, TTS or 3ICP and that performance advantage in the signing procedure is in the range from 5 to 20 times.

The verification speed in our code is not optimized so far. We expect the optimized verification speed of MQQ-SIG to be in the range of Rainbow, TTS and 3ICP.

Conclusions

We have constructed a multivariate quadratic digital signature scheme MQQ-SIG based on multivariate quadratic quasigroups.

By learning about the weaknesses of the previous attempt to design a multivariate quadratic scheme based on quasigroups -MQQ, by analyzing the successful attacks on all existing MQ schemas, and by our experimentally supported assumption that solving n 2 quadratic polynomials with n variables is as hard as solving random systems of equations, we have designed a digital signature scheme that in the random oracle model is provably CMA resistant and that we believe is strong enough to attract the attention of the cryptographic community.

The efficiency of producing digital signatures of our scheme outperforms all the existing signature schemes (RSA, ECDSA and other MQ schemes) in the range from 5 up to 3,500 times. The speed of verification of our scheme is similar to the other MQ schemes. However the MQQ-SIG scheme that was described in this paper has an unpractically big public key. The ongoing research efforts are in this direction and soon we can expect MQQ-SIG variants with significantly smaller public keys.

We believe that its superior performance will allow an employment of strong and fast authentication protocols based on the paradigm of the public key cryptography in many new areas of our modern society.

Lemma 1 (

 1 [21,22]). For every quasigroup (Q, * ) of order 2 d and for each bijection Q → {0, 1 . . . , 2 d -1} there are a uniquely determined vector valued Boolean functions * vv and d uniquely determined 2d-ary Boolean functions f 1 , f 2 , . . . , f d such that for each a, b, c ∈ Q the operation a * b = c is represented by * vv (x1, . . . , x d , y1, . . . , y d ) = f1(x1, . . . , x d , y1, . . . , y d ), . . . , f d (x1, . . . , x d , y1, . . . , y d ) .

Fig. 1 .

 1 Fig. 1. A graphical presentation of our MQ "minus" scheme

Output. 8 8 where

 88 linear expressions P i (x1, . . . , xn), i = 1, . . . , 8 and n -8 multivariate quadratic polynomials P i (x1, . . . , xn), i = 9, . . . , n 1. Represent a vector x = (f1, . . . , fn) of n linear Boolean functions of n variables x1, . . . , xn, as a string x = X1 . . . X n Xi are vectors of dimension 8; 2. Compute y = Y1 . . . Y n 8 where: Y1 = X1, Yj+1 = Xj * Xj+1, for even j = 2, 4, . . ., and Yj+1 = Xj+1 * Xj , for odd j = 3, 5, . . . 3. Output: y.

1 .

 1 Generate an MQQ * according to equations (6) . . . (9). 2. Generate a nonsingular n × n Boolean matrix S and affine transformation S according to equations (10), . . . , (13). 3. Compute y = S(P (S (x))), where x = (x1, . . . , xn). 4. Output: The public key is y as n 2 multivariate quadratic polynomials Pi(x1, . . . , xn) i = 1 + n 2 , . . . , n, and the private key is the tuple

Fig. 4 .

 4 Fig. 4. A graphical presentation of the signing and verification process with MQQ-SIG

3 .

 3 Compute x0 = D(y0) and x1 = D(y1).

4 .

 4 The MQQ-SIG digital signature of the document M is the pair sig = (x0, x1).

Table 4 .

 4 Digital verificationSignature verification with a public key P = {Pi(x1, . . . , xn) | i = 1 + n 2 , . . . , n} Input. A document M and its signature sig = (x0, x1). Output. TRUE or FALSE. 1. Compute h = h0||h1 = Hash(M), where M is the signed message, and Hash() is the standardized hash function. 2. Compute z0 = E(x0) and z1 = E(x1). 3. If z0 = h0 and z1 = h1 then return TRUE, else return FALSE.

1. Repeat: 2 .

 2 Generate a bijective multivariate quadratic mapping P i (x1, . . . , xn), i = 1 , . . . , n 3. Remove the 8 linear expressions P i (x1, . . . , xn), i = 1, . . . , 8 4. Multiply with random nonsingular Boolean matrices SR and TR, P = SR • P • TR. 5. For j = 8 to j = n 2 do: (a) Remove the last 8j equations from P. (b) Set a random Boolean vector (xn-j+1, . . . , xn) ∈ {0, 1} j (c) Obtain a system P1 = {Pi(x1, . . . , xn-j) | i = 1, . . . , n -j} of nj equations with nj variables (x1, . . . , xn-j ) (d) Call F4(P1) algorithm from Magma, to find a Gröbner basis for the system P1, and measure the degree of regularity. 6. Compute the average degree of regularity.

Table 1 .

 1 Definition of the central bijective multivariate quadratic mapping P : {0, 1} n → {0, 1} n Input. A vector x = (f1, . . . , fn) of n linear Boolean functions of n variables. We implicitly suppose that a multivariate quadratic quasigroup * is previously defined, and that n = 32 × k, with k ∈ {5, 6, 7, 8} already fixed.

	The central Bijective multivariate quadratic map-
	ping P (x)

Table 2 .

 2 Generation of the public and the private keyGeneration of the public and the private key for MQQ-SIG scheme.

	Input. Integer n, where n = 32 × k and k ∈
	{5, 6, 7, 8}.
	Output. A public key P given by n 2 multivari-ate quadratic polynomials Pi(x1, . . . , xn), i = 1 + n 2 , . . . , n, and a private key given by two per-mutations σ 0 0 and σ 1 0 on {1, . . . , n}, and 81 bytes for encoding a quasigroup * .

  The problem of finding u 1 , . . . , u n such that P i (u 1 , . . . , u n ) = 0 for 1 ≤ i ≤ m remains NP-complete even if none of the polynomials has a term involving more than two variables or if there is just one polynomial.

	Theorem 2. MQQ-SIG is CMA resistant in the random oracle model under
	the assumptions that solving n 2 MQQ equations with n variables is as hard as solving systems of n 2 random multivariate quadratic equations.

Acknowledgements. We would like to thank anonymous reviewers of the IN-TRUST 2011 conference for their useful comments that improved the text of the paper. The work described in this paper has been supported by the Commission of the European Communities through the ICT program under contract ICT-2007-216676 (ECRYPT-II). J.-C. Faugère and L. Perret are also supported by the French ANR under the Computer Algebra and Cryptography (CAC) project (ANR-09-JCJCJ-0064-01).

production of the public key in STS is essentially sequential with increasingly larger embedded subspaces. It is this structure that the attacks on STS exploit.

The second reason is that the attacks linearly combine the public key expressions in order to get ranks within certain values. Non-applicability of these attacks against MQQ-SIG is due to the fact that half of the public key expressions are removed, and linearly combining the remaining half in order to obtain low ranks does not necessarily produce vectors from the kernel of the transformation T -1 .

Operating Characteristics

In this section we discuss the sizes of the private and public key as well as the number of operations for verification and signing.

The Size of the Public and the Private Key

Since the public key consists of n 2 randomly generated multivariate quadratic equations, the size of the public key follows the rules given in [START_REF] Wolf | Taxonomy of public key schemes based on the problem of multivariate quadratic equations[END_REF]. So, for n bit blocks the size of the public key is 0.5 × n × (1 + n(n+1)

2

) bits. The private key of our scheme is the tuple (σ 0 0 , σ 1 0 , * ). The corresponding memory size needed for storage of the private key is 2n + 81 bytes.

In Table 6, there are two columns for the size of the private and public key and as we can see for MQQ-SIG the size of the public key for n ∈ {160, 192, 224, 256} is in the range from 125 up to 521 KBytes.