We briefly discuss linear decomposition and nonlinear decomposition attacks using
polynomial-time deterministic algorithms that recover the secret shared keys from
public data in many schemes of algebraic cryptography. We show that in this case,
contrary to common opinion, typical computational security assumptions are not
very relevant to the security of the schemes; i.e., one can break the schemes without
solving the algorithmic problems on which the assumptions are based. Also we
present another and in some points similar approach, which was established by
Tsaban et al.
Before demonstrating the applicability of these two methods to two well-known
noncommutative protocols, we cryptanalyze two new cryptographic schemes that
have not yet been analyzed.
Further, we introduce a novel method of construction of systems resistant against
attacks via linear algebra. In particular, we propose improved versions of the
well-known Diffie–Hellman-type (DH) and Anshel–Anshel–Goldfeld (AAG) algebraic
cryptographic key-exchange protocols.
