A nonlinear decomposition method in analysis of some encryption schemes using group automorphisms

This paper shows how the nonlinear decomposition method, that had been invented by the first author, works against two cryptographic schemes based on group automorphisms. In some cases we can find the secret data and break the scheme without solving the algorithmic problem on which scheme is based. More exactly, let $G$ be a group and $A$ be a finitely generated subgroup of the automorphism group $\mathrm{Aut}(G)$. Suppose, that the membership search problem for $G$ is efficiently solvable for any subgroup of the form $\langle g^A\rangle$ generated by the all images of $g$ under automorphisms of $A$, and every subgroup $\langle g^A\rangle$ is finitely generated. Then there exists an efficient algorithm to construct a finite generating set of $\langle g^A\rangle$ and the nonlinear decomposition method can be applied. In particular, if the elements $g, f=g^\alpha,h=f^\beta\in G$ are public, $\alpha,\beta\in\mathrm{Aut}(G)$, $\alpha\beta=\beta\alpha$, and $\alpha,\beta$ are private, then one can efficiently compute $h^\alpha$ without computing $\alpha$ or $\beta$. The method efficiently works for a Noetherian group with efficiently solvable membership search problem. In particular, finitely generated nilpotent (more generally, polycyclic) groups, that are frequently used in the modern algebraic cryptography, share this property.