The status of polycyclic group-based cryptography: A survey and open problems
---
paper_title: Algorithms for quantum computation: discrete logarithms and factoring

paper_content:

A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor: It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems. We thus give the first examples of quantum cryptanalysis. >
---
paper_title: New Public-Key Cryptosystem Using Braid Groups

paper_content:

The braid groups are infinite non-commutative groups naturally arising from geometric braids. The aim of this article is twofold. One is to show that the braid groups can serve as a good source to enrich cryptography. The feature that makes the braid groups useful to cryptography includes the followings: (i) The word problem is solved via a fast algorithm which computes the canonical form which can be efficiently manipulated by computers. (ii) The group operations can be performed efficiently. (iii) The braid groups have many mathematically hard problems that can be utilized to design cryptographic primitives. The other is to propose and implement a new key agreement scheme and public key cryptosystem based on these primitives in the braid groups. The efficiency of our systems is demonstrated by their speed and information rate. The security of our systems is based on topological, combinatorial and group-theoretical problems that are intractible according to our current mathematical knowledge. The foundation of our systems is quite different from widely used cryptosystems based on number theory, but there are some similarities in design.
---
paper_title: Non-commutative Cryptography and Complexity of Group-theoretic Problems

paper_content:

This book is about relations between three different areas of mathematics and theoretical computer science: combinatorial group theory, cryptography, and complexity theory. It explores how non-commutative (infinite) groups, which are typically studied in combinatorial group theory, can be used in public-key cryptography. It also shows that there is remarkable feedback from cryptography to combinatorial group theory because some of the problems motivated by cryptography appear to be new to group theory, and they open many interesting research avenues within group theory. In particular, a lot of emphasis in the book is put on studying search problems, as compared to decision problems traditionally studied in combinatorial group theory. Then, complexity theory, notably generic-case complexity of algorithms, is employed for cryptanalysis of various cryptographic protocols based on infinite groups, and the ideas and machinery from the theory of generic-case complexity are used to study asymptotically dominant properties of some infinite groups that have been applied in public-key cryptography so far. This book also describes new interesting developments in the algorithmic theory of solvable groups and another spectacular new development related to complexity of group-theoretic problems, which is based on the ideas of compressed words and straight-line programs coming from computer science.
---
paper_title: Collection from the left and other strategies

paper_content:

We describe experiments with various collection strategies for the multiplication of elements of a p-group. We conclude that collection from the left is a very good strategy, then analyse the computational complexity of collection from the left, and compare it with that of collection from the right. Collection from the left also appears to be an excellent strategy for the multiplication of elements of a finite soluble group.
---
paper_title: Handbook of Computational Group Theory

paper_content:

History of Computational Group Theory BACKGROUND MATERIALS Fundamentals Group Actions Series Presentation of Groups Presentation of Subgroups Abelian Group Presentations Representation Theory, Modules, Extension, Derivations, and Complements Field Theory REPRESENTING GROUPS ON A COMPUTER Representing Groups on Computers The Use of Random Methods in CGT Some Structural Calculators Computing with Homorphisms COMPUTATION IN FINITE PERMUTATION GROUPS The Calculation of Orbits and Stabilizers Testing for Alt (W) and Sym (W) Finding Block Systems Bases and Strong Generating Sets Homomorphisms from Permutation Groups Backtrack Searches Sylow Subgroups, P-cores, and the Solvable Radical Applications COSET ENUMERATION The Basic Procedure Strategies for Coset Enumeration Presentations of Subgroups Finding All Subgroups Finding All Subgroups Up to a Given Index Applications PRESENTATION OF GIVEN GROUPS Finding a Presentation of a Given Group Finding a Presentation of a Strong Generating Set The Sims 'Verify' Algorithm REPRESENTATIONS, COHOMOLOGY, AND CHARACTERS Computation in Finite Fields Elemetary Computational Linear Algebra Factorizing Polynomials Over Finite Fields Testing KG-Models for Irreducibility - The Meataxe Related Computations Cohomology Computing Character Tables Structural Investigation of Matrix Groups COMPUTATION WITH POLYCYCLIC GROUPS Polycyclic Presentations Examples of Polycyclic Groups Subgroups and Membership Testing Factor Groups and Homomorphisms Subgroup Series Orbit-Stabilizer Methods Complements and Extensions Intersections, Centralizers, and Normalizers Automorphism Groups The Structure of Finite Solvable Groups COMPUTING QUOTIENTS OF FINITELY PRESENTED GROUPS Finite Quotients and Automorphism Groups of Finite Groups Abelian Quotients Practical Computation of the HNF and SNF P-Quotients of Finitely-Presented Groups ADVANCED COMPUTATIONS IN FINITE GROUPS Some Useful Subgroups Computing Composition and Chief Series Applications of the Solvable Radical Method Computing the Subgroups of a Finite Group Appication - Enumerating Finite Unlabelled Structures LIBRARIES AND DATABASES Primitive Permutation Groups Transitive Permutation Groups Perfect Groups The Small Groups Library Crystallorgraphic Groups Other Databases REWRITING SYSTEMS Monoid Systems Rewriting Systems Rewriting Systems in Monoids and Groups Rewriting Systems for Polycyclic Groups Verifying Nilpotency Applications FINITE STATE AUTOMATA AND AUTOMATIC GROUPS Finite State Automata Automatic Groups The Algorithm to Compute Shortlex Automatic Structures Related Algorithms Applications
---
paper_title: Efficient Collection in Infinite Polycyclic Groups

