Pierre Pébereau
email: pierre.pebereau@lip6.fr

Singular points of UOV and VOX

Keywords: Multivariate cryptography, Cryptanalysis, Singular points, Bihomogeneous polynomial system

Introduction

Unbalanced Oil and Vinegar (UOV) is a multivariate signature scheme introduced in 1999 by Kipnis, Patarin and Goubin [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF] to counter the Kipnis-Shamir attack [START_REF] Kipnis | Cryptanalysis of the oil & vinegar signature scheme[END_REF] on Oil and Vinegar [START_REF] Patarin | The oil and vinegar signature scheme[END_REF]. Since then, the scheme has suffered no major attack and has been used as a basis for many multivariate signature schemes.

There is a strong belief that polynomial system solving remains a hard task for quantum computers, and this motivated the submission of UOV-based schemes to post-quantum standardisation contests. Among them, the NIST competition for post-quantum cryptography has garnered the most attention from the cryptographic community. Many multivariate signature schemes were submitted, in particular Rainbow [START_REF] Ding | Rainbow, a new multivariable polynomial signature scheme[END_REF] was a finalist in the third round. The cryptanalysis of Rainbow [START_REF] Beullens | Breaking rainbow takes a weekend on a laptop[END_REF] renewed the interest in UOV and its variants, and among the 10 multivariate schemes submitted to the additional signature round, 7 are closely related to UOV (either special cases or using modified UOV keys). These submissions are MAYO [START_REF] Beullens | MAYO: practical post-quantum signatures from oil-and-vinegar maps[END_REF], PROV [START_REF] Cogliati | Provable unbalanced oil and vinegar[END_REF], QR-UOV [START_REF] Furue | A new variant of unbalanced oil and vinegar using quotient ring: Qr-uov[END_REF], SNOVA [START_REF] Wang | [END_REF], T-UOV [START_REF] Ding | Triangular unbalanced oil and vinegar[END_REF], (plain) UOV [5] and VOX [START_REF] Cogliati | Vox-sign[END_REF].

The main appeal of these schemes, compared with the NIST PQC standards based on lattices, is the significantly shorter signature size they achieve: at NIST security level I, UOV achieves signatures as short as 96 bytes, as opposed to Falcon requiring 666 bytes. The drawback of these schemes is the very large key size, which is mitigated by considering additional structure. For instance, the MAYO submission achieves at the same security level a signature of 321 bytes for a key size of 1168 bytes, where Falcon uses a 897 bytes public key.

Contribution

In this paper, we first study the singular locus of the UOV variety, in particular its intersection with the secret subspace O and the expected dimension of this intersection. The existence of a large singular locus is a very peculiar property for a polynomial system, as it is generically empty (we use here the notion of genericity induced by Zariski topology). These singular points may be targeted by algebraic key recovery attacks. We propose two algebraic modelisations, each leading to an attack. We also highlight the connection between these attacks and the Kipnis-Shamir attack described in [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF], providing an algebraic alternative to this attack. This has several consequences: we are able to identify some heuristics implicitly used in the Kipnis-Shamir attack, and our attacks do not suffer from the field size, as opposed to the Kipnis-Shamir attack which is enumerative by nature. Moreover, the Kipnis-Shamir attack relies on the existence of rational singular points to succeed, whereas our attacks do not fail when there exists no rational singular point.

As a second contribution, we apply this work to VOX, a UOV variant. VOX [START_REF] Cogliati | Vox-sign[END_REF] is a scheme based on UOV + and utilizing the Quotient Ring (QR) transform [START_REF] Furue | A new variant of unbalanced oil and vinegar using quotient ring: Qr-uov[END_REF]. It has been submitted to the NIST call for additional signatures. We study the vulnerability of this scheme to our attacks by considering UOV +, which is equivalent to dismissing the additional structure provided by the QR-transform.

We prove that the + structure does not prevent the attacker from targeting the singular points of the underlying UOV key. The security model for UOV + key recovery attacks previously estimated that such attacks can only be applied after inverting the + transform. Our work proves that this is not the case, and we obtain cheaper attack costs than the estimates found in [START_REF] Faugère | A new perturbation for multivariate public key schemes such as hfe and uov[END_REF] and [START_REF] Cogliati | Vox-sign[END_REF]. More precisely, for the VOX parameters from [START_REF] Cogliati | Vox-sign[END_REF], we gain factors 2 19 , 2 26 , 2 57 for security levels I,III,V respectively, bringing the security below the NIST target of 2 143 , 2 207 , 2 272 gates. Asymptotically, we gain a factor q t for key recovery attacks against these schemes, where q is the size of the field considered in VOX and t is a parameter of the scheme.

We provide a method recovering the full VOX private key from a single oil vector, generalizing a result of [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF], by utilizing a MinRank instance solved enumeratively. This allows an attacker to obtain a full key recovery attack from the previously mentioned singular point computation, but also to mount a new key recovery attack.

Finally, we provide experimental results and the code used to obtain them, to study the practical behavior of the different attacks and in particular compare the theoretical bounds with practical results on small instances.

Related work

The Kipnis-Shamir attack [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF] is an enumerative attack that repeatedly computes eigenvectors of some linear maps related to the public key of a UOV instance. It has been observed that this attack computes singular points in the intersection of two quadrics that share a large isotropic subspace. This observation is due to Luyten [START_REF] Luyten | Understanding Kipnis Shamir with two quadrics[END_REF] in the context of Oil and Vinegar, and has been generalized to the case of UOV by Beullens and Castryck (private communication, July 2023). The difference in our approach is the focus on the properties of the singular locus, in particular its dimension, and proposing an alternative algebraic modeling of this computation.

VOX is a signature scheme based on UOV + and utilizing the QR structure introduced by [START_REF] Furue | A new variant of unbalanced oil and vinegar using quotient ring: Qr-uov[END_REF]. The QR transform consists in using block matrices in the key pair. Each block, of size ℓ × ℓ, represents an element of a field extension of degree ℓ, allowing for smaller public keys but introducing a new security assumption. Based on [START_REF] Furue | A new security analysis against mayo and qr-uov using rectangular minrank attack[END_REF], Furue and Ikematsu attacked the parameters of the QR transform used in VOX. This attack did not target the UOV + scheme. In contrast, we show that the unstructured security assumption, namely the security of the UOV + scheme, is overestimated by the VOX specification.

Organisation of the paper

In Section 2, we define the UOV signature scheme and quadratic forms, and recall some properties of these objects. In Section 3, we prove the existence of the singular locus of the UOV variety, and give the dimension of its intersection with O. We then exploit this structure to introduce key recovery attacks against UOV. In Section 4, we apply the results of the previous sections to introduce key recovery attacks against UOV + bypassing the + structure. To obtain a full key recovery attack, we generalize the key recovery from one vector of [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF] to the case of UOV +. These results directly apply to VOX. In Section 5, we present the experimental results supporting the theory presented throughout the paper.

Main results

The main result of this paper is the computation of the dimension of the intersection of the singular locus of the UOV variety with the secret subspace. This enables us to obtain two new algebraic attacks against the UOV scheme.

We obtain a similar result for the UOV + variety, which leads to a key recovery attack against UOV + that improves the previously known upper bounds for the security of the scheme.

Theorem 2 Let P be a UOV + public key chosen uniformly at random for parameters (q, n, o, t) with n > o. Then the UOV + variety V(I) = {x ∈ F q n , P(x) = 0} has a positive dimensional singular locus. More precisely, let r ≤ o -t,

d ′ = 2o + r -n -1, d = d ′ -t:
i. If d ′ ≥ 0, the variety defined by r equations of the underlying UOV key has a singular locus of dimension d ′ . ii. If d ≥ 0, the variety defined by r equations of the UOV + public key has a singular locus of dimension d.

From one vector computed in the previous attack, we show how to complete a key recovery by adapting a result of [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF] to the case of UOV +.

Theorem 3 Let P be a UOV + public key for parameters (q, o, v, t), let O be the associated UOV secret subspace, and let x ∈ O. Then there exists an algorithm taking as input x and P and outputting a basis of O, requiring at most O (q t (n -o) ω ) arithmetic operations in F q .

Preliminaries

Notations

Let q = p e for p prime and e ∈ N >0 . Let F q denote the finite field with q elements. We call p the characteristic of F q . Vectors are assumed to be column vectors and are denoted by bold letters: x, y, o, . . .. Matrices are denoted by capital letters, and transposition is written A T . The kernel of a matrix A is denoted by ker(A) and is a right kernel: x ∈ ker(A) ⇐⇒ Ax = 0. Given a field F and an integer n, we denote by F[x 1 , . . . , x n ] or F[x] the polynomial ring of F in n indeterminates. The restriction of a function f to a set E is denoted by f |E . The canonical basis of the vector space F n q is noted (e 1 , . . . , e n ).

Unbalanced Oil and Vinegar

A UOV key pair for parameters (n, m, q) is composed of a secret key (A, F) and a public key P, with:

