[Resource Topic] 2004/222: A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes

Welcome to the resource topic for 2004/222

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

Authors: An Braeken, Christopher Wolf, Bart Preneel


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 n \geq 2m 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 v.
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.

ePrint: https://eprint.iacr.org/2004/222

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .