Cryptology ePrint Archive: Report 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.
Category / Keywords: public-key cryptography / Multivariate Quadratic Equations, Public Key Schemes, Equivalent Keys
Date: received 16 Dec 2004, last revised 28 Jan 2005
Contact author: christopher wolf at esat kuleuven ac be
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20050128:083727 (All versions of this report)
Short URL: ia.cr/2004/361
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]