Cryptology ePrint Archive: Report 2009/483

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\"obner bases of several modified systems rather than a Gr\"obner 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.

Category / Keywords: public-key cryptography / public-key cryptography / Cryptanalysis, Multivariate Cryptography, Gr\"obner basis, F5

Date: received 29 Sep 2009

Contact author: ludovic perret at lip6 fr

Available format(s): PDF | BibTeX Citation

Version: 20091005:120355 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]