Paper 2004/361

Superfluous Keys in Multivariate Quadratic Asymmetric Systems

Christopher Wolf and Bart Preneel

Abstract

In this article, we show that public key schemes based on multivariate quadratic equations allow many equivalent, and hence superfluous private keys. We achieve this result by investigating several transformations to identify these keys and show their application to Hidden Field Equations (HFE), C$^*$, and Unbalanced Oil and Vinegar schemes (UOV). In all cases, we are able to reduce the size of the private --- and hence the public --- key space by at least one order of magnitude. We see applications of our technique both in cryptanalysis of these schemes and in memory efficient implementations.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Multivariate Quadratic EquationsPublic Key SchemesEquivalent Keys
Contact author(s)
christopher wolf @ esat kuleuven ac be
History
2005-01-28: revised
2004-12-16: received
See all versions
Short URL
https://ia.cr/2004/361
License
Creative Commons Attribution
CC BY

BibTeX

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