International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Stanislav Bulygin
Albrecht Petzoldt
Johannes Buchmann
Download:
URL: http://eprint.iacr.org/2010/420
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2010-23321,
  title={Towards provable security of the Unbalanced Oil and Vinegar signature scheme under direct attacks},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Multivariate Cryptography, UOV Signature Scheme, provable security, security reduction, semi-regular sequence},
  url={http://eprint.iacr.org/2010/420},
  note={ Stanislav.Bulygin@cased.de 14819 received 29 Jul 2010},
  author={Stanislav Bulygin and Albrecht Petzoldt and Johannes Buchmann},
  year=2010
}