Title: A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes
Authors: Braeken, A
Wolf, Christopher
Preneel, Bart
Issue Date: 2005
Publisher: Springer-Verlag
Host Document: Lecture Notes in Computer Science vol:3376 pages:29-43
Conference: CT-RSA 2005 date:February 14-18, 2005
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 n >= 2m is particularly vulnerable to Grobner 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.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IC
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics

Files in This Item:
File Status SizeFormat
article-555.pdf Published 241KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science