-A ∈ GL n (F q ) an invertible matrix, -F = (F 1 , . . . , F m ) a quadratic map with F i (e j ) = 0 for 1 ≤ i, j ≤ m -P = F • A = (P 1 , . . . , P m ) a quadratic map.

In practice, we consider homogeneous quadratic maps: there are no constant and linear terms. If we represent the quadratic maps with matrices, we have for all 1 ≤ i ≤ m:

F i = 0 F (1) i F (2) i F (3) i (1)
P i = A T F i A (2)
This idea was introduced by Patarin in [START_REF] Patarin | The oil and vinegar signature scheme[END_REF] and the motivation was that the secret system F(x) = t is linear in x 1 , . . . , x m :

F(x) = t ⇐⇒        x T F 1 x = t 1 . . . x T F m x = t m (3)
These variables are distinguished from the rest of variables and are named "oil variables". The remaining ones are "vinegar variables". The knowledge of A allows the signer to efficiently solve P(x) = t using this property. Define the ideal generated by the public key I = ⟨p 1 , . . . , p m ⟩. The set of accepted signatures for a message t ∈ F m q is an algebraic variety of dimension n -m generically. We distinguish the case t = (0, . . . , 0) and define the UOV variety

V(I) = {x ∈ F n q , P(x) = (0, . . . , 0)}

Quadratic forms

One of the key insights from the cryptanalysis of Oil and Vinegar [START_REF] Kipnis | Cryptanalysis of the oil & vinegar signature scheme[END_REF] and Rainbow [START_REF] Beullens | Improved cryptanalysis of UOV and rainbow[END_REF] is the necessity to have a geometric perspective on the equations defining the scheme. More precisely, we reformulate the UOV trapdoor in terms of subspaces, which yields a better understanding of the relationship between the public and private keys. We use the formalism of quadratic forms with the following definitions. Let f be a homogeneous quadratic form over a vector space F n q . In fields of odd characteristic, a homogeneous quadratic form f is characterized by its polar form f * := (x, y) → f (x+y)-f (x)-f (y) which is a symmetric bilinear form. As such, it admits a unique symmetric matrix representation in F n×n q . We identify both f and f * to this matrix. In fields of even characteristic, there is no longer an equivalence with symmetric bilinear forms. Instead, we can represent quadratic forms uniquely using triangular matrices. Dense square matrices are valid representations, but there are many dense matrices representing the same quadratic form. Changes of variables are not as straightforward with triangular representations, as the set of triangular matrices is not stable by congruence: if F is upper triangular, and A ∈ GL n (F q ), A T F A is not necessarily upper triangular. Notice in particular that the triangular representation of A T F A does not necessarily have the same rank as F . In characteristic two, using triangular representation, we may therefore not refer to the "rank of the quadratic form" as it is not uniquely defined. It is uniquely defined in dense or symmetric representation by property of matrix multiplication.

Therefore, when referring to the rank, we will assume that the matrices representing the quadratic forms are either dense in characteristic two or symmetric in odd characteristic. This way, we may define the rank of a quadratic form: we say that f has rank r if the matrix associated to f has rank r. The rank is preserved by linear changes of variables.

Finally, we recall the definition of isotropic subspaces which is the core of the study of the UOV key pair. A subspace V ⊂ F n is isotropic for f if there exists x ∈ V such that f (x) = 0, totally isotropic if for all x ∈ V, f (x) = 0, and

anisotropic if for all x ∈ V \ {0}, f (x) ̸ = 0.
The secret key of UOV may be characterized in terms of isotropic subspaces: (3) This shows that the secret key of UOV is a totally isotropic subspace of dimension m shared by each of the public key quadratic forms. This observation was made as early as the Kipnis-Shamir attack against OV in 1998 [START_REF] Kipnis | Cryptanalysis of the oil & vinegar signature scheme[END_REF], with the name "oil space".

Lemma 1.
Mat B (f ) = 0 F (1) F (2) F
Observe that the dimension of a totally isotropic subspace of a quadratic form of a certain rank is bounded: Lemma 2. Let f be a quadratic form of rank n defined over a field K. Let O be a totally isotropic subspace of f . Then O has dimension no greater than ⌊ n 2 ⌋.

Proof. By contradiction, assume that f has rank n and dim(O) = r > ⌊ n 2 ⌋. Let B be a basis of O, let B be a completion of B into a basis of K n . Then the matrix representing f * in basis B has a block of zeros of size r × r in the top left corner. Therefore its rank is less than n, which is a contradiction. ⊓ ⊔

Cryptanalysis of UOV and its variants

Consider an instance of UOV with parameters (q, n, m) with a public key P.

The Kipnis-Shamir attack [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF], [START_REF] Kipnis | Cryptanalysis of the oil & vinegar signature scheme[END_REF] The Kipnis-Shamir attack on Oil and Vinegar [START_REF] Kipnis | Cryptanalysis of the oil & vinegar signature scheme[END_REF]Theorem 7] is a polynomial time algorithm retrieving a basis of O when n = 2m. It motivated the "unbalanced" property of UOV introduced in [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF]. The attack has been generalized to UOV by [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF]Theorem 4.2], in which case it is no longer polynomial. We detail the attack on UOV below.

Let (α i ) 1≤i≤m-1 ∈ F m-1 q
and define M = m-1 i=1 α i P i . Then P -1 m M has an invariant subspace included in O with probability greater than p = q 3m-n -1 q m -1 . We compute eigenvectors using the characteristic polynomial, which is computed in time O(n ω ) and factored in time O(n log(n)) Therefore, after an expected q n-2m draws of eigenvectors of such linear maps, each with a cost n ω , an attacker expects to have found a vector in O.

Key recovery from one vector [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF] Lemma 1 shows that once one or more vectors of the secret key have been obtained, one obtains linear equations characterizing the remaining vectors. This formulation yields a polynomial time key recovery from two vectors by solving a linear system.

In fact, one vector suffices for this task with the following observation:

x ∈ O =⇒ O ⊂ ker   
x T P 1 . . .

x T P m   
This kernel has dimension n -m generically. Therefore, the restriction of the UOV public key to this linear subspace is a UOV instance with less variables.

If n -m < 2m, by Lemma 2 the matrices composing the public key of this new UOV instance are singular. The kernels of these matrices are linear subspaces included in O that generically span O.

Key recovery attack against UOV: Singular points

As seen in the previous section, finding one vector in the secret subspace O is enough to break UOV. This task is challenging, and motivates the search for distinguished points in O. If such points exist, one may hope to compute them more efficiently than generic points in O. This section focuses on this question, proving that there exist a large number of singular points of the UOV variety in the secret subspace. This leads to new key recovery attacks on UOV.

Singular points of V(I)

The goal of this subsection is to study the singular locus of the UOV variety, in particular its dimension. We start by defining singular points of an algebraic variety:

Definition 1. Let (p 1 , . . . , p m ) be a collection of homogeneous polynomials over K[x]. Let I = ⟨p 1 , . . . , p m ⟩ be a radical ideal. We say that x ∈ V(I) \ {0} is a singular point of V(I) if the Jacobian matrix Jac P (x) ∈ K[x] m×n has rank less than codim(I). The set of singular points of V(I) is noted Sing(V(I)).

For generic polynomial systems, there are no singular points. Note that the determinantal ideal generated by the maximal minors of Jac P (x) has dimension m -1 when P is generic: there exist points that drop the rank of the Jacobian, but they do not belong to the variety defined by the system generically.

In odd characteristic, we represent the UOV public key using symmetric matrices P 1 , . . . , P m . Notice that

1 2 Jac P (x) =   
x T P 1 . . .

x T P m    (4)
In even characteristic, using triangular matrices, we observe a similar property by dismissing the diagonal terms. This is always possible as these entries correspond to squares of variables x 2 j which are linear due to the Frobenius endomorphism x → x p .

Jac P (x) =    x T P 1 . . . x T P m    (5)
A constant factor does not affect the ideals that we consider, therefore we will also denote this matrix Jac P (x) in odd characteristic.

Theorem 1 (Homogeneous singularities). Choose p 1 , . . . , p m uniformly at random among the quadratic forms generating a radical ideal Proof. This proof uses the shape of a UOV key. Let P(x) = (p 1 (x), . . . , p m (x)). Let B = (b 1 , . . . , b n ) be a basis of F n q such that b 1 , . . . , b o is a basis of O. Let F(x) = P(Bx). This system has the shape of a UOV secret key by Lemma 1: the equations depend linearly on x 1 , . . . , x o . This implies that the partial derivatives with respect to any "oil" variable 1 ≤ j ≤ o are linear forms in the "vinegar" variables x o+1 , . . . , x n . Therefore, the Jacobian of the system has a special shape: x 1 , . . . , x o do not appear in the first o columns of the Jacobian. Thus, for all x ∈ F o q × {0} n-o (an "oil vector"), we have:

