Cryptology ePrint Archive: Report 2004/367

On the Affine Transformations of HFE-Cryptosystems and Systems with Branches

Patrick Felke

Abstract: We show how to recover the affine parts of the secret key for a certain class of HFE-Cryptosystems. Further we will show that any system build on branches can be decomposed in its single branches in polynomial time on average. The first part generalizes the result from \cite{geisel} to a bigger class of systems and is achieved by a different approach. Dispite the fact that systems with branches are not used anymore (see \cite{patarin1, goubin}), our second result is a still of interest as it applies to a very general class of HFE-cryptosystems and thus is a contribution to the list of algebraic properties, which cannot be hidden by composition with the secret affine transformations. We derived both algorithms by considering the cryptosystem as objects from the theory of nonassociative algebras and applying classical techniques from this theory. This general framework might be useful for future investigations of HFE-Cryptosysstems or to generalize other attacks known so far.

Category / Keywords: public-key cryptography /

Date: received 17 Dec 2004, last revised 16 Feb 2005

Contact author: patrick felke at ruhr-uni-bochum de

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20050216:133459 (All versions of this report)

Short URL: ia.cr/2004/367

Discussion forum: Show discussion | Start new discussion