Search

We prove that the Diophantine problem for orientable quadratic equations in free metabelian groups is decidable and furthermore, NP-complete. In the case when the number of variables in the equation is bounded, the problem is decidable in polynomial time.

Experimental investigations of the properties of nanostructured materials are of large practical significance. Physical and chemical properties of nanocrystalline and amorphous-nanocrystalline alloys are currently being actively researched. Yet, the practical use of such materials is complicated by the lack of an optimal set of physical and mechanical properties. Classical processing methods are not effective enough. Laser processing is a promising method for forming specified mechanical properties. Amorphous-nanostructured materials, as a result of local and ultrafast exposure to high temperatures and pressure, retain their structure almost unchanged. At the same time, plasticity and microhardness can remain at a high level, and in some cases even increase during processing. The relevance of the presented work lies in the study of the regularities of the simultaneous increase in plasticity and microhardness of an amorphous Co-based nanocrystalline metal alloy, due to its processing with nanosecond laser pulses. The relevance of the presented work lies in the study of the patterns of the simultaneous increase in plasticity and microhardness of an amorphous Co-based nanocrystalline metal alloy due to its processing with nanosecond laser pulses.

We analyze security properties of a two-party key-agreement protocol recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels, called Kayawood protocol. At the core of the protocol is an action (called E-multiplication) of a braid group on some finite set. The protocol assigns a secret element of a braid group to each party (private key). To disguise those elements, the protocol uses a so-called cloaking method that multiplies private keys on the left and on the right by specially designed elements (stabilizers for E-multiplication). We present a heuristic algorithm that allows a passive eavesdropper to recover Alice’s private key by removing cloaking elements. Our attack has 100% success rate on randomly generated instances of the protocol for the originally proposed parameter values and for recent proposals that suggest to insert many cloaking elements at random positions of the private key. Implementation of the attack is available on GitHub.

We develop new computational methods for studying potential counterexamples to the Andrews–Curtis conjecture, in particular, Akbulut–Kurby examples{\operatorname{AK}(n)}. We devise a number of algorithms in an attempt to disprove the most interesting counterexample{\operatorname{AK}(3)}. That includes an efficient implementation of the folding procedure for pseudo-conjugacy graphs, based on the original modification of a classic disjoint-set data structure. To improve metric properties of the search space (the set of balanced presentations of the trivial group), we introduce a new transformation, called an ACM-move, that generalizes the original Andrews–Curtis transformations and discuss details of a practical implementation. To reduce growth of the search space, we introduce a strong equivalence relation on balanced presentations and study the space modulo automorphisms of the underlying free group. We prove that automorphism moves can be applied to Akbulut–Kurby presentations. The improved technique allows us to enumerate balanced presentations AC-equivalent to{\operatorname{AK}(3)}with relations of lengths up to 20 (previous record was 17).

In this paper, we consider a two party key-exchange protocol proposed in [D. Grigoriev and V. Shpilrain, Tropical cryptography, Comm. Algebra 43 (2014), 2624–2632, Section 2], which uses tropical matrix algebra as the platform. Our analysis shows that the scheme is not secure.

In this paper we further study properties of Magnus embedding, give a precise reducibility diagram for Dehn problems in groups of the form F / N ( d ) F/N^{(d)} , and provide a detailed answer to Problem 12.98 in The Kourovka notebook. We also show that most of the reductions are polynomial time reductions and can be used in practical computation.

We provide an algorithm which, for a given quadratic equation in the Grigorchuk group determines if it has a solution. As a corollary to our approach, we prove that the group has a finite commutator width.

We consider a group-theoretic analogue of the classic subset sum problem. It is known that every virtually nilpotent group has polynomial time decidable subset sum problem. In this paper we use subgroup distortion to show that every polycyclic non-virtually-nilpotent group has NP-complete subset sum problem., Comment: 11 pages. To appear in Journal of Symbolic Computation

In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete.

The classic knapsack and related problems have natural generalizations to arbitrary (non-commutative) groups, collectively called knapsack-type problems in groups. We study the effect of free and direct products on their time complexity. We show that free products in certain sense preserve time complexity of knapsack-type problems, while direct products may amplify it. Our methods allow to obtain complexity results for rational subset membership problem in amalgamated free products over finite subgroups., 15 pages, 5 figures. Updated to include more general results, mostly in Section 4

