Paper 2004/360

Equivalent Keys in HFE, C$^*$, and variations

Christopher Wolf and Bart Preneel

Abstract

In this article, we investigate the question of equivalent keys for two $\mathcal{M}$ultivariate $\mathcal{Q}$uadratic public key schemes HFE and C$^{*--}$ and improve over a previously known result, to appear at PKC 2005. Moreover, we show a new non-trivial extension of these results to the classes HFE-, HFEv, HFEv-, and C$^{*--}$, which are cryptographically stronger variants of the original HFE and C$^*$ schemes. In particular, we are able to reduce the size of the private --- and hence the public --- key space by at least one order of magnitude. While the results are of independent interest themselves, we also see applications both in cryptanalysis and in memory efficient implementations.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Proceedings of Mycrypt 2005, LNCS 3715, pages 33-49. Serge Vaudenay, editor, Springer, 2005.
Keywords
Multivariate Quadratic EquationsPublic Key signatureHidden Field EquationsHFEHFE-HFEvHFEv-C$^*$C$^{*--}$
Contact author(s)
Christopher Wolf @ esat kuleuven ac be
History
2005-08-09: last of 2 revisions
2004-12-16: received
See all versions
Short URL
https://ia.cr/2004/360
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/360,
      author = {Christopher Wolf and Bart Preneel},
      title = {Equivalent Keys in HFE, C$^*$, and variations},
      howpublished = {Cryptology ePrint Archive, Paper 2004/360},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/360}},
      url = {https://eprint.iacr.org/2004/360}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.