The status of polycyclic group-based cryptography: a survey and open problems
From MaRDI portal
(Redirected from Publication:338844)
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
- 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?)
- 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 Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
- An algebraic method for public-key cryptography
- 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
- 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
(13)- Length-based attacks in polycyclic groups
- GENERAL ALGEBRAIC CRYPTOGRAPHIC KEY EXCHANGE SCHEME AND ITS CRYPTANALYSIS
- Two general schemes of algebraic cryptography
- scientific article; zbMATH DE number 7554059 (Why is no real title available?)
- Algorithms for twisted conjugacy classes of polycyclic-by-finite groups
- Algorithmic problems in Engel groups and cryptographic applications
- Efficient and secure delegation of exponentiation in general groups to a single malicious server
- The Reidemeister spectrum of 2-step nilpotent groups determined by graphs
- Cryptanalysis of a combinatorial public key cryptosystem
- Solving the conjugacy decision problem via machine learning
- Analysis of a certain polycyclic-group-based cryptosystem
- Evolution of group-theoretic cryptology attacks using hyper-heuristics
- A nonlinear decomposition method in analysis of some encryption schemes using group automorphisms
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)
