### On the Security of UOV

Jean-Charles Faugère and Ludovic Perret

##### Abstract

In this short note, we investigate the security of the Unbalanced Oil and Vinegar Scheme \cite{uov}. 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
public-key cryptographyCryptanalysisMultivariate CryptographyGröbner basisF5
Contact author(s)
ludovic perret @ lip6 fr
History
Short URL
https://ia.cr/2009/483

CC BY

BibTeX

@misc{cryptoeprint:2009/483,
author = {Jean-Charles Faugère and Ludovic Perret},
title = {On the Security of UOV},
howpublished = {Cryptology ePrint Archive, Paper 2009/483},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/483}},
url = {https://eprint.iacr.org/2009/483}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.