
In this paper we discuss the Hidden Subgroup Problem (HSP) in relation to
postquantum groupbased cryptography. We review the relationship between HSP
and other computational problems discuss an optimal solution method, and review
the known results about the quantum complexity of HSP. We also overview some
platforms for groupbased cryptosystems. Notably, efficient algorithms for
solving HSP in such infinite group platforms are not yet known.

In this paper we will give various examples of exponentially distorted
subgroups in linear groups, including some new example of subgroups of
$SL_n(\mathbb{Z}[x])$ for $n \ge 3$, and show how they can be used to construct
symmetrickey cryptographic platforms.

Machine learning and pattern recognition techniques have been successfully
applied to algorithmic problems in free groups. In this paper, we seek to
extend these techniques to finitely presented nonfree groups, with a
particular emphasis on polycyclic and metabelian groups that are of interest to
noncommutative cryptography.
As a prototypical example, we utilize supervised learning methods to
construct classifiers that can solve the conjugacy decision problem, i.e.,
determine whether or not a pair of elements from a specified group are
conjugate. The accuracies of classifiers created using decision trees, random
forests, and Ntuple neural network models are evaluated for several nonfree
groups. The very high accuracy of these classifiers suggests an underlying
mathematical relationship with respect to conjugacy in the tested groups.

In this paper we consider several classical and novel algorithmic problems
for rightangled Artin groups, some of which are closely related to graph
theoretic problems, and study their computational complexity. We study these
problems with a view towards applications to cryptography.

Weanalyzethecomputationalcomplexityofanalgorithmtosolve the conjugacy search
problem in a certain family of metabelian groups. We prove that in general the
time complexity of the conjugacy search problem for these groups is at most
exponential. For a subfamily of groups we prove that the conjugacy search
problem is polynomial. We also show that for a different subfamily the
conjugacy search problem reduces to the discrete logarithm problem.

In this paper we propose rightangled Artin groups as a platform for secret
sharing schemes based on the efficiency (linear time) of the word problem.
Inspired by previous work of GrigorievShpilrain in the context of graphs, we
define two new problems: Subgroup Isomorphism Problem and Group Homomorphism
Problem. Based on them, we also propose two new authentication schemes. For
rightangled Artin groups, the Group Homomorphism and Graph Homomorphism
problems are equivalent, and the later is known to be NPcomplete. In the case
of the Subgroup Isomorphism problem, we bring some results due to Bridson who
shows there are rightangled Artin groups in which this problem is unsolvable.

In this paper we propose cryptosystems based on subgroup distortion in
hyperbolic groups. We also include concrete examples of hyperbolic groups as
possible platforms.

Polycyclic groups are natural generalizations of cyclic groups but with more
complicated algorithmic properties. They are finitely presented and the word,
conjugacy, and isomorphism decision problems are all solvable in these groups.
Moreover, the nonvirtually nilpotent ones exhibit an exponential growth rate.
These properties make them suitable for use in groupbased cryptography, which
was proposed in 2004 by Eick and Kahrobaei. Since then, many cryptosystems have
been created that employ polycyclic groups. These include key exchanges such as
noncommutative ElGamal, authentication schemes based on the twisted conjugacy
problem, and secret sharing via the word problem. In response, heuristic and
deterministic methods of cryptanalysis have been developed, including the
lengthbased and linear decomposition attacks. Despite these efforts, there are
classes of infinite polycyclic groups that remain suitable for cryptography.
The analysis of algorithms for search and decision problems in polycyclic
groups has also been developed. In addition to results for the aforementioned
problems we present those concerning polycyclic representations, group
morphisms, and orbit decidability. Though much progress has been made, many
algorithmic and complexity problems remain unsolved, we conclude with a number
of them. Of particular interest is to show that cryptosystems using infinite
polycyclic groups are resistant to cryptanalysis on a quantum computer.

