TU Darmstadt / ULB / TUbiblio

Small Public Keys and Fast Verification for Multivariate Quadratic Public Key Systems

Petzoldt, Albrecht and Thomae, Enrico and Bulygin, Stanislav and Wolf, Christopher
Preneel, Bart and Takagi, Tsuyoshi (eds.) (2011):
Small Public Keys and Fast Verification for Multivariate Quadratic Public Key Systems.
In: Proceedings of "Workshop on Cryptographic Hardware and Embedded Systems 2011 (CHES 2011)", Springer, In: Lecture Notes in Computer Science, [Conference or Workshop Item]

Abstract

Security of public key schemes in a post-quantum world is a challenging task as both RSA and ECC will be broken then. In this paper, we show how post-quantum signature systems based on Multivariate Quadratic (MQ) polynomials can be improved up by about 9/10, and 3/4, respectively, in terms of public key size and verification time. The exact figures are 88% and 73%. This is particularly important for small-scale devices with restricted energy, memory, or computational power. In addition, we show that this reduction does not affect security and that it is also optimal in terms of possible attacks. We do so by combining the priory unrelated concepts of reduced and equivalent keys. Our new scheme is based on the so-called Unbalanced Oil and Vinegar class of MQ-schemes. We have derived our results mathematically and verified the speed-ups through a C++ implementation.

Item Type: Conference or Workshop Item
Erschienen: 2011
Editors: Preneel, Bart and Takagi, Tsuyoshi
Creators: Petzoldt, Albrecht and Thomae, Enrico and Bulygin, Stanislav and Wolf, Christopher
Title: Small Public Keys and Fast Verification for Multivariate Quadratic Public Key Systems
Language: ["languages_typename_1" not defined]
Abstract:

Security of public key schemes in a post-quantum world is a challenging task as both RSA and ECC will be broken then. In this paper, we show how post-quantum signature systems based on Multivariate Quadratic (MQ) polynomials can be improved up by about 9/10, and 3/4, respectively, in terms of public key size and verification time. The exact figures are 88% and 73%. This is particularly important for small-scale devices with restricted energy, memory, or computational power. In addition, we show that this reduction does not affect security and that it is also optimal in terms of possible attacks. We do so by combining the priory unrelated concepts of reduced and equivalent keys. Our new scheme is based on the so-called Unbalanced Oil and Vinegar class of MQ-schemes. We have derived our results mathematically and verified the speed-ups through a C++ implementation.

Title of Book: Proceedings of "Workshop on Cryptographic Hardware and Embedded Systems 2011 (CHES 2011)"
Series Name: Lecture Notes in Computer Science
Volume: 6917
Publisher: Springer
Uncontrolled Keywords: Secure Data;Multivariate Quadratic Cryptography, Post-Quantum Cryptography, Implementation, Unbalanced Oil and Vinegar Signature Scheme
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra > Post-Quantum Cryptography
LOEWE > LOEWE-Zentren
20 Department of Computer Science
LOEWE
Date Deposited: 30 Dec 2016 20:23
Identification Number: TUD-CS-2011-0160
Export:

Optionen (nur für Redakteure)

View Item View Item