I = ⟨p 1 , . . . , p m ⟩ such that V(I) contains an o-dimensional linear subspace O. Let d = 2o + m - n -1. If d ≥ 0,
Jac F (x) =    1 . . . o o + 1 . . . n 0 . . . 0 1 . . . . . . . . . 0 . . . 0 m J ′ (x)    where J ′ (x) is a matrix of (F q [x 1 , . . . , x o ]) m×(n-o)
with entries that are generic linear forms. Since n > m, notice that Jac F (x) is not full rank if and only if J ′ (x) is not full rank since any minor containing one of the first o columns is zero. Thus, following the terminology of [START_REF] Faugère | On the complexity of the generalized minrank problem[END_REF], Jac F (x) is not full rank if and only if x lies in the variety of the determinantal ideal J m-1 generated by the m-minors of J ′ . By [START_REF] Faugère | On the complexity of the generalized minrank problem[END_REF]Theorem 10] , this ideal has dimension

d = o-(n-o-(m-1))(m-(m-1)) if d ≥ 0, or more succintly: d = 2o + m -n -1
By the chain rule, there is a one-to-one mapping from singular points of the system F to singular points of the system P:

Jac P (x) = Jac F (B -1 x)B -1 Therefore dim Sing(V(I)) = d. ⊓ ⊔
This property distinguishes the UOV system of equations from random systems of equations since random systems of homogeneous quadratic equations do not admit non-zero singular points. Notice that in this theorem, we make a distinction between the values m and o, even though they are equal for UOV. There are two reasons for this:

-There are schemes, such as MAYO and PrUOV, based on the same core ideas as UOV but which distinguish these two values. -This allows us to obtain different modelisations to compute singular points leveraging the positive dimension of the singular locus.

Notice that by setting m = o and n = αm, Theorem 1 shows that the UOV variety has a non-empty singular locus, which has an intersection of dimension (3 -α)m -1 with O for the practical parameter range 2 < α ≤ 3.

We consider a zero-dimensional system by restricting to a subset of r equations from the key.

2o + r -n -1 ≥ 0 ⇐⇒ r ≥ n -2o + 1 = (α -2)o + 1
In particular, for r 0 = ⌈(α -2)o + 1⌉, the singular locus is 0 dimensional.

We highlight the following hypothesis, that has been used implicitly by the Kipnis-Shamir attack and that is supported by experiments on small instances. We reuse the notations introduced above.

Hypothesis 1 Let V(I) = {x ∈ F n q , p 1 (x) = . . . = p m (x) = 0} be the variety defined by a generic collection of quadrics with a common totally isotropic subspace

O. Assume dim(O) = o. If 2o + m -n -1 > 0, then Sing(V) ⊂ O.
Here, genericity means that we choose the quadrics uniformly at random among those that vanish on O. From a practical perspective, this is the key generation process in UOV: we choose all coefficients of F at random, except for the blocks of zeros that we impose.

This hypothesis is implicitly used in [18, Lemma 3] as the invariant subspace H computed by the attack is one-dimensional. We detail the relationship between these invariant subspaces and singular points in Section 3.5.

This hypothesis has a very interesting consequence that we can leverage in attacks against UOV. If it holds, then the singular locus is entirely included in O, a linear subspace.

In particular, assuming the ideal is radical, there must be n -m linear forms in a reduced Gröbner basis with respect to a graded ordering for the previous ideal. Their kernels define n -m distinct hyperplanes, the intersection of which is exactly O. The main consequence is that we do not need rational singular points to obtain a key recovery attack against the scheme using an algebraic approach. We detail this in the next result.

Proposition 1. Let O be a linear subspace of F n q of dimension o. Let I = ⟨p 1 , . . . , p m ⟩ be a radical ideal of F q [x] such that V(I) ̸ = ∅ and V(I) ⊂ O.
Then, a Gröbner basis of I for any graded monomial ordering contains linear equations Next, let ≺ be a graded monomial ordering. On the first hand, a graded monomial ordering is a monomial ordering which first compares the total degree before breaking ties. Therefore, if p is a polynomial in F q [x], then the leading term of p with respect to ≺ has degree equal to the total degree of p.

H 1 (x), . . . , H n-o (x) such that O = ∩ n-o i=1 H i Proof.
On the other hand, a Gröbner basis of

I for ≺ is a set G = {g 1 , . . . , g t } ⊂ I such that ⟨LT ≺ (g 1 ), . . . , LT ≺ (g t )⟩ = ⟨LT ≺ (I)⟩
This implies that a Gröbner basis of I must contain polynomials whose leading terms are of minimal degree, in our case 1. The collection of linear equations included in a Gröbner basis must have rank at least n -o, otherwise we could find a linear equation in I linearily independent from the ones in the basis. We add that in the reduced Gröbner basis for ≺, there are only independent linear equations, otherwise the basis would not be reduced. ⊓ ⊔

Modeling singularities

Under Hypothesis 1, we use Theorem 1 to obtain key recovery attacks against UOV by computing singular points of the variety defined by subsets of equations of the UOV public key. Intuition suggests that including all the equations may be too costly: a naive minors modeling would yield equations of degree m, far above the degree of regularity of any competitive attack on UOV (see for instance [START_REF] Beullens | Improved cryptanalysis of UOV and rainbow[END_REF]).

We propose two attacks based on two different modelings, one based on minors of the Jacobian, and a bihomogeneous modeling based on the "Lagrange multiplier" method as it is known in polynomial optimization (this is closely related to the Kipnis-Shamir approach to the MinRank problem). Both modelisations are highly structured (the former spans a determinantal ideal and the latter is bihomogeneous of bidegree (2,1)) and are suited for Gröbner basis approaches.

Definition 2. Let P(x) be a UOV system of m equations in n variables. We denote by Jac P,r the Jacobian matrix of the system P(x) truncated to the first r lines.

1. Minors modeling:

M(P, r) :      x ∈ F n q P(x) = 0 Minors m (Jac P,r (x)) = 0 (6)
2. Bihomogeneous modeling:

B(P, r) :      x ∈ F n q , y ∈ F r q P(x) = 0 y T Jac P,r (x) = 0 (7)
If they exist, solutions x of either of these systems are singular points of the variety defined by ⟨p 1 , . . . , p m ⟩ by construction.

In the case of Oil and Vinegar, Luyten [START_REF] Luyten | Understanding Kipnis Shamir with two quadrics[END_REF] observed that solving the minors modeling system for r = 2 is a polynomial task in practice. The minors modeling does not scale well in the case of UOV, due to the cost of computing maximal minors (there are n r maximal minors). This is why we introduce the bihomogeneous system.

We analyze the complexity results associated to each modeling. Note that any r lines of the Jacobian may be chosen to build Jac P,r , the choice of the first r ones is arbitrary.

Computing singular points using the minors modeling

Determinantal ideals are not semi-regular, and therefore the degree of regularity of these ideals is obtained through a different Hilbert series than the usual semiregular case. The problem of computing critical points is well-studied and is closely related to the problem of singular points. We use results from [START_REF] Berthomieu | Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems[END_REF] to obtain the Hilbert series of the ideal we consider.

Proposition 2. [1, Proposition 5 and paragraph 3.4] Let P(x) be a system of r equations in n variables. The system M(P, r) is a system of r + n r equations, of which r are of degree 2 and n r are of degree r. Let I M be the ideal generated by the system M(P, r). The Hilbert series of

F q [x]/I M is H(t) = r-1 k=0 n -r -1 + k k t k (1 + t) r
Notice that if x ∈ O, then it satisfies the remaining equations of the public key: p r+1 (x) = . . . = p m (x) = 0. Assuming they are not zero-divisors in K[x]/I M , the Hilbert series (in this case a polynomial) of the ideal I = I M + ⟨p r+1 , . . . , p m ⟩ is:

H I (t) = H(t) • (1 -t 2 ) m-r = ( r-1 k=0 n -r -1 + k k t k )(1 + t) m (1 -t) m-r
The degree of regularity of the system is the first non-positive coefficient in this polynomial [START_REF] Faugère | On the complexity of gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF]. Given the degree of regularity d reg , the number of arithmetic operations is upper-bounded by:

C(n, d reg ) = O n + d reg d reg ω
Figure 1 lists the number of field operations required for the minor modeling systems with r = m 2 +1 on modern UOV parameters. We also list the corresponding degrees of regularity. We note that these costs are over twice the security levels expected of each parameter set. The utility of this modeling and the one detailed in Section 3.4 is that increasing the size of the field does not affect the number of field operations: therefore the increase in the number of binary operations in a larger field is polylogarithmic. This makes these algebraic approaches suitable for large fields, such as those that appear in the security assumptions behind QR-UOV [START_REF] Furue | A new variant of unbalanced oil and vinegar using quotient ring: Qr-uov[END_REF].

Computing singular points using the bihomogeneous modeling

