Equivalent Keys in HFE, C*, and Variations

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, which appeared 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 and several orders of magnitude on average. While the results are of independent interest themselves as they broaden our understanding of ${\mathcal M}$ultivariate ${\mathcal Q}$uadratic schemes, we also see applications both in cryptanalysis and in memory efficient implementations.