Commence le
Finit le
Europe/Paris
Abstract. Unbalanced Oil and Vinegar (UOV) is a trapdoor signature scheme based on polynomial equations introduced in 1999 by Kipnis, Patarin and Goubin, featuring small signature sizes and fast algorithms.
The UOV key recovery problem can be formulated in the following way: find a large linear subspace in a complete intersection defined by degree two polynomials.
The geometric properties we exhibit are naturally translated into algebraic problems, which can be solved using efficient linear algebra and Gröbner bases algorithms.
As an example, we show that the varieties defined by the public keys of UOV schemes admit large singular locii.
These singularities enable us to introduce new algebraic attacks against UOV-based schemes, and to re-interpret the Kipnis-Shamir attack in an algebraic framework.
These attacks lower the security of UOV\hp and VOX showing in particular that the parameters sets proposed for these schemes do not meet the NIST security requirements.
At level V, we show that the security falls short by a factor of $2^{29}$ logical gates.
If time allows, we will also present on-going works motivated by the Debarre and Manivel bound regarding the maximal dimension of linear subspaces included in generic complete intersections.
