On the Security of UOV

Jean-Charles Faugère, Ludovic Perret

2009 · eprint 2009/483

Paper (eprint) →

Disclaimer

This content was automatically converted from the original PDF and may have undergone post-processing. None of these steps have been reviewed or approved by the authors. Errors in formulas, definitions, proofs, or text may have been introduced during conversion. The authoritative version is the original paper on ePrint. Always cite and verify against the original publication.

Converted with: marker · 2026-02-16

Jean-Charles Faugère, Ludovic Perret

Abstract. In this short note, we investigate the security of the Unbalanced Oil and Vinegar Scheme [15]. To do so, we use a hybrid approach for solving the algebraic systems naturally arising when mounting a signature-forgery attack. The basic idea is to compute Gröbner bases of several modified systems rather than a Gröbner basis of the initial system. It turns out that our approach is efficient in practice. We have obtained a complexity bounded from above by 2^{40.3} (or 9 hours of computation) to forge a signature on a set of parameters proposed by the designers of UOV.

1. Introduction

Multivariate Cryptography is the set of all the cryptographic primitives using multivariate polynomials. The use of algebraic systems in cryptography dates back to the mid eighties, and was initially motivated by the need for alternatives to number theoretic-based schemes. Indeed, although quite a few problems have been proposed to construct public-key primitives, those effectively used are essentially factorization (e.g. in RSA [17]) and discrete logarithm (e.g. in Diffie-Hellman key-exchange [11]). It has to be noted that multivariate systems enjoy low computational requirements; moreover, such schemes are not concerned with the quantum computer threat, whereas it is well known that number theoretic-based schemes like RSA, DH, or ECDH are [18].

Multivariate cryptography has become a dynamic research area, as reflected by the ever growing number of papers in the most famous cryptographic conferences. This is mainly due to the fact that an European project (NESSIE1) has advised in 2003 to use such a scheme (namely, SFLASH [8]) in the smart-card context. Unfortunately, Dubois, Fouque, Shamir and Stern [10] discovered a sever flaw in the design of SFLASH, leading to an efficient cryptanalysis of this scheme. In this paper, we investigate the security of another multivariate signature scheme, the so-called Unbalanced Oil and Vinegar UOV scheme [15]. To this end, we have used

<sup>1https://www.cosic.esat.kuleuven.be/nessie/

Gröbner bases [6, 7] and efficient algorithms for computing such bases; namely F_5 [14].

1.1. Organization of the Paper

After this introduction, the paper is organized as follows. In Section 2, we introduce the main concern of this paper, namely the Unbalanced Oil and Vinegar UOV scheme [15]. To our knowledge, no successful attack has been reported on this scheme. In section 3, we will present an efficient algebraic attack against UOV. Our attack can be viewed as a natural extension of [5, 4].

The most interesting type of one-way function used in multivariate cryptography is based on the evaluation of a set of algebraic polynomials \mathbf{p} = (p_1(x_1, \dots, x_n), \dots, p_m(x_1, \dots, x_n)) \in \mathbb{K}[x_1, \dots, x_n]^m , namely:

\mathbf{m} = (m_1, \dots, m_n) \in \mathbb{K}^n \longmapsto \mathbf{p}(\mathbf{m}) = (p_1(\mathbf{m}), \dots, p_m(\mathbf{m})) \in \mathbb{K}^m.

The mathematical hard problem underlying this one-way function is :

Polynomial System Solving (PoSSo)

Instance : polynomials p_1(x_1,\ldots,x_n),\ldots,p_m(x_1,\ldots,x_n) of \mathbb{K}[x_1,\ldots,x_n] . Question : Does there exists (z_1,\ldots,z_n)\in\mathbb{K}^n s. t. :

p_1(z_1,\ldots,z_n) = 0,\ldots,p_m(z_1,\ldots,z_n) = 0.

To introduce a trapdoor, we start from a carefully chosen algebraic system:

\mathbf{f}(\mathbf{x}) = (f_1(x_1, \dots, x_n), \dots, f_m(x_1, \dots, x_n)) \in \mathbb{K}[x_1, \dots, x_n]^m,

which is easy to solve. That is, for all \mathbf{c} = (c_1, \dots, c_m) \in \mathbb{K}^m , we have an efficient method for describing/computing the zeroes of:

f_1(x_1,\ldots,x_n) = c_1,\ldots,f_m(x_1,\ldots,x_n) = c_m.

In order to hide the specific structure of \mathbf{f} , we usually choose two linear transformations – given by invertible matrices – (S, U) \in GL_n(\mathbb{K}) \times GL_m(\mathbb{K}) and set