From a complexity perspective, we can obtain better bounds by considering the bihomogeneous system described in Equation [START_REF] Cogliati | Vox-sign[END_REF]. From a practical perspective, the improvement is significant. The results we rely on are described in detail in [24, Chapter 6] and [START_REF] Faugère | Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity[END_REF]. Definition 3. Let x = (x 1 , . . . , x n ), y = (y 1 , . . . , y m ) two sets of variables. Let p a polynomial in K[x, y]. We say that p is bihomogeneous of bidegree (d 1 , d 2 ) with respect to x, y if

∀(λ, µ) ∈ K 2 , p(λx, µy) = λ d1 µ d2 p(x, y)
We can slightly improve the formulation of Equation 7: y is any element of the one-dimensional1 left kernel of the Jacobian evaluated on a singular point. Thus, for each x ∈ Sing(V(I)), there exist q choices of y in (F q ) r . We may normalize either to y 1 = 1 or y 1 = 0 and for some i ̸ = 1, y i = 1 to obtain a unique solution. In doing so, we dehomogeneize the system, allowing us to consider an affine bihomogeneous system.

We may choose r such that the system B(P, r) is a bihomogeneous system of n + m equations in n + r -1 variables defining a zero-dimensional ideal. It is bihomogeneous of bidegree (2,1) in the variables (x 1 , . . . , x n ), (y 2 , . . . , y r ). More precisely, the n Lagrange multiplier equations y T Jac P (x) = 0 ∈ F n q are bilinear of bidegree (1,1) and the "public equations" P(x) = 0 ∈ F m q only involve (x 1 , . . . , x n ) and therefore have bidegree (2,0). Using [13, Theorem 6.1], this zero-dimensional affine bilinear system has degree of regularity min(n + 1, r) = r. This value matches the experiments performed on small instances of UOV. Therefore, the number of arithmetic operations required to obtain a Gröbner basis is dominated by:

O n + 2r -1 r ω Remark 1.
This formula is valid in the zero-dimensional case: using it to evaluate the cost of a hybrid approach is pessimistic.

We give in Figure 2 the estimated number of arithmetic operations required to solve the bihomogeneous system using a generic Gröbner basis algorithm. Fig. 2: Cost of the singular point attack via bihomogeneous modeling for UOV

Revisiting the Kipnis-Shamir attack [19]

Bihomogeneous modeling -y-Enumeration. Consider a hybrid approach to the bihomogeneous system defined in Equation ( 7), where we enumerate over all possible values of y. In this case, we will have n linear equations in x, having evaluated all the y variables in F q . Let us consider this case more carefully, by rewriting the modeling:

∃x, y | y T Jac F (x) = 0 P(x) = 0 ⇐⇒ ∃x, y |    ( m i=1 y i P i )x = 0 P(x) = 0 (8)
Instead of using a Gröbner basis algorithm, observe that the linear equations entirely determine x, and there are no x solutions unless the linear combination m i=1 y i P i is singular. If x is a solution to the linear system, we check whether it is a solution to the quadratic system simply by evaluating P(x). Such a point will be singular for the system {p 1 (x), . . . , p m (x)} by [START_REF] Cox | Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF].

Since the quadratic system is homogeneous, it does not matter which solution of the linear system we choose, as we expect only a dimension 1 kernel. Denote M (y) = m i=1 y i P i . Since the matrices are square, and the target rank is n -1, we may consider Equation ( 8) as a MinRank instance where the only equation is the determinant of the matrix M (y). Guessing all the y variables is an enumerative method for this MinRank instance.

To estimate the complexity of this approach, we count the number of choices of y corresponding to singular points. For each singular point x, there exists q -1 vectors y ∈ ker(Jac P (x)) as the rank defect of the Jacobian is only 1. Let S = |Sing(V(I))| be the number of rational singular points of the UOV variety. This yields (q -1)S valid choices of y out of q m possibilities. We delay the estimation of S, and focus on the cost of finding a valid value of y.

We can improve the previous approach by noticing that we did not use the equation defined by the determinant of M (y): we only checked whether it was canceled. If we only guess m -1 variables, then we can consider the determinant as a univariate polynomial in the remaining variable. We may solve this univariate equation with a fast finite field algorithm to find the values of y r such that the determinant vanishes. Computing the determinant of a univariate matrix is a polynomial task with efficient algorithms in practice 1 . To summarize, for each guess of the m -1 variables, we proceed as follows:

-Compute M (y) a sum of m n × n matrices in F q [y] ≤1 O(mn 2 ) -Compute det(M (y)), a determinant in F q [y] Õ(n ω ) -Solve det(M (y)) = 0 in F q .
O(n log n) -For each of the ℓ roots, solve an n × n linear system O(ℓn ω ) -Check if any solution vanishes the quadratic system O(ℓn 2 ) Denote ℓ the expected number of rational roots of a univariate polynomial Q of degree n in F q . By [START_REF] Fulman | A generating function approach to counting theorems for squarefree polynomials and maximal tori[END_REF], if Q is square-free, we have:

ℓ = n-2 i=0 - 1 q i ≤ 1
1 Precomputing this determinant as a multivariate polynomial in y does not seem to be a good idea because of its very large size -even evaluating it will be costly with n m-1 monomials.

which tends to q q+1 when n tends to infinity. We are interested in the roots of det(M (y)), therefore if it is not square-free, we consider without loss of generality its square-free part, which has degree less than n. In this case, we still upper bound the expected number of rational roots ℓ by 1. This gives the following complexity for each guess:

O(mn 2 )
Assuming S is non-zero, the expected complexity of computing singular points enumeratively is:

C(q, n, m) = O( q m-1 S mn 2 ) (9)
Kipnis-Shamir attack. The Kipnis-Shamir attack computes singular points in the intersection of two quadrics that share a large isotropic subspace. This observation is due to Luyten [START_REF] Luyten | Understanding Kipnis Shamir with two quadrics[END_REF], and Beullens and Castryck (private communication, July 2023). We can derive the same result with the tools introduced earlier. The Kipnis-Shamir attack studies the characteristic polynomial of the matrix P -1 m M , where M is a random linear combinations of public key matrices

M = m-1 i=1 y i P i . Lemma 3. Assume P m is invertible. If x is an eigenvector of P -1 m m-1
i=1 y i P i , then Jac P (x) has a rank defect.

Proof. Let χ P -1

m M be the characteristic polynomial of P -1 m M .

χ P -1 m M (λ) = det(P -1 m M -λI) Therefore: det(P m ) • χ P -1 m M (λ) = det(M -λP m )
In the previous section, we solved det(M -λP m )(y) = 0 to compute y r . This shows that eigenvectors of P -1 m M associated to an eigenvalue λ 0 induce a rank defect in Jac P by Equation [START_REF] Cox | Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF], and an associated element of the left kernel of Jac P is (y 1 , . . . , y m-1 , -λ 0 ).

⊓ ⊔

In particular, this shows that if an eigenvector of P -1 m M lies in the variety V(I), then by Hypothesis 1, it must lie in O.

To obtain the cost of the Kipnis-Shamir attack, the following hypothesis is used in [18, Note above Theorem 4.2].

Hypothesis 2 Among a collection of q n-2m distinct linear maps of the form P -1 j M , the number of eigenspaces of dimension 1 that lie in O is at least 1.

Since each eigenspace included in O corresponds exactly to a single singular point of the variety, this hypothesis allows for an estimate of S, such that Equation ( 9) matches the complexity of the Kipnis-Shamir attack:

C(q, n, m) = O(q n-2m mn 2 ) ( 10
)
Note that in the litterature this cost is identified as O(q n-2m n ω ) by neglicting the cost of summing m n × n square matrices, but this is a negligible difference for current UOV parameters.

In conclusion, an enumerative approach to the computation of singular points provides an algebraic interpretation of the Kipnis-Shamir attack from [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF]. Furthermore, we highlight two hypotheses used in the original Kipnis-Shamir attack of [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF], and reproduce the experiments of [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF] in low dimension in a new algebraic framework. This also shows that the Kipnis-Shamir attack fails when n ≥ 3m by Theorem 1.

We point out that the algebraic approach has an advantage over the Kipnis-Shamir attack: under Hypothesis 1, it does not fail if no rational singular points exist. In the next section, we use the properties of this algebraic formulation to study the security of schemes derived from UOV.

4 Application to UOV + and VOX VOX [START_REF] Cogliati | Vox-sign[END_REF] is a signature scheme submitted to the first round of the NIST call for additional signatures. It relies on the same core principles as UOV, but adds random quadratic equations to the public key. These equations are used to hide the structure of the UOV trapdoor in the form of "noise" by mixing them with the UOV public key equations. This is the "hat plus" (noted +) transform [START_REF] Faugère | A new perturbation for multivariate public key schemes such as hfe and uov[END_REF]. This allows the signer to use smaller parameters at the cost of solving a polynomial system for each signature instead of a linear system. VOX also relies on an additional structure, the Quotient Ring (QR) transform [START_REF] Furue | A new variant of unbalanced oil and vinegar using quotient ring: Qr-uov[END_REF], which is akin to the construction of structured lattices.

Definition of UOV

+

