A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes

An Braeken; Christopher Wolf; Bart Preneel

Paper 2004/222

A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes

An Braeken, Christopher Wolf, and Bart Preneel

Abstract

The Unbalanced Oil and Vinegar scheme (UOV) is a signature scheme based on multivariate quadratic equations. It uses $m$ equations and $n$ variables. A total of $v$ of these are called ``vinegar variables". In this paper, we study its security from several points of view. First, we are able to demonstrate that the constant part of the affine transformation does not contribute to the security of UOV and should therefore be omitted. Second, we show that the case is particularly vulnerable to Gröbner basis attacks. This is a new result for UOV over fields of odd characteristic. In addition, we investigate a modification proposed by the authors of UOV, namely to chose coefficients from a small subfield. This leads to a smaller public key. But due to the smaller key-space, this modification is insecure and should therefore be avoided. Finally, we demonstrate a new attack which works well for the case of small . It extends the affine approximation attack from Youssef and Gong against the Imai-Matsumoto Scheme~B for odd characteristic and applies it against UOV. This way, we point out serious vulnerabilities in UOV which have to be taken into account when constructing signature schemes based on UOV.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. This is an extended version of the article with the same title published at CT-RSA 2005 --- The Cryptographer's Track at RSA Conference 2005, Lecture Notes in Computer Science, volume 3376. Alfred J. Menezes, editor, Springer, 2005.
Keywords: UOV Multivariate Cryptography Cryptanalysis Linear Approximation
Contact author(s): Christopher Wolf @ esat kuleuven ac be
History: 2005-08-06: last of 3 revisions; 2004-09-03: received; See all versions
Short URL: https://ia.cr/2004/222
License: CC BY

BibTeX

@misc{cryptoeprint:2004/222,
      author = {An Braeken and Christopher Wolf and Bart Preneel},
      title = {A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/222},
      year = {2004},
      url = {https://eprint.iacr.org/2004/222}
}