zbMATH — the first resource for mathematics

Algebraic cryptanalysis and new security enhancements. (English) Zbl 07211443
Summary: 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.
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F70 Algebraic geometry over groups; equations over groups
94A60 Cryptography
Full Text: DOI