• This is a survey of algorithmic problems in group theory, old and new, motivated by applications to cryptography.
  • We consider what some authors call 'parabolic M\"obius subgroups' of matrices over Z, Q, and R and focus on the membership problem in these subgroups and complexity of relevant algorithms.
  • In this survey, we describe a general key exchange protocol based on semidirect product of (semi)groups (more specifically, on extensions of (semi)groups by automorphisms), and then focus on practical instances of this general idea. This protocol can be based on any group or semigroup, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when this protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. The focus then shifts to selecting an optimal platform (semi)group, in terms of security and efficiency. We show, in particular, that one can get a variety of new security assumptions by varying an automorphism used for a (semi)group extension.
  • Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with $2 \times 2$ matrices over $F_p$. Since there are many known pairs of $2 \times 2$ matrices over $Z$ that generate a free monoid, this yields numerous pairs of matrices over $F_p$, for a sufficiently large prime $p$, that are candidates for collision-resistant hashing. However, this trick can "backfire", and lifting matrix entries to $Z$ may facilitate finding a collision. This "lifting attack" was successfully used by Tillich and Z\'emor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole monoid $SL_2(Z_+)$. However, in this paper we show that the situation with other, "similar", pairs of matrices from $SL_2(Z)$ is different, and the "lifting attack" can (in some cases) produce collisions in the group generated by $A$ and $B$, but not in the positive monoid. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from $SL_2(F_p)$.
  • We propose a cryptosystem based on matrices over group rings and claim that it is secure against adaptive chosen ciphertext attack.
  • We use various laws of classical physics to offer several solutions of Yao's millionaires' problem without using any one-way functions. We also describe several informationally secure public key encryption protocols, i.e., protocols secure against passive computationally unbounded adversary. This introduces a new paradigm of decoy-based cryptography, as opposed to "traditional" complexity-based cryptography. In particular, our protocols do not employ any one-way functions.
  • In this paper, we describe a brand new key exchange protocol based on a semidirect product of (semi)groups (more specifically, on extension of a (semi)group by automorphisms), and then focus on practical instances of this general idea. Our protocol can be based on any group, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when our protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. Here we also suggest a particular non-commutative semigroup (of matrices) as the platform and show that security of the relevant protocol is based on a quite different assumption compared to that of the standard Diffie-Hellman protocol.
  • We offer a public key exchange protocol in the spirit of Diffie-Hellman, but we use (small) matrices over a group ring of a (small) symmetric group as the platform. This "nested structure" of the platform makes computation very efficient for legitimate parties. We discuss security of this scheme by addressing the Decision Diffie-Hellman (DDH) and Computational Diffie-Hellman (CDH) problems for our platform.
  • We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious "$P \ne NP$" conjecture. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal "intermediate results" of a computation. For example, when we compute the sum of $k$ numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of Yao's "millionaires' problem". Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our (bit) commitment scheme for 3 parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a "dummy" (e.g., a computer) as the third party. We explain how our concept of a "dummy" is different from a well-known concept of a "trusted third party". We also suggest a protocol, without using a one-way function, for "mental poker", i.e., a fair card dealing (and playing) over distance. We also propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.
  • We employ tropical algebras as platforms for several cryptographic schemes that would be vulnerable to linear algebra attacks were they based on "usual" algebras as platforms.
  • A (t,n)-threshold secret sharing scheme is a method to distribute a secret among n participants in such a way that any t participants can recover the secret, but no t-1 participants can. In this paper, we propose two secret sharing schemes using non-abelian groups. One scheme is the special case where all the participants must get together to recover the secret. The other one is a (t,n)-threshold scheme that is a combination of Shamir's scheme and the group-theoretic scheme proposed in this paper.
  • Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a small portion of the input. The most typical situation where sublinear time algorithms are considered is property testing. There are several interesting contexts where one can test properties in sublinear time. A canonical example is graph colorability. To tell that a given graph is not k-colorable, it is often sufficient to inspect just one vertex with incident edges: if the degree of a vertex is greater than k, then the graph is not k-colorable. It is a challenging and interesting task to find algebraic properties that could be tested in sublinear time. In this paper, we address several algorithmic problems in the theory of groups and semigroups that may admit sublinear time solution, at least for "most" inputs.
  • We propose an authentication scheme where forgery (a.k.a. impersonation) seems infeasible without finding the prover's long-term private key. The latter would follow from solving the conjugacy search problem in the platform (noncommutative) semigroup, i.e., to recovering X from X^{-1}AX and A. The platform semigroup that we suggest here is the semigroup of nxn matrices over truncated multivariable polynomials over a ring.
  • Decision problems are problems of the following nature: given a property P and an object O, find out whether or not the object O has the property P. On the other hand, witness problems are: given a property P and an object O with the property P, find a proof of the fact that O indeed has the property P. On the third hand(?!), search problems are of the following nature: given a property P and an object O with the property P, find something "material" establishing the property P; for example, given two conjugate elements of a group, find a conjugator. In this survey our focus is on various search problems in group theory, including the word search problem, the subgroup membership search problem, the conjugacy search problem, and others.
  • 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$. 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) phi, \psi of a group G and a pair of elements w, t \in G, find an element s \in G such that t = \psi(s^{-1}) w \phi(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 2x2 matrices over truncated one-variable polynomials over F_2, the field of two elements, with transposition used instead of inversion in the equality above.
  • We propose a general way of constructing zero-knowledge authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several zero-knowledge authentication schemes where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include (Sub)graph Isomorphism, Graph Colorability, Diophantine Problem, and many others.
  • There are several public key establishment protocols as well as complete public key cryptosystems based on allegedly hard problems from combinatorial (semi)group theory known by now. Most of these problems are search problems, i.e., they are of the following nature: given a property P and the information that there are objects with the property P, find at least one particular object with the property P. So far, no cryptographic protocol based on a search problem in a non-commutative (semi)group has been recognized as secure enough to be a viable alternative to established protocols (such as RSA) based on commutative (semi)groups, although most of these protocols are more efficient than RSA is. In this paper, we suggest to use decision problems from combinatorial group theory as the core of a public key establishment protocol or a public key cryptosystem. By using a popular decision problem, the word problem, we design a cryptosystem with the following features: (1) Bob transmits to Alice an encrypted binary sequence which Alice decrypts correctly with probability "very close" to 1; (2) the adversary, Eve, who is granted arbitrarily high (but fixed) computational speed, cannot positively identify (at least, in theory), by using a "brute force attack", the "1" or "0" bits in Bob's binary sequence. In other words: no matter what computational speed we grant Eve at the outset, there is no guarantee that her "brute force attack" program will give a conclusive answer (or an answer which is correct with overwhelming probability) about any bit in Bob's sequence.
  • In this paper we present a new key establishment protocol based on the decomposition problem in non-commutative groups which is: given two elements $w, w_1$ of the platform group $G$ and two subgroups $A, B \subseteq G$ (not necessarily distinct), find elements $a \in A, b \in B$ such that $w_1 = a w b$. Here we introduce two new ideas that improve the security of key establishment protocols based on the decomposition problem. In particular, we conceal (i.e., do not publish explicitly) one of the subgroups $A, B$, thus introducing an additional computationally hard problem for the adversary, namely, finding the centralizer of a given finitely generated subgroup.
  • In this article we relate two different densities. Let $F_k$ be the free group of finite rank $k \ge 2$ and let $\alpha$ be the abelianization map from $F_k$ onto $ \mathbb{Z}^k$. We prove that if $S \subseteq \mathbb{Z}^k$ is invariant under the natural action of $SL(k, \mathbb{Z})$ then the asymptotic density of $S$ in $\mathbb Z^k$ and the annular density of its full preimage $\alpha^{-1}(S)$ in $F_k$ are equal. This implies, in particular, that for every integer $t\ge 1$, the annular density of the set of elements in $F_k$ that map to $t$-th powers of primitive elements in $\mathbb{Z}^k$ is equal to to $\frac{1}{t^k\zeta(k)}$, where $\zeta$ is the Riemann zeta-function. An element $g$ of a group $G$ is called a \emph{test element} if every endomorphism of $G$ which fixes $g$ is an automorphism of $G$. As an application of the result above we prove that the annular density of the set of all test elements in the free group $F(a,b)$ of rank two is $1-\frac{6}{\pi^2}$. Equivalently, this shows that the union of all proper retracts in $F(a,b)$ has annular density $\frac{6}{\pi^2}$. Thus being a test element in $F(a,b)$ is an ``intermediate property'' in the sense that the probability of being a test element is strictly between 0 and 1.
  • Study of the dynamics of automorphisms of a group is usually focused on their growth and/or finite orbits, including fixed points. In this paper, we introduce properties of a different kind; using somewhat informal language, we call them metric properties. Two principal characteristics of this kind are called here the "curl" and the "flux"; there seems to be very little correlation between these and the growth of an automorphism, which means they are likely to be an essentially new tool for studying automorphisms. We also observe that our definitions of the curl and flux are sufficiently general to be applied to mappings of arbitrary metric spaces.
  • Recently, several public key exchange protocols based on symbolic computation in non-commutative (semi)groups were proposed as a more efficient alternative to well established protocols based on numeric computation. Notably, the protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al. exploited the conjugacy search problem in groups, which is a ramification of the discrete logarithm problem. However, it is a prevalent opinion now that the conjugacy search problem alone is unlikely to provide sufficient level of security no matter what particular group is chosen as a platform. In this paper we employ another problem (we call it the decomposition problem), which is more general than the conjugacy search problem, and we suggest to use R. Thompson's group as a platform. This group is well known in many areas of mathematics, including algebra, geometry, and analysis. It also has several properties that make it fit for cryptographic purposes. In particular, we show here that the word problem in Thompson's group is solvable in almost linear time.
  • Motivated by the work of Leininger on hyperbolic equivalence of homotopy classes of closed curves on surfaces, we investigate a similar phenomenon for free groups. Namely, we study the situation when two elements $g,h$ in a free group $F$ have the property that for every free isometric action of $F$ on an $\mathbb{R}$-tree $X$ the translation lengths of $g$ and $h$ on $X$ are equal. We give a combinatorial characterization of this phenomenon, called translation equivalence, in terms of Whitehead graphs and exhibit two difference sources of it. The first source of translation equivalence comes from representation theory and $SL_2$ trace identities. The second source comes from geometric properties of groups acting on real trees and a certain power redistribution trick. We also analyze to what extent these are applicable to the tree actions of surface groups that occur in the Thurston compactification of the Teichmuller space.
  • 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.
  • After some excitement generated by recently suggested public key exchange protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al., it is a prevalent opinion now that the conjugacy search problem is unlikely to provide sufficient level of security if a braid group is used as the platform. In this paper we address the following questions: (1) whether choosing a different group, or a class of groups, can remedy the situation; (2) whether some other "hard" problem from combinatorial group theory can be used, instead of the conjugacy search problem, in a public key exchange protocol. Another question that we address here, although somewhat vague, is likely to become a focus of the future research in public key cryptography based on symbolic computation: (3) whether one can efficiently disguise an element of a given group (or a semigroup) by using defining relations.
  • We prove that Whitehead's algorithm for solving the automorphism problem in a fixed free group $F_k$ has strongly linear time generic-case complexity. This is done by showing that the ``hard'' part of the algorithm terminates in linear time on an exponentially generic set of input pairs. We then apply these results to one-relator groups. We obtain a Mostow-type isomorphism rigidity result for random one-relator groups: If two such groups are isomorphic then their Cayley graphs on the \emph{given generating sets} are isometric. Although no nontrivial examples were previously known, we prove that one-relator groups are generically \emph{complete} groups, that is, they have trivial center and trivial outer automorphism group. We also prove that the stabilizers of generic elements of $F_k$ in $Aut(F_k)$ are cyclic groups generated by inner automorphisms and that $Aut(F_k)$-orbits are uniformly small in the sense of their growth entropy. We further prove that the number $I_k(n)$ of \emph{isomorphism types} of $k$-generator one-relator groups with defining relators of length $n$ satisfies \[ \frac{c_1}{n} (2k-1)^n \le I_k(n)\le \frac{c_2}{n} (2k-1)^n, \] where $c_1=c_1(k)>0, c_2=c_2(k)>0$ are some constants independent of $n$. Thus $I_k(n)$ grows in essentially the same manner as the number of cyclic words of length $n$.