• ### The Hidden Subgroup Problem and Post-quantum Group-based Cryptography(1805.04179)

May 10, 2018 quant-ph, cs.CR, math.GR, cs.CC
In this paper we discuss the Hidden Subgroup Problem (HSP) in relation to post-quantum group-based cryptography. We review the relationship between HSP and other computational problems discuss an optimal solution method, and review the known results about the quantum complexity of HSP. We also overview some platforms for group-based cryptosystems. Notably, efficient algorithms for solving HSP in such infinite group platforms are not yet known.
• ### Some applications of arithmetic groups in cryptography(1803.11528)

March 30, 2018 math.GR
In this paper we will give various examples of exponentially distorted subgroups in linear groups, including some new example of subgroups of $SL_n(\mathbb{Z}[x])$ for $n \ge 3$, and show how they can be used to construct symmetric-key cryptographic platforms.
• ### Solving the Conjugacy Decision Problem via Machine Learning(1705.10417)

Feb. 21, 2018 math.GR, cs.LG
Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this paper, we seek to extend these techniques to finitely presented non-free groups, with a particular emphasis on polycyclic and metabelian groups that are of interest to non-commutative cryptography. As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The accuracies of classifiers created using decision trees, random forests, and N-tuple neural network models are evaluated for several non-free groups. The very high accuracy of these classifiers suggests an underlying mathematical relationship with respect to conjugacy in the tested groups.
• ### Algorithmic problems in right-angled Artin groups: complexity and applications(1802.04870)

Feb. 20, 2018 math.AT, math.GT, math.GR
In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography.
• ### On the Conjugacy Problem in Certain Metabelian Groups(1610.06503)

Dec. 22, 2017 math.GR, cs.CC
Weanalyzethecomputationalcomplexityofanalgorithmtosolve the conjugacy search problem in a certain family of metabelian groups. We prove that in general the time complexity of the conjugacy search problem for these groups is at most exponential. For a subfamily of groups we prove that the conjugacy search problem is polynomial. We also show that for a different subfamily the conjugacy search problem reduces to the discrete logarithm problem.
• ### Cryptography with right-angled Artin groups(1610.06495)

Feb. 13, 2017 cs.CR, math.GR
In this paper we propose right-angled Artin groups as a platform for secret sharing schemes based on the efficiency (linear time) of the word problem. Inspired by previous work of Grigoriev-Shpilrain in the context of graphs, we define two new problems: Subgroup Isomorphism Problem and Group Homomorphism Problem. Based on them, we also propose two new authentication schemes. For right-angled Artin groups, the Group Homomorphism and Graph Homomorphism problems are equivalent, and the later is known to be NP-complete. In the case of the Subgroup Isomorphism problem, we bring some results due to Bridson who shows there are right-angled Artin groups in which this problem is unsolvable.
• ### Cryptosystems using subgroup distortion(1610.07515)

Oct. 24, 2016 cs.CR, math.GR
In this paper we propose cryptosystems based on subgroup distortion in hyperbolic groups. We also include concrete examples of hyperbolic groups as possible platforms.
• ### The Status of Polycyclic Group-Based Cryptography: A Survey and Open Problems(1607.05819)

Oct. 22, 2016 cs.CR, math.GR
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.
• ### Algorithmic recognition of infinite cyclic extensions(1509.05879)

Oct. 3, 2016 math.GR
We prove that one cannot algorithmically decide whether a finitely presented $\mathbb{Z}$-extension admits a finitely generated base group, and we use this fact to prove the undecidability of the BNS invariant. Furthermore, we show the equivalence between the isomorphism problem within the subclass of unique $\mathbb{Z}$-extensions, and the semi-conjugacy problem for deranged outer automorphisms.
• ### Using semidirect product of (semi)groups in public key cryptography(1604.05542)

April 19, 2016 cs.CR, math.GR
In this survey, we describe a general key exchange protocol based on semidirect product of (semi)groups (more specifically, on extensions of (semi)groups by automorphisms), and then focus on practical instances of this general idea. This protocol can be based on any group or semigroup, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when this protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. The focus then shifts to selecting an optimal platform (semi)group, in terms of security and efficiency. We show, in particular, that one can get a variety of new security assumptions by varying an automorphism used for a (semi)group extension.
• ### Secret Sharing using Non-Commutative Groups and the Shortlex Order(1311.7117)

Dec. 15, 2014 cs.CR, math.GR
In this paper we review the Habeeb-Kahrobaei-Shpilrain secret sharing scheme and introduce a variation based on the shortlex order on a free group. Drawing inspiration from adjustments to classical schemes, we also present a method that allows for the protocol to remain secure after multiple secrets are shared.
• ### Length-based attacks in polycyclic groups(1305.0548)

Nov. 22, 2014 cs.CR, math.GR
After the Anshel-Anshel-Goldfeld (AAG) key-exchange protocol was introduced in 1999, it was implemented and studied with braid groups and with the Thompson group as its underlying platforms. The length-based attack, introduced by Hughes and Tannenbaum, has been used to extensively study AAG with the braid group as the underlying platform. Meanwhile, a new platform, using polycyclic groups, was proposed by Eick and Kahrobaei. In this paper, we show that with a high enough Hirsch length, the polycyclic group as an underlying platform for AAG is resistant to the length-based attack. In particular, polycyclic groups could provide a secure platform for any cryptosystem based on conjugacy search problem such as non-commutative Diffie-Hellman, ElGamal and Cramer-Shoup key exchange protocols.
• ### A Polynomial Time Algorithm For The Conjugacy Decision and Search Problems in Free Abelian-by-Infinite Cyclic Groups(1410.5297)