paper_content:

We present and analyse an algorithm for collection in polycyclic groups which has better complexity in terms of the exponents occurring in the collected words than previously used collection algorithms, and yields a much better performance especially for infinite polycyclic groups.
---
paper_title: Using the Mal’cev correspondence for collection in polycyclic groups

paper_content:

Abstract We describe several approaches for realizing the Mal'cev correspondence between Q -powered nilpotent groups and nilpotent Lie algebras over Q . We apply it to fast collection in polycyclic groups. Our methods are fully implemented and publicly available. We report on the implementation and give runtimes for some example groups.
---
paper_title: Matrix representations for torsion-free nilpotent groups by Deep Thought

paper_content:

Abstract We present an algorithm for calculating a representation by unitriangular matrices over the integers of a finitely-generated torsion-free nilpotent group given by a polycyclic presentation. The algorithm uses polynomials computed by the Deep Thought algorithm which describe the multiplication in the given group. The algorithm is more efficient than a previous method.
---
paper_title: A Practical Algorithm for Finding Matrix Representations for Polycyclic Groups

paper_content:

In this paper we describe a new algorithm for constructing a representation by integer matrices for a polycyclic group given by a finite presentation. This is a first step toward finding a practical algorithm for this problem. We used our algorithm to construct representations for various polycyclic groups. The examples which we studied included a collection of free nilpotent groups, and our results here led us to a new theoretical result concerning such groups.
---
paper_title: Growth of finitely generated solvable groups and curvature of Riemanniann manifolds

paper_content:

If a group Γ is generated by a finite subset 5, then one has the "growth function" gs, where gs(m) is the number of distinct elements of Γ expressible as words of length <m on 5. Roughly speaking, J. Milnor [9] shows that the asymptotic behaviour of gs does not depend on choice of finite generating set S c Γ, and that lower (resp. upper) bounds on the curvature of a riemannian manifold M result in upper (resp. lower) bounds on the growth function of π^M). The types of bounds on the growth function are
---
paper_title: �ber unendliche diskontinuierliche Gruppen

paper_content:

A fluid metering apparatus having paired cylinders, pistons and piston rods. The piston rods are connected to a lever or walking beam which, when pivoted at its center equidistant between the rod connections provides controlled equal travel distance and rate for the pistons providing equal cubic displacement in the cylinders. When the beam is pivoted off-center closer to one rod connection than to the other, the piston on the closer rod travels a shorter distance at a slower rate than the other piston providing unequal cubic displacement in the cylinders. In either case the quantities are measured proportionally to one another in the same period of time. The system is controlled by air cylinders and valves actuated by the reference piston rod. Telltale indicators are carried by the air cylinders to visually show any malfunction at each air cylinder individually. Automatic system operation is provided for continuous metering. Automatic system shut-down closes all valves at the material inlets and outlets sealing the resin, hardener, etc. in stable condition for resumption of metering.
---
paper_title: Conjugate Separability in Polycyclic Groups

paper_content:

