International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Superfluous Keys in Multivariate Quadratic Asymmetric Systems

Authors:
Christopher Wolf
Bart Preneel
Download:
URL: http://eprint.iacr.org/2004/361
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12324,
  title={Superfluous Keys in Multivariate Quadratic Asymmetric Systems},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Multivariate Quadratic Equations, Public Key Schemes, Equivalent Keys},
  url={http://eprint.iacr.org/2004/361},
  note={ christopher.wolf@esat.kuleuven.ac.be 12811 received 16 Dec 2004, last revised 28 Jan 2005},
  author={Christopher Wolf and Bart Preneel},
  year=2004
}