The status of polycyclic group-based cryptography: a survey and open problems
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- A linear decomposition attack
- A practical algorithm for finding matrix representations for polycyclic groups
- A secret sharing scheme based on group presentations and the word problem
- An algebraic method for public-key cryptography
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
- Analysis of a certain polycyclic-group-based cryptosystem
- Authentication schemes from actions on graphs, groups, or rings
- Collection from the left and other strategies
- Conjugacy in polycyclic groups
- Conjugate separability in polycyclic groups
- Decidable Properties of Polycyclic Groups
- Efficient collection in infinite polycyclic groups.
- Growth of finitely generated solvable groups
- Growth of finitely generated solvable groups and curvature of Riemannian manifolds
- scientific article; zbMATH DE number 5982274 (Why is no real title available?)
- scientific article; zbMATH DE number 5380256 (Why is no real title available?)
- scientific article; zbMATH DE number 1759777 (Why is no real title available?)
- scientific article; zbMATH DE number 2133330 (Why is no real title available?)
- scientific article; zbMATH DE number 2144695 (Why is no real title available?)
- scientific article; zbMATH DE number 799789 (Why is no real title available?)
- Length Based Attack and Braid Groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key Exchange Protocol
- Length-based attacks in polycyclic groups
- Matrix representations for torsion-free nilpotent groups by Deep Thought.
- Non-commutative digital signatures
- On homomorphisms onto finite groups
- On the orbit-stabilizer problem for integral matrix actions of polycyclic groups
- Orbit decidability and the conjugacy problem for some extensions of groups.
- POLYCYCLIC GROUPS, ANALYTIC GROUPS AND ALGEBRAIC GROUPS
- Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography
- Random subgroups and analysis of the length-based and quotient attacks
- Search and witness problems in group theory.
- The automorphism group of a polycyclic group
- The conjugacy search problem in public key cryptography: unnecessary and insufficient
- The twisted conjugacy problem for endomorphisms of polycyclic groups
- Two Remarks on Polycyclic Groups
- Using the Mal'cev correspondence for collection in polycyclic groups.
- Using the subgroup membership search problem in public key cryptography
- Vulnerability of cryptographic primitives based on the power conjugacy search problem in quantum computing
- WHEN IS THE AUTOMORPHISM GROUP OF A VIRTUALLY POLYCYCLIC GROUP VIRTUALLY POLYCYCLIC?
Cited in
(17)- Cryptanalysis of a combinatorial public key cryptosystem
- Evolution of group-theoretic cryptology attacks using hyper-heuristics
- Efficient and secure delegation of exponentiation in general groups to a single malicious server
- Length-based attacks in polycyclic groups
- Two general schemes of algebraic cryptography
- Algorithms for twisted conjugacy classes of polycyclic-by-finite groups
- Solving the conjugacy decision problem via machine learning
- scientific article; zbMATH DE number 7554059 (Why is no real title available?)
- Algorithmic problems in Engel groups and cryptographic applications
- GENERAL ALGEBRAIC CRYPTOGRAPHIC KEY EXCHANGE SCHEME AND ITS CRYPTANALYSIS
- A nonlinear decomposition method in analysis of some encryption schemes using group automorphisms
- The Reidemeister spectrum of 2-step nilpotent groups determined by graphs
- Investigation of metabelian platform groups for protocols based on (simultaneous) conjugacy search problem
- Computational group theory: bedrock and new frontiers
- KoKa-DSS: a group-based digital signature scheme
- Cryptanalysis of some nonabelian group-based key exchange protocols
- Analysis of a certain polycyclic-group-based cryptosystem
This page was built for publication: The status of polycyclic group-based cryptography: a survey and open problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q338844)