We dismiss this additional structure for now, and work in the general case: we consider that the VOX secret matrices are dense and random instead of structured. This is equivalent to working directly on UOV + or Full-VOX (FOX, introduced in the same specification), by multiplying the parameters o, v by the "QR factor" c. Note that VOX uses prime fields with q > 2.

A UOV + key pair for parameters (o, v, t, q) is composed of a secret key (S, A, F) and a public key P, with:

-A ∈ GL o+v (F q ) -S = I t S ′ 0 I o-t , S ′ ∈ F (o-t)×t q , S ∈ GL o (F q )
-F = (F 1 , . . . , F o ) a quadratic map with F i (e j ) = 0 for i > t and j ≤ o.

-

P = S • F • A a quadratic map
Let n = o + v and let F = (F t+1 , . . . , F o ) be the underlying UOV secret key. The (truncated) UOV key pair underlying the UOV + key is ( F, A), P = F • A. These polynomials are called "oil polynomials" in analogy with "oil variables".

The "vinegar polynomials" are p 1 , . . . , p t and they define the vinegar variety

V t = {x ∈ F q n , p 1 (x) = . . . = p t (x) = 0}.
Figure 3 includes the parameter sets submitted at NIST for VOX in [START_REF] Cogliati | Vox-sign[END_REF], and new parameters following an attack on the QR transform (see [START_REF] Furue | A new security analysis against mayo and qr-uov using rectangular minrank attack[END_REF], [START_REF] Macario-Rat | Rectangular attack on vox[END_REF]). The initial VOX parameters were the parameter sets VOX I, III, V . Notice that in every case, the underlying UOV instance is unbalanced by a small term c. Fig. 3: VOX parameters in [START_REF] Cogliati | Vox-sign[END_REF] and [START_REF] Macario-Rat | Rectangular attack on vox[END_REF].

Singular points of the UOV + variety

We now apply the work of Section 3 to UOV +. The core idea is to study, as previously for UOV, how singular points of the secret key are mapped by the secret change of variables, and in turn deduce non-generic properties of the public key. In the case of UOV, all singular points of the secret key were mapped to singular points of the public key by the one-to-one map A.

In the case of UOV +, the singular locus of the underlying UOV key is intersected by the variety defined by the vinegar polynomials to obtain singular values of the public key. Still, singular values of the public system are elements of O, the UOV secret of the UOV + key. The choice of nearly-balanced parameters o ≈ v implies that singular point computations are significantly more efficient than in the case of UOV.

Theorem 2. Let P be a UOV + public key chosen uniformly at random for parameters (q, n, o, t) with n > o. Then the UOV + variety V(I) = {x ∈ F q n , P(x) = 0} has a positive dimensional singular locus. More precisely, let r ≤ o -t,

d ′ = 2o + r -n -1, d = d ′ -t:
i. If d ′ ≥ 0, the variety defined by r equations of the underlying UOV key has a singular locus of dimension d ′ .

ii. If d ≥ 0, the variety defined by r equations of the UOV + public key has a singular locus of dimension d.

Proof. We construct the Jacobian matrices of all intermediate keys to highlight the way the singular points of the secret key are mapped throughout the process. Let F ′ = (P 1 • A -1 , . . . , P t • A -1 , F t+1 , . . . , F o ). Let x ∈ O be a singular point of F, the underlying UOV secret key. We obtain, as in Theorem 1, the shape of the secret UOV + Jacobian:

Jac F ′ (x) =           1 . . . o o + 1 . . . n 1 . . . t 0 . . . 0 t + 1 . . . . . . . . . 0 . . . 0 o J 1 (x) J 2 (x)          
Since x is a singular point of F, J 2 (x) has rank at most o -t -1. Therefore, Jac F ′ (x) has rank at most o -1. We move on to the next intermediate key, and deduce the Jacobian from the chain rule:

P ′ = F ′ • A Jac P ′ (y) = Jac F ′ (Ay) • A (11)
Notice that these operations cannot increase the rank of the Jacobian matrix, and that the right product with A acts on the columns of the Jacobian.

Jac P ′ (y) =           1 . . . o o + 1 . . . n 1 . . . t t + 1 . . . o J 1 (Ay)A J 2 (Ay)A          
In particular, we have that Jac P ′ (A -1 x) has rank at most o -1. Finally, we apply the linear map S to obtain the full UOV + public key, again with the chain rule.

P = S • P ′ Jac P (y) = S • Jac P ′ (y) (12)
Again, this left product cannot increase the rank of the matrix.

Jac P (y) =           1 . . . o o + 1 . . . n 1 . . . t t + 1 . . . o J 1 (Ay)A (S ′ J 1 + J 2 )(Ay)A          
Since the rank may not increase at any step, singular points of the underlying UOV key drop the rank of the UOV + public Jacobian.

rank(Jac P (x)) ≤ rank(Jac P (x)) + t

In particular, if A -1 x also vanishes the vinegar polynomials, then A -1 x is a singular point of the full UOV + public key. We give the dimension estimates below.

i. Let J r be the ideal generated by ( P(x), Minors r (Jac P (x))). By construction, P is a truncated UOV public key with r equations which vanish on the linear subspace O of dimension o. By Theorem 1, we have:

d ′ = dim J r = 2o + r -n -1
ii. Since p 1 (x), . . . , p t (x) are random quadratic equations, we can assume they define generic hypersurfaces, and the ideal J r + ⟨p 1 (x), . . . , p t (x)⟩ has dimension dim(J r ) -t. Notice that by the previous observations, if x is a singular point of the underlying UOV key, then the Jacobian of the UOV + public system is also rank deficient. Therefore, if x is singular for the underlying UOV key and x ∈ V t , then P(x) = 0 and therefore x is singular for the UOV + public system.

⊓ ⊔

The UOV + (and VOX) security estimates rely on the idea that one cannot attack the partial UOV key without first guessing the coefficients of the S map on at least two equations, therefore multiplying the cost of any attack on the partial key by a factor q 2t . This assumption allows VOX and UOV + to use UOV parameters that would otherwise be weak to key recovery attacks.

In Theorem 2, we show that this estimate is optimistic: we target the partial UOV key by computing singular points of the UOV + key without knowing S, since the singular locus of the partial key generically intersects the vinegar variety if the quantity d ′ is non-negative. In light of Section 3.5, this proves that the Kipnis-Shamir attack directly works on the UOV + public key since it computes rational singular points of the variety generated by a collection of quadratic equations.

We use Equation [START_REF] Ding | Triangular unbalanced oil and vinegar[END_REF], which predicts the cost of the Kipnis-Shamir attack interpreted as an enumerative singular point computation, along with Hypothesis 2 to estimate the number of rational singular points. We have dim SingV(I) = 3o -n -1 -t, therefore we have the following cost for the Kipnis-Shamir attack against UOV +: C(q, n, o, t) = O(q n-2o+t on 2 ) [START_REF] Faugère | Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity[END_REF] This cost was previously identified as O q n-2o+2t n ω in [START_REF] Faugère | A new perturbation for multivariate public key schemes such as hfe and uov[END_REF], [START_REF] Cogliati | Vox-sign[END_REF], which we improve by a factor q t . We give below log 2 (field operations) estimates, using ω = 2.81. We add the previous best attacks that target UOV + and the Full VOX key, as described in [START_REF] Faugère | A new perturbation for multivariate public key schemes such as hfe and uov[END_REF], [START_REF] Cogliati | Vox-sign[END_REF]. Multiplication cost is taken to be 2 log(q) 2 + log(q) gates. In [START_REF] Cogliati | Vox-sign[END_REF], costs were given in number of arithmetic operations, therefore we use the previous cost to convert to gate counts, as per NIST methodology. Fig. 4: Computational cost of our version of the Kipnis-Shamir attack on VOX parameters submitted to NIST [START_REF] Cogliati | Vox-sign[END_REF].

We consider the cost of the attack on the original UOV + parameters. This scheme is not concerned by the rectangular MinRank attack of [START_REF] Furue | A new security analysis against mayo and qr-uov using rectangular minrank attack[END_REF]. As this paper was used as a foundation for VOX, it is not surprising that the cost is almost equal. New parameters for VOX have been proposed in [START_REF] Macario-Rat | Rectangular attack on vox[END_REF], to protect the QR transform used in the scheme. We give an analysis of our attack against these parameters in Figure 6. In the next section, we show how to recover the rest of the secret key using a single secret vector. This will also highlight a method to lower the complexity of attacks against UOV + independently of improvements to the Kipnis-Shamir attack against UOV.

Key recovery from one vector against UOV

+

Once we have obtained a vector in O, we wish to complete a full key recovery attack. A polynomial-time key recovery from one vector against UOV is introduced in [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF], by studying the kernel of the Jacobian of the system evaluated on an element of the secret subspace. In [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF]Section 4], these tools are applied to VOX, interpreted as UOV +: the underlying UOV public key may be targeted once the map S is inverted. Using t vectors of the UOV secret key, one inverts the map by solving a linear system. The author concludes that the method does not apply out of the box, and instead requires t vectors of O to break the scheme.

