2016/07/20 by Jonathan Gryak, Gryak, Jonathan, Delaram Kahrobaei +1
Mathematics · Computer Science · #Geometric and Algebraic Topology #Coding theory and cryptography #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1607.05819
Polycyclic groups are natural generalizations of cyclic groups but with more\ncomplicated algorithmic properties. They are finitely presented and the word,\nconjugacy, and isomorphism decision problems are all solvable in these groups.\nMoreover, the non-virtually nilpotent ones exhibit an exponential growth rate.\nThese properties make them suitable for use in group-based cryptography, which\nwas proposed in 2004 by Eick and Kahrobaei. Since then, many cryptosystems have\nbeen created that employ polycyclic groups. These include key exchanges such as\nnon-commutative ElGamal, authentication schemes based on the twisted conjugacy\nproblem, and secret sharing via the word problem. In response, heuristic and\ndeterministic methods of cryptanalysis have been developed, including the\nlength-based and linear decomposition attacks. Despite these efforts, there are\nclasses of infinite polycyclic groups that remain suitable for cryptography.\nThe analysis of algorithms for search and decision problems in polycyclic\ngroups has also been developed. In addition to results for the aforementioned\nproblems we present those concerning polycyclic representations, group\nmorphisms, and orbit decidability. Though much progress has been made, many\nalgorithmic and complexity problems remain unsolved, we conclude with a number\nof them. Of particular interest is to show that cryptosystems using infinite\npolycyclic groups are resistant to cryptanalysis on a quantum computer.\n