  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 non-virtually nilpotent ones exhibit an exponential growth rate.
These properties make them suitable for use in group-based 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
non-commutative 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
length-based 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.
