Geometric approach to the cryptanalysis of UOV

We present results concerning the security of post-quantum multivariate signature schemes based on UOV, in particular those submitted to NIST.

We motivate our approach by a geometric interpretation of the trapdoor, based on the work of Kipnis and Shamir and more recently by Beullens.

The geometric properties we exhibit are naturally translated into algebraic problems, which can be solved using standard algebraic cryptanalysis tools,

such as efficient linear algebra and Gröbner basis 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.

Our 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.

We also present on-going work with S. Abelard and M. Safey el Din enabling a generic analysis of the polynomial systems arising in the study of UOV.