In this section, we show that [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF]Theorem 7] may be generalized to UOV + without inverting S, and thus show how to perform a key recovery against UOV + and VOX using a single oil vector.

Lemma 4. Let P = (P 1 , . . . , P m ) be a UOV + public key for parameters (q, o, v, t), let O be the associated UOV secret subspace, let V t = {x ∈ F q , p 1 (x) = . . . = p t (x)} be the vinegar variety of P. If x ∈ O, then ker(Jac P (x)) ∩ O has dimension at least o -t as a linear subspace.

Proof. Recall that

Jac P (x) =   
x T P 1 . . .

x T P o   
Furthermore, by definition of S the chain rule yields:

Jac P (x) = S • Jac P (x)
Since S is injective, the right kernels of Jac P (x) and Jac P (x) are equal. The observation of [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF] is that

O ⊂ ker    x T Pt+1 . . . x T Po   
is entirely included in O. This value is greater than t, and therefore this yields a free family of vectors of O that allows to retrieve S using the method presented in [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF], and therefore yields the remaining vectors required to form a basis of O in polynomial time.

Let us look at the complexity of this process:

1. Compute B a basis of ker(Jac

P (x)) O(n ω ) 2. Compute P t+1|B O(n ω ) 3. Find (s t+1,j ) 1≤j≤t O(q t n ′ω ) 4. Invert S O(n ω ) 5. Retrieve O O(n ω )
The total cost is dominated by O (q t (n -o)n ′ω ).

⊓ ⊔

Notice that the MinRank instance presented in the proof of Theorem 3 is solved very naively. Let T (q, n, o, t) be the cost of solving this MinRank instance. This work provides the upper bound T (q, n, o, t) < q t (n -o + 1) ω . Notice that this yields a test "x ∈ O?" with the same complexity: if there exists t+1 ≤ i ≤ o such that no family (s i,j ) j can be found, then x ̸ ∈ O, otherwise x ∈ O.

For larger field sizes, we may improve the complexity by solving this MinRank instance using a Gröbner basis approach.

Combining singular point computations with "x ∈ O?"

By combining our study of the singular points from Section 4.2 with the one vector key recovery from Section 4.3, we can obtain a novel attack on UOV + and VOX.

The Kipnis-Shamir attack computes vectors that drop the rank of the Jacobian of a UOV public key among eigenvector of some linear maps. For each such vector x, it checks whether P(x) = 0, in which case the attacker concludes that they have computed a point of O.

For UOV +, vectors of O do not vanish the public key equations. Therefore, we may replace this step of the attack by using the key recovery from one vector (Theorem 3) as a test "x ∈ O?". In this case, we pay a factor T (q, n, o, t) for each point computed: these points are among the points that drop the rank of the public Jacobian by Theorem 2. This yields a more obvious separation between the cost of attacking the + transformation versus the security of the underlying UOV key:

O q n-2o on 2 × T (q, n, o, t)

The first part of the formula corresponds to the security of UOV against the Kipnis-Shamir attack, while the second part is the cost of solving a MinRank instance that is related to the + transform. Compared with the Kipnis-Shamir attack described in Section 4.2, this is only worse by a polynomial factor (no + 1) ω using the algorithm introduced in Section 4.3. Any improvement to the key recovery from one vector would yield improved complexity for this attack.

Consequences for UOV + and VOX

We have shown that the hat plus structure only improves the security of UOV by a factor at most q t asymptotically against the Kipnis-Shamir attack, as opposed to the factor q 2t claimed in [START_REF] Cogliati | Vox-sign[END_REF]. The new VOX parameters introduced in [START_REF] Macario-Rat | Rectangular attack on vox[END_REF] for VOX increase the value c, which is directly equal to n -2o, compared with the previous parameter sets. Therefore, even though this change was made to protect the QR transform, it significantly improves the security of the scheme against our attacks as well.

Experimental results

We verified our results on the singular locus of the UOV variety with various experiments in low dimensions (m ≤ 10) and for the field F 251 . The size of the field does not significantly affect Gröbner basis algorithms.

Dimension of the singular locus

To study the properties of the singular locus, we use the bihomogeneous modeling defined in Equation [START_REF] Cogliati | Vox-sign[END_REF]. The minors modeling is highly impractical to manipulate: computing the minors is already a hard task due to their number: n r .

We also point out that the statement of Theorem 1 is homogeneous: to obtain a useful result from a Gröbner basis algorithm, one must dehomogeneize the equations (typically done by setting x 1 = 1). In doing so, we reduce the dimension of the singular locus by one compared with the homogeneous result, as this is equivalent to intersecting the variety with an arbitrary hyperplane.

Another important remark is that Gröbner basis algorithms are efficient in the zero-dimensional case: therefore, when we expect the variety to have dimension d, we add d random linear forms in the x variables to obtain a zerodimensional variety. This is not entirely equivalent to setting d variables to arbitrary values, as in doing so one assumes that there exists a rational solution with these specific coordinates. This is essential in our case, as singular points are not always rational, but their existence (in an extension) will always allow to mount an algebraic attack against the scheme. This means that in cases where there are no rational singular points, the Kipnis-Shamir attack will fail, while our attacks will not. We demonstrate this property using the Gröbner bases computed in our experiments.

We can study experimentally the degree and dimension of the variety using the computation of a Gröbner basis. More precisely, the dimension is the degree of the denominator of the Hilbert series and the degree is the evaluation of the numerator of the series at 1.

Let P be the public key of a UOV instance for parameters n, m, q, let d = 3m -n -1 (as in Theorem 1), and choose f a collection of d -1 linear maps uniformly at random. These linear maps define the hyperplanes with which we intersect our variety. The zero-dimensional system we solve to perform a key recovery attack (without a hybrid approach) is the following:

x ∈ F n q , x 1 = 1, y ∈ F m q , y 1 = 1

     P(x) = 0 ∈ F m q y T Jac P (x) = 0 ∈ F n q f (x) = 0 ∈ F d q (14)
The dimensions obtained experimentally match Theorem 1. In every case, the Gröbner basis contains exactly n -m linear polynomials defining O, which supports Hypothesis 1.

We list in Figure 7 the results obtained on UOV systems. We provide code to reproduce our experiments.

Theorem 1

 1 Choose p 1 , . . . , p m uniformly at random among the quadratic forms generating a radical ideal I = ⟨p 1 , . . . , p m ⟩ such that V(I) contains an o-dimensional linear subspace O. Let d = 2o + m -n -1. If d ≥ 0, then the singular locus of V(I) is non-empty and its intersection with O has dimension d.

  then the singular locus of V(I) is non-empty and its intersection with O has dimension d.

Fig. 1 :

 1 Fig. 1: Cost of the singular point attack via minors modeling for UOV

Fig. 5 :

 5 Fig. 5: Computational cost of our version of the Kipnis-Shamir attack on UOV +

Fig. 6 :

 6 Fig.6: Computational cost of our version of the Kipnis-Shamir attack for VOX parameters proposed in[START_REF] Macario-Rat | Rectangular attack on vox[END_REF].

  The linear subspace O is a totally isotropic subspace of a quadratic form f if and only if for all (x, y)∈ O 2 , f * (x, y) = f * (y, x) = 0.Let (o 1 , . . . , o m ) be a basis of O, a totally isotropic subspace of f . Complete (o 1 , . . . , o m ) into B, a basis of F n q . Then a matrix representing f in basis B has the secret UOV shape:

  m,n Dimension Degree of the variety Degree of regularity Fig. 7: Experimental computation of Gröbner bases for bihomogeneous modelisations of the singularities of UOV systems in F 251 .

	4, 8	2	4	3
	4, 9	1	10	4
	4, 10	0	20	5
	5, 10	3	5	4
	5, 11	2	15	4
	5, 12	1	35	5
	5, 13	0	70	6
	6, 12	4	6	4
	6, 13	3	21	5
	6, 14	2	56	6
	6, 15	1	126	6
	6, 16	0	252	7
	7, 14	5	7	4
	7, 15	4	28	5
	7, 16	3	84	6
	7, 17	2	210	7

This kernel must but of dimension at least one by definition of a singular point, and of dimension no greater than one as the dimension of the determinatal ideal Jm-2 of the m -1 minors of the Jacobian from Theorem 1 is negative:d = m -(n -(n -m -(m -2))) (m -(m -2)) = -4 for n = 5

2 m.

Acknowledgements

The author would like to thank Simon Abelard and Mohab Safey el Din for their supervision and insightful discussions.

Therefore in our case

O ∩ ker   

x T P 1 . . .

This intersection has dimension at least o -t. By genericity of P 1 , . . . , P t , we expect this to be an equality in most cases. This concludes the proof.

⊓ ⊔

We obtain a key recovery from one vector by restricting the VOX public key to this kernel, and by considering the properties of this new UOV + instance.

Theorem 3. Let P be a UOV + public key for parameters (q, o, v, t), let O be the associated UOV secret subspace, and let x ∈ O. Then there exists an algorithm taking as input x and P and outputting a basis of O, using at most O (q t (n -o) ω ) arithmetic operations in F q .

