
It is well known that any polycyclic group, and hence any finitely generated
nilpotent group, can be embedded into $GL_{n}(\mathbb{Z})$ for an appropriate
$n\in \mathbb{N}$; that is, each element in the group has a unique matrix
representation. An algorithm to determine this embedding was presented in
Nickel. In this paper, we determine the complexity of the crux of the algorithm
and the dimension of the matrices produced as well as provide a modification of
the algorithm presented by Nickel.

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.

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.

Most common public key cryptosystems and public key exchange protocols
presently in use, such as the RSA algorithm, DiffieHellman, and elliptic curve
methods are number theory based and hence depend on the structure of abelian
groups. The strength of computing machinery has made these techniques
theoretically susceptible to attack and hence recently there has been an active
line of research to develop cryptosystems and key exchange protocols using
noncommutative cryptographic platforms. This line of investigation has been
given the broad title of noncommutative algebraic cryptography. This was
initiated by two public key protocols that used the braid groups, one by Ko,
Lee et.al.and one by Anshel, Anshel and Goldfeld. The study of these protocols
and the group theory surrounding them has had a large effect on research in
infinite group theory. In this paper we survey these noncommutative group based
methods and discuss several ideas in abstract infinite group theory that have
arisen from them. We then present a set of open problems.