On the Security of UOV
Jean‐Charles Faugère, Ludovic Perret · 2008
Abstract. In this short note, we investigate the security of the Unbalanced Oil and Vinegar Scheme [15]. 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. 1.