We prove that one cannot algorithmically decide whether a finitely presented
$\mathbb{Z}$extension admits a finitely generated base group, and we use this
fact to prove the undecidability of the BNS invariant. Furthermore, we show the
equivalence between the isomorphism problem within the subclass of unique
$\mathbb{Z}$extensions, and the semiconjugacy problem for deranged outer
automorphisms.

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.

In this paper we review the HabeebKahrobaeiShpilrain secret sharing scheme
and introduce a variation based on the shortlex order on a free group. Drawing
inspiration from adjustments to classical schemes, we also present a method
that allows for the protocol to remain secure after multiple secrets are
shared.

After the AnshelAnshelGoldfeld (AAG) keyexchange protocol was introduced
in 1999, it was implemented and studied with braid groups and with the Thompson
group as its underlying platforms. The lengthbased attack, introduced by
Hughes and Tannenbaum, has been used to extensively study AAG with the braid
group as the underlying platform. Meanwhile, a new platform, using polycyclic
groups, was proposed by Eick and Kahrobaei.
In this paper, we show that with a high enough Hirsch length, the polycyclic
group as an underlying platform for AAG is resistant to the lengthbased
attack. In particular, polycyclic groups could provide a secure platform for
any cryptosystem based on conjugacy search problem such as noncommutative
DiffieHellman, ElGamal and CramerShoup key exchange protocols.

In this paper we introduce a polynomial time algorithm that solves both the
conjugacy decision and search problems in free abelianbyinfinite cyclic
groups where the input is elements in normal form. We do this by adapting the
work of Bogopolski, Martino, Maslakova, and Ventura in
\cite{bogopolski2006conjugacy} and Bogopolski, Martino, and Ventura in
\cite{bogopolski2010orbit}, to free abelianbyinfinite cyclic groups, and in
certain cases apply a polynomial time algorithm for the orbit problem over
$\Z^n$ by Kannan and Lipton.

In this paper we study the conjugacy problem in polycyclic groups. Our main
result is that we construct polycyclic groups $G_n$ whose conjugacy problem is
at least as hard as the subset sum problem with $n$ indeterminates. As such,
the conjugacy problem over the groups $G_n$ is NPcomplete where the parameters
of the problem are taken in terms of $n$ and the length of the elements given
on input.

In his paper Stadler develops techniques for improving the security of
existing secret sharing protocols by allowing to check whether the secret
shares given out by the dealer are valid. In particular, the secret sharing is
executed over abelian groups. In this paper we develop similar methods over
nonabelian groups.

Garber, Kahrobaei, and Lam studied polycyclic groups generated by number
field as platform for the AAG keyexchange protocol. In this paper, we discuss
the use of a different kind of polycyclic groups, Heisenberg groups, as a
platform group for AAG by submitting Heisenberg groups to one of AAG's major
attacks, the lengthbased attack.

We propose a cryptosystem based on matrices over group rings and claim that
it is secure against adaptive chosen ciphertext attack.

This communication records some observations made in the course of studying
onerelator groups from the point of view of residual solvability. As a
contribution to clas sification efforts we single out some relator types that
render the corresponding onerelator groups residually solvable.

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.

A method for nonabelian CramerShoup cryptosystem is presented. The role of
decision and search is explored, and the platform of solvable/polycyclic group
is suggested. In the process we review recent progress in nonabelian
cryptography and post some open problems that naturally arise from this path of
research.

An abelian extension of the special orthogonal Lie algebra $D_n$ is a
nonsemisimple Lie algebra $D_n \inplus V$, where $V$ is a finitedimensional
representation of $D_n$, with the understanding that $[V,V]=0$. We determine
all abelian extensions of $D_n$ that may be embedded into the exceptional Lie
algebra $E_{n+1}$, $n=5, 6$, and 7. We then classify these embeddings, up to
inner automorphism. As an application, we also consider the restrictions of
irreducible representations of $E_{n+1}$ to $D_n \inplus V$, and discuss which
of these restrictions are or are not indecomposable.

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.

The objective of this work is to survey several digital signatures proposed
in the last decade using noncommutative groups and rings and propose a digital
signature using noncommutative groups and analyze its security.

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.