Proof. Notice that ker(Jac P (x)) has dimension n -o for generic points, and dimension n -o + 1 for singular points. We assume that x is singular. Indeed, when x is not singular, the dimension becomes n -o and the problem is easier to solve. Let B be a basis of ker(Jac P (x)).

Following the methodology of [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF], we restrict the UOV + public key to this kernel.

We also define the restriction of the underlying UOV key for clarity:

The collection P |B = (P 1|B , . . . , P o|B ) can be considered as the public key of a generalized UOV + instance with the same number of equations o, in dimension n ′ = n -o + 1, and with an UOV trapdoor of dimension o -t by Lemma 4. Notice that P|B , the underlying UOV key, is composed only of singular matrices as n -o + 1 < 2(o -t), using Lemma 2. In particular, as observed in [START_REF] Pébereau | One vector to rule them all: Key recovery from one vector in uov schemes[END_REF], the UOV matrices Pi|B have rank r = 2 • (n -2o + t + 1), which is significantly lower than n -o + 1 for all proposed parameter sets.

Therefore, once this restriction has been computed, the attacker may determine (s i,j ) j for any fixed i by solving a MinRank instance:

Denote M (s) = P i|B + t j=1 s i,j P j|B . This MinRank instance has t variables over a matrix of dimension n ′ × n ′ and a target rank r = 2 • (n -2o + t + 1).

If we solve this instance by enumerating all values of (s i,j ) 1≤j≤t , the cost is q t (n -o + 1) ω , which achieves the announced upper bound.

Once we have found one collection (s i,j ) 1≤j≤t for some i, we obtain Pi|B , and the kernel of Pi|B has dimension n -o + 1 -2(n -2o + t + 1) = 3o -n -2t and


Jean-Michel Muller

Some algebraic properties of floating-point arithmetic

Thanks to the IEEE-754 standard, floating-point arithmetic is now a well-defined mathematical structure, on which it is possible to build proofs and algorithms. We give some examples of properties (mainly closure properties) that can be proven.

Introduction

For many years, floating-point arithmetic has been a mere set of cooking recipes. The consequences of this have sometimes been disastrous: numerical programs were not reliable nor portable. Without a clear specification of the underlying arithmetic, it was not possible to prove even simple properties of a sequence of operations, and the only way to feel comfortable with an important numerical program was to perform intensive tests.

The IEEE-754 [START_REF] Cody | A proposed radix-and-word-length-independent standard for floating-point arithmetic[END_REF][START_REF]ANSI/IEEE Standard[END_REF] standard for binary floating-point arithmetic (and the radix independent IEEE-854 [START_REF] Cody | A proposed radix and word length independent standard for floating-point arithmetic[END_REF][START_REF]Ieee standard for radix independent floating-point arithmetic. ANSI/IEEE Standard[END_REF] standard that followed) put an end to this dangerous era. The IEEE-754 standard (we will later refer to it as "the IEEE standard" or "the standard") clearly specifies the formats of the floating-point representations of numbers, and the behaviour of the four arithmetic operations.

Define F n as the set of exponent-unbounded, n-bit mantissa, binary floating-point numbers (with n ≥ 1), that is:

F n = M × 2 E , 2 n-1 ≤ M ≤ 2 n -1, M, E ∈ N ∪ {0}
F n is not the set of the available floating-point numbers on an existing system. It is an "ideal" system, with no overflows or underflows. We will show results in F n . These results will remain true in an actual systems that implement the IEEE standard, provided that no overflows or underflows occur. The mantissa of a nonzero element

M × 2 E of F n is the number m(x) = M/2 n-1 .
The result of an arithmetic operation whose input values belong to F n may not belong to F n (as a matter of fact, in general it does not). Hence that result must be rounded. The standard defines 4 different rounding modes:

• rounding towards +∞, or upwards: • u (x) is the smallest element of F n that is greater than or equal to x;

• rounding towards -∞, or downwards: • d (x) is the largest element of F n that is less than or equal to x;

• rounding towards 0: • z (x) is equal to • u (x) if x < 0, and to • d (x) otherwise;

• rounding to the nearest even: • n (x) is the element of F n that is closest to x. If x is exactly halfway between two elements of F n , • n (x) is the one for which M is an even number.

The first three rounding modes are called directed rounding modes.

The standard requires that the user should be able to choose one rounding mode among these ones, called the active rounding mode. After that, when performing one of the 4 arithmetic operations, or when computing square roots, the obtained result should be equal to the rounding of the exact result.

We will denote these "correctly rounded" operations with a circle and a letter indicating the rounding mode. For instance, when a and b belong to

F n , a ⊕ u b = • u (a + b), whereas a n b = • n (a/b).
For a ∈ F n , we define a + as its successor in F n , that is, a + = min{b ∈ F n , b > a}, and ulp(a) as |a| + -|a|. If a is not an element of F n , we define ulp(a) as • u (a) -• d (a). The name ulp is an acronym for unit in the last place. When x ∈ F n , ulp(x) is the weight of the last mantissa bit of x. We also define a -as the predecessor of a.

Floating-point reciprocals

Given a rounding mode t, we want to investigate whether an element x ∈ F n has an FPreciprocal (Floating-Point reciprocal) for ⊗ t , that is, whether there exists z ∈ F n such that x ⊗ t z = • t (xz) = 1. From the obvious properties:

x ∈ F n , k ∈ Z ⇒ x2 k ∈ F n λ ∈ R, k ∈ Z ⇒ • t (λ2 k ) = 2 k • t (λ) x, z ∈ F n , k ∈ Z, x ⊗ t z = 1 ⇒ (x2 k ) ⊗ t (z2 -k ) = 1
we can assume that 1 ≤ x < 2 (that is, it suffices to focus on reciprocals of the mantissas of the elements of F n ). Before looking for FP-reciprocals, one can try to investigate whether the "true" reciprocal of a given element of F n may belong to F n (or some other set F q ). The answer, given by the following lemma, is quite straightforward.

Lemma 1 Let x ∈ F n . There exists q ∈ N, q ≥ 1 such that 1/x belongs to F q if and only if x is a power of 2.

Proof. The above remarks show that it suffices to assume that 1 ≤ x < 2. Define y = 1/x and assume y ∈ F q . This gives:

• X = 2 n-1 x ∈ N; • Y = 2 p y ∈ N (since 1/2 < y ≤ 1).
The integer XY is equal to 2 n+p-1 . Therefore, in the prime number decomposition of X and Y , 2 is the only prime number that can appear.

Directed rounding modes 1.Unicity of FP-reciprocals

In general, an element of F n may have more than one FP-reciprocal. Consider x = 27/16, and the two values z 1 = 19/32 and z 2 = 5/8. All these values belong to F 5 , and

x ⊗ d z 1 = x ⊗ d z 2 = 1.
Property 1 For any directed rounding mode, an element of F n has at most 2 reciprocals. Assuming rounding towards +∞ (⊗ u ), a nonnegative number has at most one FP-reciprocal.

Proof.

Assume x ∈ F n , 1 < x < 2 (the case x = 1 is obvious, since x is its own unique FP-reciprocal in any rounding mode). Define y = 1/x, and

z 1 = • d (y) z 2 = • u (y).
We have:

1/2 < y < 1 1/2 ≤ z 1 ≤ 1 -2 -n 1/2 + 2 -n ≤ z 2 ≤ 1
Let us first assume rounding towards 0, or downwards. It is worth noticing that, since x = 1, z 1 < y. Hence for any z ∈ F n that is less than or equal to

z 1 , z ⊗ d x = • d (z × x) ≤ z × x < xy = 1. Now, consider the case z ≥ z + 2 + . The number z + 2 + is greater than or equal to z 2 + 2 -n+1 (it can be larger if z 2 = 1 or z + 2 = 1). Therefore: xz ≥ xz 2 + x2 -n+1 ≥ xy + 2 -n+1 = 1 + ulp(1) ∈ F n . Hence x ⊗ d z = • d (xz) ≥ 1 + 2 -n+1 .
Now, let us assume rounding towards +∞, or upwards. Quite obviously (same reasoning as for z 1 and • d ), for any z ∈ F n that is greater than or equal to z 2 , z ⊗ u z > 1. Now, consider a number z ∈ F n that is less than or equal to z - 1 . Two cases may occur:

• if z 1 > 1/2, then z - 1 = z 1 -2 -n . In such a case, xz ≤ xz 1 -x2 -n ≤ xy -2 -n = 1 -2 -n ∈ F n . Hence, x ⊗ z ≤ 1 -2 -n ; • if z 1 = 1/2 then, since xz 1 ∈ F n , we have x ⊗ u z 1 = xz 1 < xy, since we have assumed y = 1/2;
Hence, the only element of F n that may be an FP-reciprocal of x is z 1 .

Existence of FP-reciprocals

Property 2 Every nonnegative element of F n has a FP-reciprocal in F n for ⊗ u .

