Lecture Notes in Computer Science vol:3386 pages:275-287
PKC 2005 date:January 23-26, 2005
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 axe 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.