A group G is said to be conjugate separable if, whenever x and y are elements of G which are not conjugate, there is a finite homomorphic image of G in which the images of x and y are not conjugate. The main result of this paper is that polycyclic-by-finite groups are conjugate separable. Conjugate separability was introduced by Blackburn [2], who showed that finitely generated torsion-free nilpotent groups are conjugate separable. This was extended to supersolvable groups by Kargapolov [5], and to finitely generated nilpotent-by-finite groups by Toh [8]. Remeslennikov [6] obtained the same result as this paper. His proof contained a number of mistakes, but Hartley’s review [MR43, #6313] pointed out that these could be corrected. This paper is taken from my Ph.D. thesis, Rice University, 1970, written under the direction of Steve Gersten. I did not become aware of Remeslennikov’s proof until after I has left Rice University. Both of our proofs are based on a number theoretic result of Chevalley [3]. The main difference between them is that Remeslennikov reduces directly to Chevalley’s result while I first extend Chevalley’s result to certain matrix groups, showing that they have the “congruence subgroup property.” The present form of the paper is a redraft, written in 1975, of a version submitted in April, 1970, and the following changes have been made. (1) Remeslennikov’s work has been acknowledged. (2) Some arguments have been shortened, and I have taken advantage of five years’ experience to improve the writing style. Here is an outline of the proof. Let
---
paper_title: Search and witness problems in group theory

paper_content:

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.
---
paper_title: On the orbit-stabilizer problem for integral matrix actions of polycyclic groups

paper_content:

We present an algorithm to solve the orbit-stabilizer problem for a polycyclic group G acting as a subgroup of GL(d, Z) on the elements of Qd. We report on an implementation of our method and use this to observe that the algorithm is practical.
---
paper_title: The twisted conjugacy problem for endomorphisms of polycyclic groups

paper_content:

Abstract An algorithm is constructed that, when given an explicit presentation of a polycyclic group G, decides for any endomorphism ψ ∈ End(G) and any pair of elements u, v ∈ G, whether or not the equation (xψ)u = vx has a solution x ∈ G. Thus it is shown that the problem of the title is decidable. Also we present an algorithm that produces a finite set of generators of the subgroup Fix ψ (G) ⩽ G of all ψ-invariant elements of G.
---
paper_title: WHEN IS THE AUTOMORPHISM GROUP OF A VIRTUALLY POLYCYCLIC GROUP VIRTUALLY POLYCYCLIC?

paper_content:

The automorphism group of a virtually polycyclic group $G$ is either virtually polycyclic or it contains a non-abelian free subgroup. We describe conditions on the structure of $G$ to decide which of the two alternatives occurs for $Aut(G).$
---
paper_title: Orbit decidability and the conjugacy problem for some extensions of groups

paper_content:

Given a short exact sequence of groups with certain conditions, $1\to F\to G\to H\to 1$, we prove that $G$ has solvable conjugacy problem if and only if the corresponding action subgroup $A\leqslant Aut(F)$ is orbit decidable. From this, we deduce that the conjugacy problem is solvable, among others, for all groups of the form $\mathbb{Z}^2\rtimes F_m$, $F_2\rtimes F_m$, $F_n \rtimes \mathbb{Z}$, and $\mathbb{Z}^n \rtimes_A F_m$ with virtually solvable action group $A\leqslant GL_n(\mathbb{Z})$. Also, we give an easy way of constructing groups of the form $\mathbb{Z}^4\rtimes F_n$ and $F_3\rtimes F_n$ with unsolvable conjugacy problem. On the way, we solve the twisted conjugacy problem for virtually surface and virtually polycyclic groups, and give an example of a group with solvable conjugacy problem but unsolvable twisted conjugacy problem. As an application, an alternative solution to the conjugacy problem in $Aut(F_2)$ is given.
---
paper_title: Vulnerability of Cryptographic Primitives Based on the Power Conjugacy Search Problem in Quantum Computing

paper_content:

This paper shows the existence of an efficient algorithm to solve the generalized discrete logarithm problem in quantum computing by reducing it to the Abelian hidden subgroup problem. The proposed method can also efficiently solve a partial power conjugacy search problem whose complexity in some groups underlies the resistance of several cryptographic systems and protocols in quantum computing.
---
paper_title: An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups

paper_content:

In this paper we extend the algorithm for extraspecial groups in \cite{iss07}, and show that the hidden subgroup problem in nil-2 groups, that is in groups of nilpotency class at most 2, can be solved efficiently by a quantum procedure. The algorithm presented here has several additional features. It contains a powerful classical reduction for the hidden subgroup problem in nilpotent groups of constant nilpotency class to the specific case where the group is a $p$-group of exponent $p$ and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently.
---
paper_title: The Conjugacy Search Problem in Public Key Cryptography: Unnecessary and Insufficient

paper_content:

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.
---
paper_title: Length Based Attack and Braid Groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key Exchange Protocol

paper_content:

The length based attack on Anshel-Anshel-Goldfeld commutator key-exchange protocol [1] was initially proposed by Hughes and Tannenbaum in [9]. Several attempts have been made to implement the attack [6], but none of them had produced results convincing enough to believe that attack works. In this paper we show that accurately designed length based attack can successfully break a random instance of the simultaneous conjugacy search problem for certain parameter values and argue that the public/private information chosen uniformly random leads to weak keys.
---
paper_title: New Public-Key Cryptosystem Using Braid Groups

paper_content:

The braid groups are infinite non-commutative groups naturally arising from geometric braids. The aim of this article is twofold. One is to show that the braid groups can serve as a good source to enrich cryptography. The feature that makes the braid groups useful to cryptography includes the followings: (i) The word problem is solved via a fast algorithm which computes the canonical form which can be efficiently manipulated by computers. (ii) The group operations can be performed efficiently. (iii) The braid groups have many mathematically hard problems that can be utilized to design cryptographic primitives. The other is to propose and implement a new key agreement scheme and public key cryptosystem based on these primitives in the braid groups. The efficiency of our systems is demonstrated by their speed and information rate. The security of our systems is based on topological, combinatorial and group-theoretical problems that are intractible according to our current mathematical knowledge. The foundation of our systems is quite different from widely used cryptosystems based on number theory, but there are some similarities in design.
---
paper_title: NIS05-6: A Non-Commutative Generalization of ElGamal Key Exchange using Polycyclic Groups

paper_content:

In this paper, we propose a non-commutative key-exchange scheme which generalizes the classical ElGamal Cipher to polycyclic groups. We describe the criteria for groups which would provide good candidates for such cryptosystems, we also examine the complexity of the decision problems related to these key exchange.
---
paper_title: Using the subgroup membership search problem in public key cryptography

paper_content:

There are several public key protocols around that use the computational hardness of either the conjugacy search problem or the word (search) problem for nonabelian groups. In this paper, we describe a cryptosystem whose security is based on the computational hardness of the subgroup membership (search) problem: given a group G, a subgroup H generated by h1, . . . , hk, and an element h ∈ H, find an expression of h in terms of h1, . . . , hk. It is also interesting to note that groups which we suggest to use as the platform, free metabelian groups, are infinitely presented, in contrast with groups typically used in public key cryptography. Nevertheless, these group have efficiently (and, in fact, very easily) solvable word problem.
---
paper_title: An authentication scheme based on the twisted conjugacy problem

paper_content:

The conjugacy search problem in a group G is the problem of recovering an x ∈ G from given g ∈ G and h = x-1gx. 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) θ, ψ of a group G and a pair of elements ω, t ∈ G, find an element s ∈ G such that t = ψ(s-1)ωθ(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 2 × 2 matrices over truncated one-variable polynomials over F2, the field of two elements, with transposition used instead of inversion in the equality above.
---
paper_title: Zero-knowledge authentication schemes from actions on graphs, groups, or rings

paper_content:

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any speciflc algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include Graph Colorability, Diophantine Problem, and many others.
---
paper_title: A Secret Sharing Scheme Based on Group Presentations and the Word Problem

paper_content:

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.
---
paper_title: Length-Based Attacks for Certain Group Based Encryption Rewriting Systems

paper_content:

In this note, we describe a probabilistic attack on public key cryptosystems based on the word/conjugacy problems for finitely presented groups of the type proposed recently by Anshel, Anshel and Goldfeld. In such a scheme, one makes use of the property that in the given group the word problem has a polynomial time solution, while the conjugacy problem has no known polynomial solution. An example is the braid group from topology in which the word problem is solvable in polynomial time while the only known solutions to the conjugacy problem are exponential. The attack in this paper is based on having a canonical representative of each string relative to which a length function may be computed. Hence the term length attack. Such canonical representatives are known to exist for the braid group.
---
paper_title: Length Based Attack and Braid Groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key Exchange Protocol

paper_content:

The length based attack on Anshel-Anshel-Goldfeld commutator key-exchange protocol [1] was initially proposed by Hughes and Tannenbaum in [9]. Several attempts have been made to implement the attack [6], but none of them had produced results convincing enough to believe that attack works. In this paper we show that accurately designed length based attack can successfully break a random instance of the simultaneous conjugacy search problem for certain parameter values and argue that the public/private information chosen uniformly random leads to weak keys.
---
paper_title: Random subgroups and analysis of the length-based and quotient attacks

paper_content:

A method for positioning and rotating a workpiece shaped like a body of rotation and having a plane face, comprising the following steps: positioning the workpiece on an axial and a radial supports; transmitting the torque from a rotary driving member to the workpiece due to the forces of friction developed therebetween; and feeding ultrasonic mechanical vibrations to at least one of the supports, said vibrations being fed to any one of the supports in the direction substantially parallel to or at an angle not exceeding 10 degrees with the line of contact between the workpiece and said support. An arrangement implementing this method comprises separate axial and radial supports, the radial support being constituted by two parts spaced apart through a certain angle and having the profile, in the working portion, congruent to the cylindrical profile of the workpiece surface. The arrangement is further provided with a frictional rotary driving member contacting with the workpiece to be machined, and with an electromechanical magnetostriction converter operating within the ultrasonic range and having a waveguide rigidly connected to both converter and support, mechanical vibrations being fed thereto.
---
paper_title: WHEN IS THE AUTOMORPHISM GROUP OF A VIRTUALLY POLYCYCLIC GROUP VIRTUALLY POLYCYCLIC?

paper_content:

The automorphism group of a virtually polycyclic group $G$ is either virtually polycyclic or it contains a non-abelian free subgroup. We describe conditions on the structure of $G$ to decide which of the two alternatives occurs for $Aut(G).$
---
paper_title: Using the Mal’cev correspondence for collection in polycyclic groups

paper_content:

Abstract We describe several approaches for realizing the Mal'cev correspondence between Q -powered nilpotent groups and nilpotent Lie algebras over Q . We apply it to fast collection in polycyclic groups. Our methods are fully implemented and publicly available. We report on the implementation and give runtimes for some example groups.
---
paper_title: On the orbit-stabilizer problem for integral matrix actions of polycyclic groups

paper_content:

We present an algorithm to solve the orbit-stabilizer problem for a polycyclic group G acting as a subgroup of GL(d, Z) on the elements of Qd. We report on an implementation of our method and use this to observe that the algorithm is practical.
---
paper_title: Orbit decidability and the conjugacy problem for some extensions of groups

paper_content:

Given a short exact sequence of groups with certain conditions, $1\to F\to G\to H\to 1$, we prove that $G$ has solvable conjugacy problem if and only if the corresponding action subgroup $A\leqslant Aut(F)$ is orbit decidable. From this, we deduce that the conjugacy problem is solvable, among others, for all groups of the form $\mathbb{Z}^2\rtimes F_m$, $F_2\rtimes F_m$, $F_n \rtimes \mathbb{Z}$, and $\mathbb{Z}^n \rtimes_A F_m$ with virtually solvable action group $A\leqslant GL_n(\mathbb{Z})$. Also, we give an easy way of constructing groups of the form $\mathbb{Z}^4\rtimes F_n$ and $F_3\rtimes F_n$ with unsolvable conjugacy problem. On the way, we solve the twisted conjugacy problem for virtually surface and virtually polycyclic groups, and give an example of a group with solvable conjugacy problem but unsolvable twisted conjugacy problem. As an application, an alternative solution to the conjugacy problem in $Aut(F_2)$ is given.
---
paper_title: �ber unendliche diskontinuierliche Gruppen

paper_content:

A fluid metering apparatus having paired cylinders, pistons and piston rods. The piston rods are connected to a lever or walking beam which, when pivoted at its center equidistant between the rod connections provides controlled equal travel distance and rate for the pistons providing equal cubic displacement in the cylinders. When the beam is pivoted off-center closer to one rod connection than to the other, the piston on the closer rod travels a shorter distance at a slower rate than the other piston providing unequal cubic displacement in the cylinders. In either case the quantities are measured proportionally to one another in the same period of time. The system is controlled by air cylinders and valves actuated by the reference piston rod. Telltale indicators are carried by the air cylinders to visually show any malfunction at each air cylinder individually. Automatic system operation is provided for continuous metering. Automatic system shut-down closes all valves at the material inlets and outlets sealing the resin, hardener, etc. in stable condition for resumption of metering.
---

Title: The Status of Polycyclic Group-Based Cryptography: A Survey and Open Problems

Section 1: Introduction
Description 1: Introduce polycyclic group-based cryptography, its motivations, and the scope of the paper.

Section 2: Algorithmic Problems in Polycyclic Groups
Description 2: Discuss various algorithmic representations and related decision problems in polycyclic groups.

Section 3: Cryptosystems
Description 3: Describe different cryptosystems that employ polycyclic groups, including key exchanges, digital signatures, and secret sharing schemes.

Section 4: Cryptanalysis and Attacks
Description 4: Present an overview of attacks on polycyclic group-based cryptosystems, focusing on specific vulnerabilities and methods.

Section 5: Conclusion
Description 5: Summarize the findings and the current state of polycyclic group-based cryptography research.

Section 6: Open Problems
Description 6: Provide a list of unresolved computational and algorithmic questions in the field, highlighting areas for future research.