In this paper, we study complexity of randomly generated instances of Dehn search problems in finitely presented groups. We use Crump–Mode–Jagers (CMJ) processes to show that most of the random instances are easy. Our analysis shows that for any choice of a finitely presented platform group in Wagner–Magyarik public key encryption protocol the majority of random keys can be broken by a polynomial time algorithm.

We prove that the Diophantine problem for spherical quadratic equations in free metabelian groups is solvable and, moreover, NP-complete

Power circuits are data structures which support efficient algorithms for highly compressed integers. Using this new data structure it has been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator Baumslag group is in P. Before that the best known upper bound was non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic algebra and algorithmic group theory: (1) We define a modified reduction procedure on power circuits which runs in quadratic time, thereby improving the known cubic time complexity. The improvement is crucial for our other results. (2) We improve the complexity of the Word Problem for the Baumslag group to cubic time, thereby providing the first practical algorithm for that problem. (The algorithm has been implemented and is available in the CRAG library.) (3) The main result is that the Word Problem of Higman's group is decidable in polynomial time. The situation for Higman's group is more complicated than for the Baumslag group and forced us to advance the theory of power circuits.

We prove that the Word Problem in the Baumslag group G ( 1 , 2 ) = 〈 a , b ; a a b = a 2 〉 which has a non-elementary Dehn function is decidable in polynomial time.

We analyze the Sibert et al. group-based (Feige-Fiat-Shamir type) authentication protocol and show that the protocol is not computationally zero-knowledge. In addition, we provide experimental evidence that our approach is practical and can succeed even for groups with no efficiently computable length function such as braid groups. The novelty of this work is that we are not attacking the protocol by trying to solve an underlying complex algebraic problem, namely, the conjugacy search problem, but use a probabilistic approach, instead.

We consider (graph-)group-valued random element $\xi$, discuss the properties of a mean-set $\ME(\xi)$, and prove the generalization of the strong law of large numbers for graphs and groups. Furthermore, we prove an analogue of the classical Chebyshev's inequality for $\xi$ and Chernoff-like asymptotic bounds. In addition, we prove several results about configurations of mean-sets in graphs and discuss computational problems together with methods of computing mean-sets in practice and propose an algorithm for such computation., Comment: 29 pages, 2 figures, new references added, Introduction revised, Chernoff-like bound added

The conjugacy search problem in a group G is the problem of recovering an x ∈ G from given g ∈ G and h = x-1gx. The alleged computational hardness of this problem in some groups was used in several recently suggested public key exchange protocols, including the one due to Anshel, Anshel, and Goldfeld, and the one due to Ko, Lee et al. Sibert, Dehornoy, and Girault used this problem in their authentication scheme, which was inspired by the Fiat-Shamir scheme involving repeating several times a three-pass challenge-response step. In this paper, we offer an authentication scheme whose security is based on the apparent hardness of the twisted conjugacy search problem which is: given a pair of endomorphisms (i.e., homomorphisms into itself) θ, ψ of a group G and a pair of elements ω, t ∈ G, find an element s ∈ G such that t = ψ(s-1)ωθ(s) provided at least one such s exists. This problem appears to be very non-trivial even for free groups. We offer here another platform, namely, the semigroup of all 2 × 2 matrices over truncated one-variable polynomials over F2, the field of two elements, with transposition used instead of inversion in the equality above.

The conjugacy search problem in a group G is the problem of recovering an x in G from given g in G and h=x^{-1}gx. This problem is in the core of several recently suggested public key exchange protocols, most notably the one due to Anshel, Anshel, and Goldfeld, and the one due to Ko, Lee at al. In this note, we make two observations that seem to have eluded most people's attention. The first observation is that solving the conjugacy search problem is not necessary for an adversary to get the common secret key in the Ko-Lee protocol. It is sufficient to solve an apparently easier problem of finding x, y in G such that h=ygx for given g, h in G. Another observation is that solving the conjugacy search problem is not sufficient for an adversary to get the common secret key in the Anshel-Anshel-Goldfeld protocol., 4 pages