Paper 2005/464

Equivalent Keys in Multivariate Quadratic Public Key Systems

Christopher Wolf and Bart Preneel

Abstract

Multivariate Quadratic public key schemes have been suggested back in 1985 by Matsumoto and Imai as an alternative for the RSA scheme. Since then, several other schemes have been proposed, for example Hidden Field Equations, Unbalanced Oil and Vinegar schemes, and Stepwise Triangular Schemes. All these schemes have a rather large key space for a secure choice of parameters. Surprisingly, the question of equivalent keys has not been discussed in the open literature until recently. In this article, we show that for all basic classes mentioned above, it is possible to reduce the private --- and hence the public --- key space by several orders of magnitude. For the Matsumoto-Imai scheme, we are even able to show that the reductions we found are the only ones possible, i.e., that these reductions are tight. While the theorems developed in this article are of independent interest themselves as they broaden our understanding of Multivariate Quadratic public key systems, we see applications of our results both in cryptanalysis and in memory efficient implementations of MQ-schemes.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Multivariate QuadraticEquivalent Keys
Contact author(s)
Christopher Wolf @ ens fr
History
2005-12-31: received
Short URL
https://ia.cr/2005/464
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/464,
      author = {Christopher Wolf and Bart Preneel},
      title = {Equivalent Keys in Multivariate Quadratic Public Key Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2005/464},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/464}},
      url = {https://eprint.iacr.org/2005/464}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.