The status of polycyclic group-based cryptography: a survey and open problems
From MaRDI portal
Publication:338844
DOI10.1515/GCC-2016-0013zbMATH Open1353.94050arXiv1607.05819OpenAlexW2963307827MaRDI QIDQ338844FDOQ338844
Authors: Jonathan Gryak, Delaram Kahrobaei 
Publication date: 7 November 2016
Published in: Groups - Complexity - Cryptology (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1607.05819
Recommendations
Cryptography (94A60) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Cites Work
- Title not available (Why is that?)
- An algebraic method for public-key cryptography
- The conjugacy search problem in public key cryptography: unnecessary and insufficient
- The automorphism group of a polycyclic group
- Growth of finitely generated solvable groups and curvature of Riemannian manifolds
- Title not available (Why is that?)
- Length Based Attack and Braid Groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key Exchange Protocol
- Growth of finitely generated solvable groups
- On homomorphisms onto finite groups
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
- Title not available (Why is that?)
- Conjugacy in polycyclic groups
- Conjugate separability in polycyclic groups
- Efficient collection in infinite polycyclic groups.
- A practical algorithm for finding matrix representations for polycyclic groups
- Length-based attacks in polycyclic groups
- Vulnerability of cryptographic primitives based on the power conjugacy search problem in quantum computing
- A linear decomposition attack
- Using the Mal'cev correspondence for collection in polycyclic groups.
- Matrix representations for torsion-free nilpotent groups by Deep Thought.
- Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography
- A secret sharing scheme based on group presentations and the word problem
- Non-commutative digital signatures
- Search and witness problems in group theory.
- Title not available (Why is that?)
- POLYCYCLIC GROUPS, ANALYTIC GROUPS AND ALGEBRAIC GROUPS
- Random subgroups and analysis of the length-based and quotient attacks
- Title not available (Why is that?)
- Using the subgroup membership search problem in public key cryptography
- Orbit decidability and the conjugacy problem for some extensions of groups.
- The twisted conjugacy problem for endomorphisms of polycyclic groups
- Decidable Properties of Polycyclic Groups
- WHEN IS THE AUTOMORPHISM GROUP OF A VIRTUALLY POLYCYCLIC GROUP VIRTUALLY POLYCYCLIC?
- Title not available (Why is that?)
- On the orbit-stabilizer problem for integral matrix actions of polycyclic groups
- Two Remarks on Polycyclic Groups
- Authentication schemes from actions on graphs, groups, or rings
- Analysis of a certain polycyclic-group-based cryptosystem
- Collection from the left and other strategies
Cited In (13)
- Length-based attacks in polycyclic groups
- Two general schemes of algebraic cryptography
- Title not available (Why is that?)
- 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
- Solving the conjugacy decision problem via machine learning
- Cryptanalysis of a combinatorial public key cryptosystem
- 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
- GENERAL ALGEBRAIC CRYPTOGRAPHIC KEY EXCHANGE SCHEME AND ITS CRYPTANALYSIS
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)
