### Towards provable security of the Unbalanced Oil and Vinegar signature scheme under direct attacks

Stanislav Bulygin, Albrecht Petzoldt, and Johannes Buchmann

##### Abstract

In this paper we show that solving systems coming from the public key of the Unbalanced Oil and Vinegar (UOV) signature scheme is on average at least as hard as solving a certain quadratic system with completely random quadratic part. In providing lower bounds on direct attack complexity we rely on the empirical fact that complexity of solving a non-linear polynomial system is determined by the homogeneous part of this system of the highest degree. Our reasoning explains, in particular, the results on solving the UOV systems presented by J.-C. Faugere and L. Perret at the SCC conference in 2008.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Multivariate CryptographyUOV Signature Schemeprovable securitysecurity reductionsemi-regular sequence
Contact author(s)
Stanislav Bulygin @ cased de
History
Short URL
https://ia.cr/2010/420

CC BY

BibTeX

@misc{cryptoeprint:2010/420,
author = {Stanislav Bulygin and Albrecht Petzoldt and Johannes Buchmann},
title = {Towards provable security of the Unbalanced Oil and Vinegar signature scheme under direct attacks},
howpublished = {Cryptology ePrint Archive, Paper 2010/420},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/420}},
url = {https://eprint.iacr.org/2010/420}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.