TU Darmstadt / ULB / TUbiblio

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

Bulygin, Stanislav and Petzoldt, Albrecht and Buchmann, Johannes
Gong, G. and Gupta, K. C. (eds.) (2010):
Towards provable security of the Unbalanced Oil and Vinegar signature scheme under direct attacks.
In: Proceedings of IndoCrypt 2010, Springer, In: Lecture Notes in Computer Science, 6498, [Conference or Workshop Item]

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.

Item Type: Conference or Workshop Item
Erschienen: 2010
Editors: Gong, G. and Gupta, K. C.
Creators: Bulygin, Stanislav and Petzoldt, Albrecht and Buchmann, Johannes
Title: Towards provable security of the Unbalanced Oil and Vinegar signature scheme under direct attacks
Language: ["languages_typename_1" not defined]
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.

Title of Book: Proceedings of IndoCrypt 2010
Series Name: Lecture Notes in Computer Science
Volume: 6498
Publisher: Springer
Uncontrolled Keywords: Secure Data;Multivariate Cryptography, UOV Signature Scheme, provable security, security reduction, semi-regular sequence
Divisions: LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
LOEWE > LOEWE-Zentren
20 Department of Computer Science
LOEWE
Date Deposited: 30 Dec 2016 20:23
Identification Number: TUD-CS-2010-0230
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item