Paper 2011/294

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

Albrecht Petzoldt, Enrico Thomae, Stanislav Bulygin, and Christopher Wolf

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
MQMultivariate QuadraticUOVUnbalanced Oil and Vinegar
Contact author(s)
chris @ christopher-wolf de
History
2011-06-03: revised
2011-06-03: received
See all versions
Short URL
https://ia.cr/2011/294
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/294,
      author = {Albrecht Petzoldt and Enrico Thomae and Stanislav Bulygin and Christopher Wolf},
      title = {Small Public Keys and Fast Verification for Multivariate Quadratic Public Key Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2011/294},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/294}},
      url = {https://eprint.iacr.org/2011/294}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.