Cryptology ePrint Archive: Report 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
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.
Category / Keywords: public-key cryptography / Multivariate Quadratic, Equivalent Keys
Date: received 22 Dec 2005
Contact author: Christopher Wolf at ens fr
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20051231:150243 (All versions of this report)
Short URL: ia.cr/2005/464
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]