Oct. 20, 2014 math.GR, cs.CC
In this paper we introduce a polynomial time algorithm that solves both the conjugacy decision and search problems in free abelian-by-infinite cyclic groups where the input is elements in normal form. We do this by adapting the work of Bogopolski, Martino, Maslakova, and Ventura in \cite{bogopolski2006conjugacy} and Bogopolski, Martino, and Ventura in \cite{bogopolski2010orbit}, to free abelian-by-infinite cyclic groups, and in certain cases apply a polynomial time algorithm for the orbit problem over $\Z^n$ by Kannan and Lipton.
• ### A family of polycyclic groups over which the uniform conjugacy problem is NP-complete(1403.4153)

Oct. 20, 2014 cs.CR, math.GR, cs.CC
In this paper we study the conjugacy problem in polycyclic groups. Our main result is that we construct polycyclic groups $G_n$ whose conjugacy problem is at least as hard as the subset sum problem with $n$ indeterminates. As such, the conjugacy problem over the groups $G_n$ is NP-complete where the parameters of the problem are taken in terms of $n$ and the length of the elements given on input.
• ### Publicly Verifiable Secret Sharing Using Non-Abelian Groups(1403.3661)

Aug. 27, 2014 cs.CR, math.GR
In his paper Stadler develops techniques for improving the security of existing secret sharing protocols by allowing to check whether the secret shares given out by the dealer are valid. In particular, the secret sharing is executed over abelian groups. In this paper we develop similar methods over non-abelian groups.
• ### Heisenberg Groups as Platform for the AAG key-exchange protocol(1403.4165)

March 17, 2014 cs.CR, math.GR
Garber, Kahrobaei, and Lam studied polycyclic groups generated by number field as platform for the AAG key-exchange protocol. In this paper, we discuss the use of a different kind of polycyclic groups, Heisenberg groups, as a platform group for AAG by submitting Heisenberg groups to one of AAG's major attacks, the length-based attack.
• ### A CCA secure cryptosystem using matrices over group rings(1403.3660)

March 14, 2014 cs.CR, math.GR
We propose a cryptosystem based on matrices over group rings and claim that it is secure against adaptive chosen ciphertext attack.
• ### Some Residually Solvable One-Relator Groups(1310.5241)

Oct. 19, 2013 math.GR
This communication records some observations made in the course of studying one-relator groups from the point of view of residual solvability. As a contribution to clas- sification efforts we single out some relator types that render the corresponding one-relator groups residually solvable.
• ### On the Dimension of Matrix Representations of Finitely Generated Torsion Free Nilpotent Groups(1309.4514)

Sept. 18, 2013 math.GR, cs.CC
It is well known that any polycyclic group, and hence any finitely generated nilpotent group, can be embedded into $GL_{n}(\mathbb{Z})$ for an appropriate $n\in \mathbb{N}$; that is, each element in the group has a unique matrix representation. An algorithm to determine this embedding was presented in Nickel. In this paper, we determine the complexity of the crux of the algorithm and the dimension of the matrices produced as well as provide a modification of the algorithm presented by Nickel.
• ### Decision and Search in Non-abelian Cramer Shoup Public Key Cryptosystem(1309.4519)

Sept. 18, 2013 cs.CR, math.GR
A method for non-abelian Cramer-Shoup cryptosystem is presented. The role of decision and search is explored, and the platform of solvable/polycyclic group is suggested. In the process we review recent progress in non-abelian cryptography and post some open problems that naturally arise from this path of research.
• ### Classification of embeddings of abelian extensions of $D_n$ into $E_{n+1}$(1305.6996)

May 30, 2013 math.RT
An abelian extension of the special orthogonal Lie algebra $D_n$ is a nonsemisimple Lie algebra $D_n \inplus V$, where $V$ is a finite-dimensional representation of $D_n$, with the understanding that $[V,V]=0$. We determine all abelian extensions of $D_n$ that may be embedded into the exceptional Lie algebra $E_{n+1}$, $n=5, 6$, and 7. We then classify these embeddings, up to inner automorphism. As an application, we also consider the restrictions of irreducible representations of $E_{n+1}$ to $D_n \inplus V$, and discuss which of these restrictions are or are not indecomposable.
• ### Public key exchange using semidirect product of (semi)groups(1304.6572)

April 24, 2013 cs.CR, math.GR
In this paper, we describe a brand new key exchange protocol based on a semidirect product of (semi)groups (more specifically, on extension of a (semi)group by automorphisms), and then focus on practical instances of this general idea. Our protocol can be based on any group, in particular on any non-commutative group. One of its special cases is the standard Diffie-Hellman protocol, which is based on a cyclic group. However, when our protocol is used with a non-commutative (semi)group, it acquires several useful features that make it compare favorably to the Diffie-Hellman protocol. Here we also suggest a particular non-commutative semigroup (of matrices) as the platform and show that security of the relevant protocol is based on a quite different assumption compared to that of the standard Diffie-Hellman protocol.
• ### Public Key Exchange Using Matrices Over Group Rings(1302.1625)

Feb. 7, 2013 cs.CR, math.GR
We offer a public key exchange protocol in the spirit of Diffie-Hellman, but we use (small) matrices over a group ring of a (small) symmetric group as the platform. This "nested structure" of the platform makes computation very efficient for legitimate parties. We discuss security of this scheme by addressing the Decision Diffie-Hellman (DDH) and Computational Diffie-Hellman (CDH) problems for our platform.
• ### Non-commutative Digital Signatures(1210.7493)

Oct. 28, 2012 cs.CR, math.GR
The objective of this work is to survey several digital signatures proposed in the last decade using non-commutative groups and rings and propose a digital signature using non-commutative groups and analyze its security.
• ### A Secret Sharing Scheme Based on Group Presentations and the Word Problem(1205.0157)

May 1, 2012 cs.CR, math.GR
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.