Vol. 9, No. 2, 2020

Download this article
Download this article For screen
For printing
Recent Issues
Volume 10, Issue 1
Volume 9, Issue 4
Volume 9, Issue 3
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
The Journal
About the Journal
Editorial Board
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
founded and published with the
scientific support and advice of the
Moscow Institute of
Physics and Technology
ISSN (electronic): 2640-7361
ISSN (print): 2220-5438
Previously Published
Author Index
To Appear
Other MSP Journals
Algebraic cryptanalysis and new security enhancements

Vitaliĭ Roman’kov

Vol. 9 (2020), No. 2, 123–146

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.

postquantum cryptography, algebraic cryptanalysis, algebraic cryptography, marginal sets
Mathematical Subject Classification 2010
Primary: 20F10
Secondary: 20F70, 94A60
Received: 9 November 2019
Revised: 2 March 2020
Accepted: 25 March 2020
Published: 11 May 2020
Vitaliĭ Roman’kov
Mathematical Center
Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences