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

Christopher Wolf; Bart Preneel

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 $M$ ultivariate $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 Equations Public Key signature Hidden Field Equations HFE HFE-HFEv HFEv-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: 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},
      url = {https://eprint.iacr.org/2004/360}
}

Paper 2004/360

Equivalent Keys in HFE, C∗, and variations

Abstract

Metadata

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