Alexey D. Myasnikov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Alexey D. Myasnikov has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Alexander Ushakov
Stevens Institute of Technology
3 shared publications - Robert Haralick
Pattern Recognition Laboratory, CS Department, The Graduate Center, City University of New York, 365 Fifth Avenue, New York, NY 10016, USA
2 shared publications
Latest Publications
- Open Access
- 24 January 2014
- Published by Walter de Gruyter GmbH in Journal of Mathematical Cryptology
- Vol. 8 (2) , 95-114
Cryptanalysis of matrix conjugation schemes
: In this paper we cryptanalyze two protocols: the Grigoriev–Shpilrain authentication protocol and a public key cryptosystem due to Wang, Wang, Cao, Okamoto and Shao. Both of these protocols use the computational hardness of some variations of the conjugacy search problem in a class of noncommutative monoids. We devise a practical heuristic algorithm solving those problems. As a conclusion we claim that these protocols are insecure for the proposed parameter values.
- 24 January 2014
- Published by Walter de Gruyter GmbH in Journal of Mathematical Cryptology
- Vol. 8 (2) , 95-114
Open AccessCryptanalysis of matrix conjugation schemes
: In this paper we cryptanalyze two protocols: the Grigoriev–Shpilrain authentication protocol and a public key cryptosystem due to Wang, Wang, Cao, Okamoto and Shao. Both of these protocols use the computational hardness of some variations of the conjugacy search problem in a class of noncommutative monoids. We devise a practical heuristic algorithm solving those problems. As a conclusion we claim that these protocols are insecure for the proposed parameter values.
- 1 January 2014
- Published by Walter de Gruyter GmbH in Groups - Complexity - Cryptology
- Vol. 6 (1)
Quantum algorithm for discrete logarithm problem for matrices over finite group rings
- 1 January 2014
- Published by Walter de Gruyter GmbH in Groups - Complexity - Cryptology
- Vol. 6 (1)
Quantum algorithm for discrete logarithm problem for matrices over finite group rings
- 1 January 2009
- Published by Walter de Gruyter GmbH in Groups - Complexity - Cryptology
- Vol. 1 (1)
Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux Key Agreement Protocol
- 1 January 2009
- Published by Walter de Gruyter GmbH in Groups - Complexity - Cryptology
- Vol. 1 (1)
Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux Key Agreement Protocol
- 31 July 2006
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 41 (7) , 818-834
A hybrid search algorithm for the Whitehead Minimization problem
- 31 July 2006
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 41 (7) , 818-834
A hybrid search algorithm for the Whitehead Minimization problem
- Open Access
A Hybrid Search Algorithm for the Whitehead Minimization Problem
The Whitehead Minimization problem is a problem of finding elements of the minimal length in the automorphic orbit of a given element of a free group. The classical algorithm of Whitehead that solves the problem depends exponentially on the group rank. Moreover, it can be easily shown that exponential blowout occurs when a word of minimal length has been reached and, therefore, is inevitable except for some trivial cases. In this paper we introduce a deterministic Hybrid search algorithm and its stochastic variation for solving the Whitehead minimization problem. Both algorithms use search heuristics that allow one to find a length-reducing automorphism in polynomial time on most inputs and significantly improve the reduction procedure. The stochastic version of the algorithm employs a probabilistic system that decides in polynomial time whether or not a word is minimal. The stochastic algorithm is very robust. It has never happened that a non-minimal element has been claimed to be minimal.
Open AccessA Hybrid Search Algorithm for the Whitehead Minimization Problem
The Whitehead Minimization problem is a problem of finding elements of the minimal length in the automorphic orbit of a given element of a free group. The classical algorithm of Whitehead that solves the problem depends exponentially on the group rank. Moreover, it can be easily shown that exponential blowout occurs when a word of minimal length has been reached and, therefore, is inevitable except for some trivial cases. In this paper we introduce a deterministic Hybrid search algorithm and its stochastic variation for solving the Whitehead minimization problem. Both algorithms use search heuristics that allow one to find a length-reducing automorphism in polynomial time on most inputs and significantly improve the reduction procedure. The stochastic version of the algorithm employs a probabilistic system that decides in polynomial time whether or not a word is minimal. The stochastic algorithm is very robust. It has never happened that a non-minimal element has been claimed to be minimal.