(p_1(\mathbf{x}), \dots, p_m(\mathbf{x})) = (f_1(\mathbf{x} \cdot S), \dots, f_m(\mathbf{x} \cdot S)) \cdot U,

abbreviated by \mathbf{p}(\mathbf{x}) = \mathbf{f}(\mathbf{x} \cdot S) \cdot U \in \mathbb{K}^m to shorten the notation.

The public-key of such systems will be the polynomials of \mathbf{p} and the secret-key is the two matrices (S, U) \in GL_n(\mathbb{K}) \times GL_m(\mathbb{K}) and the polynomials of \mathbf{f} .

To generate a signature \mathbf{s} \in \mathbb{K}^n of a digest \mathbf{m} \in \mathbb{K}^m , we compute \mathbf{s}' \in \mathbb{K}^n such that \mathbf{f}(\mathbf{s}') = \mathbf{m} \cdot U^{-1} . This can be done efficiently due to the particular choice of \mathbf{f} . Finally, the signature is \mathbf{s} = \mathbf{s}' \cdot S^{-1} since :

\mathbf{p}(\mathbf{s}) = \mathbf{f}(\mathbf{s}' \cdot S^{-1} \cdot S) \cdot U = \mathbf{m} \cdot U^{-1} \cdot U = \mathbf{m}.

To verify the signature \mathbf{s} \in \mathbb{K}^n of the digest \mathbf{m} \in \mathbb{K}^m , we check whether the equality : " \mathbf{p}(\mathbf{s}) = \mathbf{m} " holds. We would like to emphasize that most of the multivariate

signature schemes proposed so far (e.g. [8, 19]), including UOV [15], follow this general principle. For UOV, the matrix U is simply equal to the identity matrix. The main specificity of UOV lies in the way of constructing the inner polynomials f(x) = f1(x1, . . . , xn), . . . , fm(x1, . . . , xn) ∈ K[x1, . . . , xn] m. Kipnis, Patarin, and Goubin [15] proposed the following construction. The n variables x1, . . . , xn are partitioned in two sets {xi}i∈V and {xi}i∈O where V = {1, . . . , n − m} is the set of vinegar indices and O = {n − m + 1, . . . , n} the set of oil indices. Each polynomial fk of the secret mapping has a quadratic part f (2) k of the special form :

$$f_k^{(2)}(x_1, \dots, x_n) = \sum_{(i,j) \in V \times V i \le j} \alpha_{i,j}^{(k)} x_i x_j + \sum_{(i,j) \in V \times O} \beta_{i,j}^{(k)} x_i x_j . \tag{1}$$

As a consequence of this very special structure, the equations induced by equations (1) when fixing the vinegar variables to constant values are linear in the remaining (oil) variables. This provides an efficient method for inverting system f(x) with a high probability — the linear system in the oil variables we obtain is invertible with high probability. For more details, we refer the reader to the initial paper [15].

The authors of UOV have recommended in [15, 16] to choose parameter values such that n > 3m. In particular, they proposed [16] the following set of parameters : K = F2 4 , m = 16, n = 32 (or 48). We will show that this set of parameters does not guaranty a sufficient level of security.

We now describe our attack against UOV [15]. Our goal is to forge a valid signature s 0 ∈ Kn for a given digest m = (m1, . . . , mm) ∈ Km. In other words, we want to find an element of the variety :

V_{\mathbb{K}}(p_1-m_1,\ldots,p_m-m_m)\subseteq\mathbb{K}^n,

with p1, . . . , pm ∈ K[x1, . . . , xn] the polynomials of UOV public-key. We recall that the parameters are K = F2 4 , m = 16 and n = 32 (or 48) .

The main limitation for computing directly this variety is due to the fact that the number of equations (m) is smaller that the number of variables (n). As a consequence, there is at least (#K) n−m valid solutions to the signature-forgery system. Hence, even if you suppose that you have been able to compute a Gr¨obner basis for the degree reverse lexicographical ordering (DRL), you will probably not be able to recover efficiently the Lex-Gr¨obner basis using FGLM [12]. The reason is that the complexity of FGLM is polynomial in the size of the variety.

A natural way to overcome these practical limitations is to randomly specialize (i.e. fix) n − m variables. We will have to solve a system having the same number of variables and equations (m). For each specification of the n − m variables, we can always find a solution of the new system yielding to a valid signature. We also mention that the specialized system will have very few solutions in practice. Thus, the cost of computing the variety will be now essentially the cost of computing a Gr¨obner basis. It is exactly at this point that the authors of [5], which also tried to attack UOV using Gr¨obner basis, stopped their analysis.

The important observation here is that – after having specified n − m variables – the new system will behave like a semi-regular system [1, 3, 2]. We will present latter in this section experimental results supporting this claim. Note that such a behavior has been also observed, in a different context, in [20]. The degree of regularity of a semi-regular system of m variables and equations is equal to m + 1. In our context (m = 16), this remains out of the scope of the F5 algorithm. This is exactly the reason explaining why Braeken, Wolf, Preneel concluded that their attack can not be efficient.

To avoid this difficulty, we can use the fact that #K is relatively small and try to decrease the degree of regularity by specializing r ≥ 0 more variables (in addition of the n − m variables already fixed). Thus, we will have to solve a systems of m equations with m−r variables, which behave like semi-regular systems. This allows to decrease the degree of regularity, and thus the complexity of F5. For instance, the degree of regularity of a semi-regular system of m−1 variables and m equations is approximately equal to l (m+1) 2 m . More generally, the degree of regularity is given by the index of the first non-positive coefficient of the series[1, 3, 2] :

\frac{\prod_{i=1}^{m} (1-z^2)}{(1-z)^{m-r}}.

In the following table, we have quoted the degree of regularity observed in our experiments. Namely, the maximum degree reached during F5 on systems obtained by fixing n − m + r variables (r ≥ 0) on signature-forgery systems. We have also quoted the theoretical degree of regularity of a semi-regular system of m equations in m − r variables. These experiments suggest that the systems obtained when mounting a specify+solve signature forgery attack against UOV behave like semiregular systems.

m m − r r dreg
(theoretical)		 dreg
(observed)
16 15 1 9 9
16 14 2 7 7
16 13 3 6 6

By fixing variables, we can obtain a significant gain on the complexity the F5. On the other hand, as soon as r > 0, each specification of the r variables will not necessarily lead to an algebraic system whose set of solutions is not empty . But, we know that there exists a least one guess of the r variables (in practice exactly one) leading to a system whose zeroes allow to construct a valid signature. Thus, we have to perform an exhaustive search on the r new variables. In other words, instead of computing one Gr¨obner basis of a system of m equations and variables, we compute (#K) r Gr¨obner bases of "easier" systems (m equations with m − r variables). We have then to find an optimal tradeoff between the cost of F_5 and the number of Gröbner basis that we have to compute.

In the table above, we have quoted practical results that we have obtained with F_5 when solving systems obtained by fixing n-m+r variables ( r \geq 0 ) on signature-forgery systems. In this table, T_{\rm F_5} is the time of computing one Gröbner basis with F_5 . We also included the corresponding number of operations (field multiplications) {\rm Nop}_{\rm F_5} performed by {\rm F_5} , and the total number N of operations of our attack (i.e. the cost of computing 2^{4\cdot r} Gröbner bases). Finally, we have quoted the maximum memory, denoted Mem, used during the Gröbner basis computation. The experimental results have been obtained using a bi-pro Xeon 2.4 Ghz with 6 Gb. of Ram.

\overline{m} m-r r T_{\mathrm{F}_5} Mem \mathrm{Nop}_{\mathrm{F}_5} N
16 15 1 \approx 1 \text{ h}. 3532 Mb. 2^{36.9} 2^{40.9}
16 14 2 126 s. 270 Mb. 2^{32.3} 2^{40.5}
16 13 3 9.41 s. 38 Mb. 2^{28.7} 2^{40.7}

Once can see that the most interesting tradeoff is obtained with r=2. In this case, we obtain a complexity of 2^{40.3} , which is approximatively equivalent to 9 hours of computations. It is interesting to remark that the complexity of our attack not relies on the number of variables n, but only on the number of polynomials. So, the result presented here are valid for n=32, or n=48 (and for any n=k\cdot m , with k\geq 1 ).

As the consequence, the parameters of UOV [16] that we have studied should be no longer recommended. We believe that one should use the other set of parameters, with \mathbb{K} = \mathbb{F}_2 , proposed in [16].

References

Jean-Charles Faug`ere, Ludovic Perret INRIA, Centre Paris-Rocquencourt, SALSA Project UPMC, Univ Paris 06, LIP6 CNRS, UMR 7606, LIP6 Universit´e Pierre et Marie Curie Paris 6 UFR Ing´enierie 919 LIP6 Passy Kennedy, bureau 733 Boite Courrier 169 4, Place Jussieu 75252 Paris cedex 05

e-mail: Jean-Charles.Faugere@inria.fr e-mail: ludovic.perret@lip6.fr

History

  • 2026-02-17Add disclaimer: content not author-approved, eprint is authoritative6638546
  • 2026-02-16Add 471 new paper pages from poseidon-formalizationc189c48