
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 noncommutative group. One of its special cases is the
standard DiffieHellman protocol, which is based on a cyclic group. However,
when this protocol is used with a noncommutative (semi)group, it acquires
several useful features that make it compare favorably to the DiffieHellman
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 collisionresistant 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 oneway 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 decoybased cryptography, as opposed to "traditional"
complexitybased cryptography. In particular, our protocols do not employ any
oneway 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
noncommutative group. One of its special cases is the standard DiffieHellman
protocol, which is based on a cyclic group. However, when our protocol is used
with a noncommutative (semi)group, it acquires several useful features that
make it compare favorably to the DiffieHellman protocol. Here we also suggest
a particular noncommutative 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 DiffieHellman protocol.

We offer a public key exchange protocol in the spirit of DiffieHellman, 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 DiffieHellman (DDH) and Computational DiffieHellman
(CDH) problems for our platform.

We show that some problems in information security can be solved without
using oneway functions. The latter are usually regarded as a central concept
of cryptography, but the very existence of oneway 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 oneway 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 oneway 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
wellknown concept of a "trusted third party".
We also suggest a protocol, without using a oneway 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 t1 participants can. In this paper, we propose two secret
sharing schemes using nonabelian 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
grouptheoretic 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 kcolorable, 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 kcolorable. 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 longterm 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
FiatShamir scheme involving repeating several times a threepass
challengeresponse 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 nontrivial even for free groups. We offer here another
platform, namely, the semigroup of all 2x2 matrices over truncated onevariable
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 zeroknowledge 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
zeroknowledge authentication schemes where forgery (a.k.a. impersonation) is
NPhard. 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 noncommutative (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 noncommutative 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 zetafunction. 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 noncommutative (semi)groups were proposed as a more efficient alternative
to well established protocols based on numeric computation. Notably, the
protocols due to AnshelAnshelGoldfeld and KoLee 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 KoLee
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
AnshelAnshelGoldfeld protocol.

After some excitement generated by recently suggested public key exchange
protocols due to AnshelAnshelGoldfeld and KoLee 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 genericcase 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 onerelator groups. We obtain a Mostowtype isomorphism rigidity
result for random onerelator 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 onerelator 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 onerelator groups with defining
relators of length $n$ satisfies \[ \frac{c_1}{n} (2k1)^n \le I_k(n)\le
\frac{c_2}{n} (2k1)^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$.