Vol. 9, No. 2, 2020

Download this article
Download this article For screen
For printing
Recent Issues
Volume 12, Issue 3
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 4
Volume 11, Issue 3
Volume 11, Issue 2
Volume 11, Issue 1
Volume 10, Issue 4
Volume 10, Issue 3
Volume 10, Issue 2
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
Older Issues
Volume 7, Issue 4
Volume 7, Issue 3
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 4
Volume 6, Issue 2-3
Volume 6, Issue 1
Volume 5, Issue 4
Volume 5, Issue 3
Volume 5, Issue 1-2
Volume 4, Issue 4
Volume 4, Issue 3
Volume 4, Issue 2
Volume 4, Issue 1
Volume 3, Issue 3-4
Volume 3, Issue 2
Volume 3, Issue 1
Volume 2, Issue 4
Volume 2, Issue 3
Volume 2, Issue 2
Volume 2, Issue 1
Volume 1, Issue 4
Volume 1, Issue 3
Volume 1, Issue 2
Volume 1, 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
mathematicians from the
Moscow Institute of
Physics and Technology
ISSN (electronic): 2640-7361
ISSN (print): 2220-5438
Author Index
To Appear
Other MSP Journals
This article is available for purchase or by subscription. See below.
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.

PDF Access Denied

We have not been able to recognize your IP address as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

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