An immediate consequence of this property is that every nonpositive element of F n has a FP-reciprocal in F n for ⊗ d .

Proof. Let x ∈ F n , x > 0. We have to find z ∈ F n such that x ⊗ d z = 1. We assume 1 ≤ x ≤ 2. Define y = 1/x (y is a real number, it does not necessarily belong to F n ), and consider z = • u (y). From 1/2 < y ≤ 1, since the roundings are monotonic functions, and since 1/2 and 1 belong to F n (and therefore are equal to their own roundings, for any of the 4 rounding modes), we deduce 1/2 < z ≤ 1. Two cases may occur:

• if z = 1, this means that 1 -2 -n < y ≤ 1. Hence, 1 ≤ x < 1 + 2 -n + 2 -2n + 2 -3n + . . . ≤ 1 + 2 -n+1 = 1 + ulp(1) = 1 + . From x ∈ F n and 1 ≤ x < 1 + , we deduce x = 1. Therefore x ⊗ d z = • d (1 × 1) = 1;
• if z < 1, then the binary representation of z has the form 0.z 1 z 2 . . . z n , and we have:

y ≤ z < y + 2 -n . Thus 1 ≤ xz < 1 + x2 -n < 1 + 2 -n+1 .
This implies

• d (1) = 1 ≤ x ⊗ d z < • d (1 + 2 -n+1 ) = 1 + , therefore x ⊗ d z = 1.

Rounding to the nearest 1.2.1 Unicity of FP-reciprocals

In rounding to the nearest mode, a number may have more than one FP-reciprocal. Consider for instance x = 3/2, as an element of F 5 . The two following elements of F 5 , z 1 = 21/32 and z 2 = 11/16 satisfy x ⊗ n z 1 = x ⊗ z 2 = 1. This is the maximum number of FP-reciprocals a number can have.

Property 3

In rounding to the nearest mode, the only numbers that can be FP-reciprocals

of x ∈ F n are • d (1/x) and • u (1/x).
The proof is ommitted, since it is very similar to the proof of the corresponding property for the directed roundings.

Existence of FP-reciprocals

It is worth noticing that some elements of F n do not have an FP-reciprocal for ⊗ n . An exhaustive test shows that if n ≤ 5, all elements of F n have an FP-reciprocal. The only element of F 6 between 1 and 2 with no FP-reciprocal is 29/16 = 1.11010. Hence all elements of F 6 with no reciprocals have the form 29 × 2 k , k ∈ Z. The only element of F 7 between 1 and 2 with no FP-reciprocal is 59/32. Table 1 gives the number γ(n) of elements of F n between 1 and 2 with no FP-reciprocal for small values of n.

Although the problem seems more complicated than for directed rounding modes, we can anyway give a conjecture and a few results.

Conjecture 1

The proportion γ(n)/2 n-1 of elements of F n without a FP-reciprocal converges toward 1: Number γ(n) of elements of F n between 1 and 2 with no FP-reciprocal (for ⊗ n ), for small values of n. We also give the proportion γ(n)/2 n-1 of elements of F n without a FP-reciprocal. We conjecture that this proportion converges toward 1 2 -3 2 log(4/3) = 0.06847689 . . . The idea behind the conjecture is the following: saying that y ∈ F n , 1 ≤ y < 2 has no reciprocal for ⊗ n is equivalent1 to saying that there is no z

∈ F n such that yz ∈ [1 - 2 -n-1 , 1 + 2 -n ].
This means, if we define integers Y = y2 n-1 and Z = z2 n that Y Z is not in the interval [2 2n-1 -2 n-2 , 2 2n-1 + 2 n-1 ], i.e., that 2 2n-1 + 2 n-1 = Y Z + ρ, where ρ is not in [0, 2 n-2 + 2 n-1 ]. A value y ∈ F n without a reciprocal therefore corresponds to an integer Y ∈ [2 n-1 , 2 n ] such that 2 2n-1 + 2 n-1 modulo Y is larger than 3 × 2 n-2 . There is obviously no such Y that is less than 3 × 2 n-2 . For larger values, assuming that the "probability" 2 of having 2 2n-1 + 2 n-1 modY = k is 1/Y , we can approximate the number of values without reciprocal by:

2 n k=2 n-1 +2 n-2 Y -3.2 n-2 Y = 2 n-2 + 1 -3.2 n-2 2 n k=3.2 n-2 1/Y.
By approximating the last sum by log(2 n ) -log(3.2 n-2 ) = 2 log(2) -log(3), we get the conjecture.

Property 4 Every element of F n whose absolute value of the mantissa is between 1 and 3/2 has a FP-reciprocal in F n for ⊗ n .

This property is immediately deducible from the sentence "There is obviously no such Y that is less than 3 × 2 n-2 " in the justification of Conjecture 1.

Division and reciprocation algorithms

We aim at being able to retreive correctly rounded quotients from approximations of them (obtained for instance using Newton-Raphson or Goldschmidt iterations). We assume that the "fused multiply-and-accumulate", MAC function is available with correct rounding, i.e. that we are able to compute, from three elements a, b and c of F n , the number •(ab + c), where • is any of the four rounding modes, the following results are presented in [START_REF] Cornea-Hasegan | Correctness proofs outline for newton-raphson based floating-point divide and square root algorithms[END_REF].

Theorem 1 (Cornea-Hasegan, Golliver and Markstein, 1999

) Let x ∈ F n , let z ∈ {• d (1/x), • u (1/x)}.
We assume that x is not a power of 2. The following calculations (requiring fused MACs only)

= • n (1 -xz) z = • n (z + z) gives a value z equal to • n (1/x).
Theorem 2 (Cornea-Hasegan, Golliver and Markstein, 1999

) Let x, y ∈ F n , let z = • n (1/x), let q ∈ {• d (y/x), • u (y/x)}.
The following calculations (requiring fused MACs only)

r = • n (y -xq) q * = • n (q + rz)
gives a value q * equal to • n (y/x).

These two theorems allow to get correctly rounded quotients from the result of a Newton-Raphson iteration that approximates 1/x. Some other iterations (such as the Goldschmidt iteration) directly compute a quotient a/b, without the preliminary computation of a reciprocal.

Kahan [START_REF] Kahan | Lecture notes on the status of IEEE-754[END_REF] explains that the fused MAC allows to compute remainders exactly. Let us show how it works. Let a, b, q ∈ F n , such that q ∈ {• d (a/b), • u (a/b)} .

Without loss of generality, we assume 1 ≤ a < 2 1 ≤ b < 2 Define q * = • n (a/b).

Property 5 q * can be computed as follows.

1. compute r = • n (a -bq). Define an integer

K = n + 1 if q ≤ 1 n if q > 1 2. get q * =    q -if r < -2 -K b q + if r > 2 -K b q otherwise
Proof It suffices to notice that r is a multiple of 2 -n-K+2 that is less than 2 -K+1 b. This suffices to show that r ∈ F n . Hence, it is computed exactly.

Conclusion

We have given some examples of properties that one can show using the correct rounding property of good floating point arithmetic implementations. Such properties allow to derive algorithms and proofs.

By neglecting the case when a value is exactly the middle of two consecutive elements of F n , but we can easily show that this case never occurs.

Of course, there is a serious lack of rigor here. This is not a proof, just a quick justification of the conjecture.


domain: sdv shs spi

text:
Food is a right, a commons next to a

What is the Partnership SFS about?

its Food System actors collectively strive to achieve environmentally-friendly, socially secure and fair, economically viable, healthy and safe food systems in Europe, in order to help realise its goals of the Farm to Fork strategy, in line with the global ambitions of United Nations (UN) Sustainable Food Summit 2021. The food environment, and citizens are in the core

But, what is the food environment?

• The school canteen, restaurant,…?

• The food exhibition, fair,… ?

• The food valley, region, country, EUwide, global?

(Interacting) playing fields and role(s) to play are crucial in all FS approaches 70+ case studies in FOODPathS: And, which roles play citizens?

• civilian, consumer, employee in food handling, politician, legislator, financer, medical doctor, philanthropist, scientist, educator, innovator, student, journalist, ….?

  www.foodpaths.eu The HorizonEurope Project 'FOODPathS' supports the development of this Partnership by giving a voice & space to different actors (citizens in their different roles) in their divers environments (European CSA Project no. 101059497, 17 partners representing 19 networks (local, regional, national, European, global, public-private, philanthropic, research, education, innovation, communication, management) Vertical Horizontal What? > The Focus areas of the future P-SFS (from a food systems lens; post farming & fishing oriented) TF3 -Change the way we connect (act) citizens and food production TF4 -Change the way we govern the food systems TF2 -Change the way we process and supply TF1 -Change the way (what) we eat TF7 -FS knowledge hub of FS Labs TF8 -Knowledge sharing and scaling TF6 -FS observatory, data, methods TF5 -Co-funding and Programming https://scareurope.org/images/FOOD/Main_actions/SFS_Partnership_SRIA_31012023.pdf