BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Delaram Kahrobaei

Delaram Kahrobaei appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.GRCryptography and SecurityComputational ComplexityDiscrete Mathematicsmath.ATmath.GTmath.RT

Catalog footprint

What is connected

28works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

28 published item(s)

preprint2023arXiv

Group-based Cryptography in the Quantum Era

In this expository article we present an overview of the current state-of-the-art in post-quantum group-based cryptography. We describe several families of groups that have been proposed as platforms, with special emphasis in polycyclic groups and graph groups, dealing in particular with their algorithmic properties and cryptographic applications. We then, describe some applications of combinatorial algebra in fully homomorphic encryption. In the end we discussing several open problems in this direction.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the efficiency of a general attack against the MOBS cryptosystem

All instances of the semidirect key exchange protocol, a generalisation of the famous Diffie-Hellman key exchange protocol, satisfy the so-called "telescoping equality"; in some cases, this equality has been used to construct an attack. In this report we present computational evidence suggesting that an instance of the scheme called `MOBS' is an example of a scheme where the telescoping equality has too many solutions to be a practically viable means to conduct an attack.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The root extraction problem in braid group-based cryptography

The root extraction problem in braid groups is the following: given a braid $β\in \mathcal{B}_n$ and a number $k\in \mathbb{N}$, find $α\in \mathcal{B}_n$ such that $α^k=β$. In the last decades, many cryptosystems such as authentication schemes and digital signatures based on the root extraction problem have been proposed. In this paper, we first describe these cryptosystems built around braid groups. Then we prove that, in general, these authentication schemes and digital signature are not secure by presenting for each of them a possible attack.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Algorithmic recognition of infinite cyclic extensions

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Status of Polycyclic Group-Based Cryptography: A Survey and Open Problems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Using semidirect product of (semi)groups in public key cryptography

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A family of polycyclic groups over which the uniform conjugacy problem is NP-complete

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Polynomial Time Algorithm For The Conjugacy Decision and Search Problems in Free Abelian-by-Infinite Cyclic Groups

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Length-based attacks in polycyclic groups

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Classification of embeddings of abelian extensions of $D_n$ into $E_{n+1}$

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Dimension of Matrix Representations of Finitely Generated Torsion Free Nilpotent Groups

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Public Key Exchange Using Matrices Over Group Rings

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Public key exchange using semidirect product of (semi)groups

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Secret Sharing Scheme Based on Group Presentations and the Word Problem

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems

Most common public key cryptosystems and public key exchange protocols presently in use, such as the RSA algorithm, Diffie-Hellman, and elliptic curve methods are number theory based and hence depend on the structure of abelian groups. The strength of computing machinery has made these techniques theoretically susceptible to attack and hence recently there has been an active line of research to develop cryptosystems and key exchange protocols using noncommutative cryptographic platforms. This line of investigation has been given the broad title of noncommutative algebraic cryptography. This was initiated by two public key protocols that used the braid groups, one by Ko, Lee et.al.and one by Anshel, Anshel and Goldfeld. The study of these protocols and the group theory surrounding them has had a large effect on research in infinite group theory. In this paper we survey these noncommutative group based methods and discuss several ideas in abstract infinite group theory that have arisen from them. We then present a set of open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Growth rate of an endomorphism of a group

In [B] Bowen defined the growth rate of an endomorphism of a finitely generated group and related it to the entropy of a map $f:M \mapsto M$ on a compact manifold. In this note we study the purely group theoretic aspects of the growth rate of an endomorphism of a finitely generated group. We show that it is finite and bounded by the maximum length of the image of a generator. An equivalent formulation is given that ties the growth rate of an endomorphism to an increasing chain of subgroups. We then consider the relationship between growth rate of an endomorphism on a whole group and the growth rate restricted to a subgroup or considered on a quotient.We use these results to compute the growth rates on direct and semidirect products. We then calculate the growth rate of endomorphisms on several different classes of groups including abelian and nilpotent.

0 citations0 reviewsNo code linkedOpen access