Paper 2004/367 Original: eprint.iacr.org/2004/367 ↗

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

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.