# A New Key Exchange Protocol Based on Infinite Non-Abelian Groups

Authors: Jing Zhang; Ya-Juan Yang; Yi-Peng Li
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In order to resist quantum attacks, a key exchange protocol based on infinite non-abelian groups is proposed in this paper. For the purpose, by the composition of twice the operation of a semidirect product, we construct a shared secret key which contains two hard problems of equivalent decomposition problem (EDP) and discrete logarithm problem (DLP). Then, two methods，algebra attack and brute force attack, were employed to verify the antiattack for the proposed protocol. By a sound mathematical inference, it demonstrates that the proposed protocol possesses security positively. Finally, we analyzed the computational complexity and bit complexity when the protocol being implemented on braid groups, and furthermore, the complexity data confirm the feasibility of establishing the key exchange protocol there. Thus, in any case, security or complexity, the actual use of the proposed protocol means achievable in practice.


---

## Body

## 1. Introduction

In 1993, Sidelnikov et al. proposed a new idea that infinite non-abelian group and semigroup can be used in public key cryptography [1]. The main problem of key exchange protocol on infinite non-abelian (semi) group is to hide some factors by hard problems, such as conjugacy search problem (CSP), decomposition problem (DP), subgroup membership search problem (MSP), discrete logarithm problem (DLP), and homomorphism search problem (HSP). Then since, many research studies have come up with some key protocols with a hard problem on the algebra structure. For example, in [2], the authors presented a key exchange protocol based on the DP for non-abelian groups. In [3], the authors presented a new cryptosystem with CSP on a braid group which is an infinite non-abelian group and has a good feature for cryptography. With the development of quantum algorithms and the improved factorization algorithms, we hold the opinion that only one hard problem is insufficient for the security of cryptosystem, especially only CSP is insufficient for the security of public key cryptography [4]. For enhancing security, it is a viable idea to carry out several hard problems simultaneously for a key exchange protocol.In 2006, Sakalauskas et al. employed CSP and DLP to build a key agreement protocol in the group representation level and guaranteed there that it is sufficient to use two hard problems at the same time for the entire security of key exchange protocols [5]. In 2013, Habeeb et al. proposed a new kind of key exchange protocol which was the first time that a semidirect product of groups was applied to the cryptosystem [6]. In 2020, Skuratovskii built a key exchange protocol based on the metacyclic group of Miller’s Moreno type which is a minimal non-abelian group, and it improves the efficiency of the key exchange [7].At the same time, Aleksejus et al. defined a key exchange protocol using the matrix power function (MPF) on a non-abelian groupM16, modular group of order 16, whose security is based on the NP-complete LRMPF, left-to-right MPF, and decision problem [8], so researchers believe that the protocol is not vulnerable to quantum attack. And the cryptography on the non-abelian algebra structure has been an important research field to antiquantum attack [9–11].In this paper, motivated by Habeeb’s method for constructing a protocol on non-abelian groups, we proposed a key exchange protocol with DLP and EDP by the operation of a semidirect product on the infinite non-abelian group. Since there is no effective quantum algorithm of hard problem on the non-abelian group, it is desirable to use two hard problems in the proposed key protocol at the same time. Certainly, our protocol constructed in this way is antiquantum attack. Also, the security analysis of the protocol is carried out by algebra attack and brute force attack, and as an application example, the key exchange protocol was implemented on a braid group.The remaining of this paper are organized as follows: mathematical preliminaries are introduced in Section2 that are needed in the proposed protocol. The main results of this paper and a key exchange protocol based on infinite non-abelian groups are proposed in Section 3, while the security analysis for the protocol are located in section 4. Section 5 deals with the application of the protocol being implemented on a braid group, and Section 6 presents some new research fields of cryptography as a concluding remark.


## 2. Preliminaries

Group theory is the basis of this research; as a preliminary, we give a brief introductory on groups which will be used later, and details of these results may be found in [12, 13].Definition 1 (semidirect product).
LetG,·andG′,∘ be the semigroups, AutG be the group of automorphisms of G with composition operation, and let ρ:G′⟶AutG be a homomorphism. Then, the semidirect product of GandG′ is the set of pairs(1)Γ=G×ρG′=g,h:g∈G,h∈G′,with the binary operation(2)g,h∗g′,h′=gρh′⋅g′,h∘h′.Here, g,g′∈Gandh,h′∈G′, and gρh′ denotes the image of g under the automorphism ρh′.
It is proved thatΓ,∗ is a group and an extending group of direct products. In addition, if G,⋅andG′,∘ are the infinite group, then Γ,∗ is also an infinite non-abelian group.
It is easy to see the followings: if we letG′=AutG, ρ=idG, then(3)Γ=G×G′=g,ϕ:g∈G,ϕ∈AutG,with the group operation(4)g,ϕ∗g′,ϕ′=ϕ′g⋅g′,ϕ∘ϕ′,where ϕ∘ϕ' denote a composition of automorphism and ϕ′ acting first.
Note 1
LetBijG denote a set of all the bijection on G⟶G. In our key exchange protocol, we only need that mapping ϕ is a bijection, that is ϕ∈BijG. In the set Γ=G×G′=g,ϕ:g∈G,ϕ∈BijG, we still define the binary operation as above g,ϕ∗g′,ϕ′=ϕ′g⋅g′,ϕ∘ϕ′, and define g,ϕm=g,ϕm−1g,ϕ where m∈Z+. If G is a group, then for ∀a,b∈G, let ϕ=ϕba=b−1a; obviously, ϕba is a bijection, and ϕbma=b−ma. So, g,ϕbm=b−m−1⋅gm,ϕbm.Definition 2 (Centralizer).
LetG be a group, g∈G; the set CGg=a∈G|a−1ga=g is called the centralizer of g.
In Fact,CGg is a Subgroup of Gsatisfyingag=ga for ∀a∈CGg
Decomposition problem (DP) : letG be a platform group, for ∀μ,ϑ∈G and two subgroups A,B<G, to find α∈A,β∈B satisfying μ=α⋅ϑ⋅β. It is a hard problem. Here, we proposed an equivalent decomposition problem and proved that the hardness of the two problems is similar.Definition 3 (equivalent decomposition problem (EDP)).
LetG be a platform group, for ∀μ,ϑ∈G, to find α,θn∈G satisfying μ=ρ⋅ϑn; here, n∈Z+.
Sinceμ=α⋅ϑn⇔μ=α⋅ϑ⋅ϑn−1, it is easy to see that finding αandθn is the same as finding αandθn−1. This is equivalent to find α and β, in the decomposition problem. So, the hardness of EDP is the same with the decomposition problem.Definition 4 (discrete logarithm problem).
LetG be a platform group, for ∀μ,ϑ∈G, to find n∈Z satisfying μ=ϑn.


## 3. Key Exchange Protocol

Suppose both parties of cryptography are Alice and Bob, they transmit messages by a public channel. Before describing our protocol, we first introduce Habeeb’s semidirect product method applied to the protocol construction.


### 3.1. Semidirect Product Method

Habeeb et al. proposed a new kind of key exchange protocol based on the semidirect product of group in [6]. Let G be a group with automorphism ϕ∈AutG, and element g∈G. Suppose Alice and Bob agree on group G, Alice chooses a private m∈Z+ and Bob chooses a private n∈Z+. Habeeb’s key exchange protocol is constructed as follows:Public key:gPrivate key:m,nstep 1. Alice computesg,ϕm=ϕm−1g⋯ϕ2gϕgg,ϕm, denoting A=ϕm−1g⋯ϕ2gϕgg, and sends A to Bobstep 2. Bob computesg,ϕn=ϕn−1g⋯ϕ2gϕgg,ϕn, denoting B=ϕn−1g⋯ϕ2gϕgg, and sends B to Alicestep 3. Alice computesB,x⋅A,ϕm=ϕmBA,xϕm; her key now is KA=ϕmBAstep 4. Bob computesA,y⋅B,ϕn=ϕnAB,yϕn; his key now is KB=ϕnABSinceB,x⋅A,ϕm=A,y⋅B,ϕn=g,ϕm+n, so KA=KB=K, that is, the shared secret key.For the security of the above protocol, the authors only addressed the security of a particular instantiation, which does not depend on any open hard problem. But, due to the security, it is necessary to build a key exchange protocol with open hard problems. That's the reason why we propose a key exchange protocol on non-abelian groups as follows.


### 3.2. A New Key Exchange Protocol

Now, we introduce the key exchange protocol on infinite non-abelian groups. LetG be an infinite non-abelian multiplication group, mapping ϕ=ϕba=b−1a∈BijG; here, Alice and Bob can select a different parameter b in the protocol for ∀b,a∈G. Suppose Alice and Bob are agreed on group G, element g∈G, a key exchange protocol is then be constructed as follows:Public key:gPrivate keys:m,n,k,hstep 1. Alice selects private keysm∈Z+ and k∈G satisfying kg≠gk; then, she has a mapping ϕka=k−1a:G⟶G. By computing the centralizer CGk−1, and selecting a subgroup G′ofCGk−1 such that G′≥N, here N is a positive integer, and she computes the product(5)g,ϕkm=k−m−1gm,ϕkm,and then, by lettingA=k−m−1gm, A′=k−1A=k−mgm, she sends A′andG′ to Bob.step 2. Bob selects private keysn∈Z+ and h∈G' satisfying hg≠gh; then, he has a mapping ϕha=h−1a:G⟶G and computes the product(6)g,ϕhn=h−n−1gn,ϕhn,and then, by lettingB=h−n−1gn, B'=h−1B=h−ngn, he sends B′ to Alice.step 3. Alice computes(7)B′⋅km−1,xA,ϕkm=ϕkmB′⋅km−1A,xϕkm.In fact, Alice needs only to computeϕkmB′⋅km−1A without having to calculate xϕkm since she does not know the mapping x=ϕhn, and her key is(8)KAlice=ϕkmB′⋅km−1A,=k−mh−ngnkm−1k−m−1gm,=k−mh−ngm+n.step 4. Bob computes(9)A′⋅hn−1,yB,ϕhn=ϕhnA′⋅hn−1B,yϕhn.The same as Alice, Bob need not computeyϕhn, and his key is(10)KBob=ϕhnA′⋅hn−1B,=h−nk−mgmhn−1h−n−1gn,=h−nk−mgm+n.Sinceh∈G′,G′ is a group, so h−1∈G′,thus, we have the equation(11)h−1k−1=k−1h−1⇒h−nk−m=k−mh−n.That is, for∀m,n∈Z+, h−nk−mgm+n=k−mh−ngm+n, so K=KAlice=KBob. Thus, the shared secret key will be(12)K=k−mh−ngm+n=h−nk−mgm+n.In computingCGk−1, Alice need not figure out all the elements of CGk−1; she need to only calculate the elements that satisfy the safety requirements. In addition, when Alice sends subgroup G′ to Bob, she needs just to send the generator set S of G', namely, G′=<S>.Note 2Although the proposed protocol employing the semidirect product of group which was being used by Habeeb’s in [6], ours have several differences with Habeeb’s, mainly in the following aspects:(1)
In Habeeb’s protocol using the semidirect product of group, mappingϕ is an automorphism of group. Our protocol only uses the operation rule of the semidirect product, and mapping ϕ is just a bijection on group G.(2)
Centralizer is applied in our protocol, which could guarantee the commutativity between Alice’s private keyk and Bob’s private key h, but Habeeb’s protocol has no element commutativity on the group.(3)
Obviously, our protocol contains two private keys for both parties, but Habeeb’s contains only one.(4)
The security assumptions are different. The security of our protocol is based on both hard problems: EDP and DLP, but Habeeb’s protocol does not.In our protocol, the security assumption is that it is difficult to solve EDP and DLP on the non-abelian group. Next, in order to verify the security of our protocol, we have to examine it.


## 3.1. Semidirect Product Method

Habeeb et al. proposed a new kind of key exchange protocol based on the semidirect product of group in [6]. Let G be a group with automorphism ϕ∈AutG, and element g∈G. Suppose Alice and Bob agree on group G, Alice chooses a private m∈Z+ and Bob chooses a private n∈Z+. Habeeb’s key exchange protocol is constructed as follows:Public key:gPrivate key:m,nstep 1. Alice computesg,ϕm=ϕm−1g⋯ϕ2gϕgg,ϕm, denoting A=ϕm−1g⋯ϕ2gϕgg, and sends A to Bobstep 2. Bob computesg,ϕn=ϕn−1g⋯ϕ2gϕgg,ϕn, denoting B=ϕn−1g⋯ϕ2gϕgg, and sends B to Alicestep 3. Alice computesB,x⋅A,ϕm=ϕmBA,xϕm; her key now is KA=ϕmBAstep 4. Bob computesA,y⋅B,ϕn=ϕnAB,yϕn; his key now is KB=ϕnABSinceB,x⋅A,ϕm=A,y⋅B,ϕn=g,ϕm+n, so KA=KB=K, that is, the shared secret key.For the security of the above protocol, the authors only addressed the security of a particular instantiation, which does not depend on any open hard problem. But, due to the security, it is necessary to build a key exchange protocol with open hard problems. That's the reason why we propose a key exchange protocol on non-abelian groups as follows.


## 3.2. A New Key Exchange Protocol

Now, we introduce the key exchange protocol on infinite non-abelian groups. LetG be an infinite non-abelian multiplication group, mapping ϕ=ϕba=b−1a∈BijG; here, Alice and Bob can select a different parameter b in the protocol for ∀b,a∈G. Suppose Alice and Bob are agreed on group G, element g∈G, a key exchange protocol is then be constructed as follows:Public key:gPrivate keys:m,n,k,hstep 1. Alice selects private keysm∈Z+ and k∈G satisfying kg≠gk; then, she has a mapping ϕka=k−1a:G⟶G. By computing the centralizer CGk−1, and selecting a subgroup G′ofCGk−1 such that G′≥N, here N is a positive integer, and she computes the product(5)g,ϕkm=k−m−1gm,ϕkm,and then, by lettingA=k−m−1gm, A′=k−1A=k−mgm, she sends A′andG′ to Bob.step 2. Bob selects private keysn∈Z+ and h∈G' satisfying hg≠gh; then, he has a mapping ϕha=h−1a:G⟶G and computes the product(6)g,ϕhn=h−n−1gn,ϕhn,and then, by lettingB=h−n−1gn, B'=h−1B=h−ngn, he sends B′ to Alice.step 3. Alice computes(7)B′⋅km−1,xA,ϕkm=ϕkmB′⋅km−1A,xϕkm.In fact, Alice needs only to computeϕkmB′⋅km−1A without having to calculate xϕkm since she does not know the mapping x=ϕhn, and her key is(8)KAlice=ϕkmB′⋅km−1A,=k−mh−ngnkm−1k−m−1gm,=k−mh−ngm+n.step 4. Bob computes(9)A′⋅hn−1,yB,ϕhn=ϕhnA′⋅hn−1B,yϕhn.The same as Alice, Bob need not computeyϕhn, and his key is(10)KBob=ϕhnA′⋅hn−1B,=h−nk−mgmhn−1h−n−1gn,=h−nk−mgm+n.Sinceh∈G′,G′ is a group, so h−1∈G′,thus, we have the equation(11)h−1k−1=k−1h−1⇒h−nk−m=k−mh−n.That is, for∀m,n∈Z+, h−nk−mgm+n=k−mh−ngm+n, so K=KAlice=KBob. Thus, the shared secret key will be(12)K=k−mh−ngm+n=h−nk−mgm+n.In computingCGk−1, Alice need not figure out all the elements of CGk−1; she need to only calculate the elements that satisfy the safety requirements. In addition, when Alice sends subgroup G′ to Bob, she needs just to send the generator set S of G', namely, G′=<S>.Note 2Although the proposed protocol employing the semidirect product of group which was being used by Habeeb’s in [6], ours have several differences with Habeeb’s, mainly in the following aspects:(1)
In Habeeb’s protocol using the semidirect product of group, mappingϕ is an automorphism of group. Our protocol only uses the operation rule of the semidirect product, and mapping ϕ is just a bijection on group G.(2)
Centralizer is applied in our protocol, which could guarantee the commutativity between Alice’s private keyk and Bob’s private key h, but Habeeb’s protocol has no element commutativity on the group.(3)
Obviously, our protocol contains two private keys for both parties, but Habeeb’s contains only one.(4)
The security assumptions are different. The security of our protocol is based on both hard problems: EDP and DLP, but Habeeb’s protocol does not.In our protocol, the security assumption is that it is difficult to solve EDP and DLP on the non-abelian group. Next, in order to verify the security of our protocol, we have to examine it.


## 4. Security Analysis

Security of key exchange protocol relies on both hard problems on the infinite non-abelian group: equivalent decomposition problem (EDP) and discrete logarithm problem (DLP). During the construction of the key,A′ and B′ are transferred. Since k−mandh−n can be regarded as entirety, respectively, which are unknown for attacker, it is an EDP to find k−m,h−n,gm,gn from equations A′=k−mgm and B′=h−ngn. And to find private keys m and n, the attacker must solve DLP.Alice and Bob exchange messages by a public channel; an attacker can observe the transmission of the protocol. He can get tripleg,A′=k−mgm,B′=h−ngn, and his aim is to get the shared secret key K. If he can figure out k−m,gm from A′, then K=k−mB′gm can be captured by him. Similarly, if he can get h−n,gn from B′, then the shared secret key also can be captured. Let us consider one of the both situations.


### 4.1. Algebra Attack

Due tokandm are unknown, hence k−m,gm cannot be figured out directly, and an attacker can choose an arbitrary element k¯∈G; replacing k−m with k¯, he gets(13)k¯gm=A′⇒gm=A′k¯−1.It is a DLP to computem from the above equation, so there is nopolynomial time algorithm to find m. Thus, letting gm replaced by A′k¯−1, he has(14)K¯=k¯B′gm=k¯h−ngnA′k¯−1=k¯h−ngnk−mgmk¯−1.SinceG is a non-abelian group, so K¯≠K.On the contrary, an attacker also can choose an arbitrary integerm¯∈Z+; replacing m with m¯ and gm with gm¯, he gets(15)k−mgm¯=A′⇒k−m=A′g−m¯.LetK¯=k−mB′gm¯=A′g−m¯B′gm¯=k−mgmg−m¯h−ngngm¯, since G is a non-abelian group, so K¯≠K.The algebra attack is the same forhandn, and we omit the deductions here. These attacking results show that an attacker cannot get the shared key and so the protocol is safe for algebra attack.


### 4.2. Brute Force Attack

Brute force attack means that the attacker exhausts all possibilities to find a private message. Becausek comes from group G, h comes from group G′ and G′<G; therefore，it is more effective to attack the protocol from G′. That means an attacker tries to find out all the possible h¯∈G′ for n∈Z+ satisfying h¯gn=B′.SinceG′<CGk, we have N≤G′≤CGk, and there are at least N possibilities of h¯. Assuming that the order of g is γ, then the attacker needs to compute gi for γ times i≤γ. Because G is an infinite group, CGk and γ could be large enough; this means that the complexity of the brute force attack is between Nγ and CGkγ.IfG is chosen as a proper group, such as a braid group, it is impossible to get a shared key by brute force attack.


## 4.1. Algebra Attack

Due tokandm are unknown, hence k−m,gm cannot be figured out directly, and an attacker can choose an arbitrary element k¯∈G; replacing k−m with k¯, he gets(13)k¯gm=A′⇒gm=A′k¯−1.It is a DLP to computem from the above equation, so there is nopolynomial time algorithm to find m. Thus, letting gm replaced by A′k¯−1, he has(14)K¯=k¯B′gm=k¯h−ngnA′k¯−1=k¯h−ngnk−mgmk¯−1.SinceG is a non-abelian group, so K¯≠K.On the contrary, an attacker also can choose an arbitrary integerm¯∈Z+; replacing m with m¯ and gm with gm¯, he gets(15)k−mgm¯=A′⇒k−m=A′g−m¯.LetK¯=k−mB′gm¯=A′g−m¯B′gm¯=k−mgmg−m¯h−ngngm¯, since G is a non-abelian group, so K¯≠K.The algebra attack is the same forhandn, and we omit the deductions here. These attacking results show that an attacker cannot get the shared key and so the protocol is safe for algebra attack.


## 4.2. Brute Force Attack

Brute force attack means that the attacker exhausts all possibilities to find a private message. Becausek comes from group G, h comes from group G′ and G′<G; therefore，it is more effective to attack the protocol from G′. That means an attacker tries to find out all the possible h¯∈G′ for n∈Z+ satisfying h¯gn=B′.SinceG′<CGk, we have N≤G′≤CGk, and there are at least N possibilities of h¯. Assuming that the order of g is γ, then the attacker needs to compute gi for γ times i≤γ. Because G is an infinite group, CGk and γ could be large enough; this means that the complexity of the brute force attack is between Nγ and CGkγ.IfG is chosen as a proper group, such as a braid group, it is impossible to get a shared key by brute force attack.


## 5. Application to Braid Group

In the cryptosystem, braid groups have given rise to the attention of cryptographer for several years [16–22]. Because braid groups are infinite non-abelian groups with exponential growth respect to the braid index, there exist fast algorithms to perform on group operations in a normal way of elements for the braid group, and there are many hard problems based on topological or group-theoretical open problems on the braid group. Thus, it is suitable to implement our key exchange protocol on a braid group.


### 5.1. Braid Group

Given an integern¯≥2, the n¯-braid group Bn¯ is defined by following group presentation: Bn¯=e,σ1,⋯,σn−1|σiσj=σjσiifi−j≥2;σiσjσi=σjσiσjifi−j=1, here, the integer n¯ is called the braid index, and each element of Bn¯ is called a n¯ braid.There are several kinds of group representation for braid groups, such as Burau representation, Garsides representation, and Birman–Ko–Lee representation. Our protocol is based on the Elrifai–Morton representation for the braid group [16], where each braid has a unique left-canonical form.Theorem 1 (see [16]).
For anyW∈Bn¯, there is a unique representation, called the left-canonical form:(16)W=ΔuA1A2⋯AP,u∈Z,Ai∈Σ˜n¯\e,Δ,Here Σ˜n¯ is the set of all permutation braids, Δ is the fundamental braid, and AiAi+1 is the left-weighted for 1≤i≤p−1.Then, a braidW=ΔuA1A2⋯AP could be described as a tuple u,π1,π2,⋯πp, where permutation braids Ai corresponding to the permutation πi, and p is called the canonical length of W denoted by len (W). In [16], the authors also proposed the word algorithm for the representation of word in Artin generators.


### 5.2. Key Exchange Protocol on Braid Group

In our key exchange protocol,m,n∈Z+, let the public key be g∈Bn¯ and the private key be k∈Bn¯andh∈Bn¯. By the word algorithm, the braids are represented in the left-canonical form, and the public key g is represented in advance. Centralizer CBn¯k−1 could be obtained by the algorithm in [17].


### 5.3. Complexity Analysis

According the left-canonical form of braids, two parameters, the braid index and the canonical length, need be considered. For simplicity, we assume that the braid index isn¯ and the canonical length is p for all the braids in our key exchange protocol.


#### 5.3.1. Computational Complexity

In the key exchange protocol, for Alice, there exists one braidk∈Bn¯ that needs be represented in the left-canonical form. She needs to compute k−1, k−mgm, CBnk−1 , and k−mB′km−1A, while k−m and km−1 should be computed in advance. It has been proved that we compute CBn¯k−1 in needing times Ot3ℓ2n¯6logn¯, see [17]; here, t is the number of elements in supersummit set of k−1, which is bounded by a polynomial in ℓ. Since Alice needs only to calculate some elements of CBn¯k−1, it is appropriate to assume that the complexity is Oℓ5n¯6logn¯.Lemma 1 (see [3]).
(1)
LetW be a word on σi's with a word length ℓ; then, the left-canonical form of W can be computed in time Oℓ2n¯logn¯.(2)
LetU=ΔuA1A2⋯AP and V=ΔvA1A2⋯Aq be the left-canonical form of n¯ braids, then we compute the left-canonical forms of UV in time Opqn¯logn¯.(3)
IfU=ΔuA1A2⋯AP be the left-canonical form of U∈Bn¯, then we compute the left-canonical form of U−1 in time Opn¯.By Lemma1, the computational complexity is summarized in Table 1 for Alice and Table 2 for Bob.Table 1
Time complexity for Alice.
OperationsThe number of operationsTime complexityWord algorithm ofk1 timeOℓ2n¯logn¯k−11 inverse operationOpn¯k−mgm2m multiplicationO2mp2n¯logn¯k−mB′km−1A3 multiplicationsOp2n¯logn¯CBn¯k−11 timeOℓ5n¯6logn¯Table 2
Time complexity for Bob.
OperationsNumber of operationsTime complexityWord algorithm ofh1 timeOℓ2n¯logn¯h−11 inverse operationOpn¯h−ngn2n multiplicationO2np2n¯logn¯h−nA′hn−1B3 multiplicationsOp2n¯logn¯


#### 5.3.2. Bit Complexity

While implementing our key exchange protocol algorithm, for Alice, a subgroupG′ of CBn¯k−1, A, km−1, mapping ϕkm, public key g, and shared secret key K needs be stored. For ∀a∈Bn¯, generators of CBn¯a are less than n¯n¯−1/2 (see [18]). If we let G′=CBn¯k−1, it is necessary to store n¯n¯−1/2 braids which is the worst case for storage space. For mapping ϕkm, it is enough to store the braid k−m.A braid withp canonical factors can be represented by a bit string of size pn¯logn¯, for braids a,b∈Bn¯, lenab≤lena+lenb (see [3]). In the worst case, the bit complexity is summarized in Table 3 for Alice and Table 4 for Bob.Table 3
Bit complexity for Alice.
BraidsBit complexityGenerators of subgroupG′pn¯2n¯−12logn¯km−1m−1pn¯logn¯Am−1mpn¯logn¯ϕkmmpn¯logn¯gpn¯logn¯K2m+npn¯logn¯Table 4
Bit complexity for Bob.
BraidsBit complexityhn−1n−1pn¯logn¯Bn−1npn¯logn¯ϕhnnpn¯logn¯gpn¯logn¯K2m+npn¯logn¯Therefore，the bit complexity is less thann¯n¯−1/2+m2+3m+2nlogn¯ for Alice and less than n2+3n+2mlogn¯ for Bob.


## 5.1. Braid Group

Given an integern¯≥2, the n¯-braid group Bn¯ is defined by following group presentation: Bn¯=e,σ1,⋯,σn−1|σiσj=σjσiifi−j≥2;σiσjσi=σjσiσjifi−j=1, here, the integer n¯ is called the braid index, and each element of Bn¯ is called a n¯ braid.There are several kinds of group representation for braid groups, such as Burau representation, Garsides representation, and Birman–Ko–Lee representation. Our protocol is based on the Elrifai–Morton representation for the braid group [16], where each braid has a unique left-canonical form.Theorem 1 (see [16]).
For anyW∈Bn¯, there is a unique representation, called the left-canonical form:(16)W=ΔuA1A2⋯AP,u∈Z,Ai∈Σ˜n¯\e,Δ,Here Σ˜n¯ is the set of all permutation braids, Δ is the fundamental braid, and AiAi+1 is the left-weighted for 1≤i≤p−1.Then, a braidW=ΔuA1A2⋯AP could be described as a tuple u,π1,π2,⋯πp, where permutation braids Ai corresponding to the permutation πi, and p is called the canonical length of W denoted by len (W). In [16], the authors also proposed the word algorithm for the representation of word in Artin generators.


## 5.2. Key Exchange Protocol on Braid Group

In our key exchange protocol,m,n∈Z+, let the public key be g∈Bn¯ and the private key be k∈Bn¯andh∈Bn¯. By the word algorithm, the braids are represented in the left-canonical form, and the public key g is represented in advance. Centralizer CBn¯k−1 could be obtained by the algorithm in [17].


## 5.3. Complexity Analysis

According the left-canonical form of braids, two parameters, the braid index and the canonical length, need be considered. For simplicity, we assume that the braid index isn¯ and the canonical length is p for all the braids in our key exchange protocol.


### 5.3.1. Computational Complexity

In the key exchange protocol, for Alice, there exists one braidk∈Bn¯ that needs be represented in the left-canonical form. She needs to compute k−1, k−mgm, CBnk−1 , and k−mB′km−1A, while k−m and km−1 should be computed in advance. It has been proved that we compute CBn¯k−1 in needing times Ot3ℓ2n¯6logn¯, see [17]; here, t is the number of elements in supersummit set of k−1, which is bounded by a polynomial in ℓ. Since Alice needs only to calculate some elements of CBn¯k−1, it is appropriate to assume that the complexity is Oℓ5n¯6logn¯.Lemma 1 (see [3]).
(1)
LetW be a word on σi's with a word length ℓ; then, the left-canonical form of W can be computed in time Oℓ2n¯logn¯.(2)
LetU=ΔuA1A2⋯AP and V=ΔvA1A2⋯Aq be the left-canonical form of n¯ braids, then we compute the left-canonical forms of UV in time Opqn¯logn¯.(3)
IfU=ΔuA1A2⋯AP be the left-canonical form of U∈Bn¯, then we compute the left-canonical form of U−1 in time Opn¯.By Lemma1, the computational complexity is summarized in Table 1 for Alice and Table 2 for Bob.Table 1
Time complexity for Alice.
OperationsThe number of operationsTime complexityWord algorithm ofk1 timeOℓ2n¯logn¯k−11 inverse operationOpn¯k−mgm2m multiplicationO2mp2n¯logn¯k−mB′km−1A3 multiplicationsOp2n¯logn¯CBn¯k−11 timeOℓ5n¯6logn¯Table 2
Time complexity for Bob.
OperationsNumber of operationsTime complexityWord algorithm ofh1 timeOℓ2n¯logn¯h−11 inverse operationOpn¯h−ngn2n multiplicationO2np2n¯logn¯h−nA′hn−1B3 multiplicationsOp2n¯logn¯


### 5.3.2. Bit Complexity

While implementing our key exchange protocol algorithm, for Alice, a subgroupG′ of CBn¯k−1, A, km−1, mapping ϕkm, public key g, and shared secret key K needs be stored. For ∀a∈Bn¯, generators of CBn¯a are less than n¯n¯−1/2 (see [18]). If we let G′=CBn¯k−1, it is necessary to store n¯n¯−1/2 braids which is the worst case for storage space. For mapping ϕkm, it is enough to store the braid k−m.A braid withp canonical factors can be represented by a bit string of size pn¯logn¯, for braids a,b∈Bn¯, lenab≤lena+lenb (see [3]). In the worst case, the bit complexity is summarized in Table 3 for Alice and Table 4 for Bob.Table 3
Bit complexity for Alice.
BraidsBit complexityGenerators of subgroupG′pn¯2n¯−12logn¯km−1m−1pn¯logn¯Am−1mpn¯logn¯ϕkmmpn¯logn¯gpn¯logn¯K2m+npn¯logn¯Table 4
Bit complexity for Bob.
BraidsBit complexityhn−1n−1pn¯logn¯Bn−1npn¯logn¯ϕhnnpn¯logn¯gpn¯logn¯K2m+npn¯logn¯Therefore，the bit complexity is less thann¯n¯−1/2+m2+3m+2nlogn¯ for Alice and less than n2+3n+2mlogn¯ for Bob.


## 5.3.1. Computational Complexity

In the key exchange protocol, for Alice, there exists one braidk∈Bn¯ that needs be represented in the left-canonical form. She needs to compute k−1, k−mgm, CBnk−1 , and k−mB′km−1A, while k−m and km−1 should be computed in advance. It has been proved that we compute CBn¯k−1 in needing times Ot3ℓ2n¯6logn¯, see [17]; here, t is the number of elements in supersummit set of k−1, which is bounded by a polynomial in ℓ. Since Alice needs only to calculate some elements of CBn¯k−1, it is appropriate to assume that the complexity is Oℓ5n¯6logn¯.Lemma 1 (see [3]).
(1)
LetW be a word on σi's with a word length ℓ; then, the left-canonical form of W can be computed in time Oℓ2n¯logn¯.(2)
LetU=ΔuA1A2⋯AP and V=ΔvA1A2⋯Aq be the left-canonical form of n¯ braids, then we compute the left-canonical forms of UV in time Opqn¯logn¯.(3)
IfU=ΔuA1A2⋯AP be the left-canonical form of U∈Bn¯, then we compute the left-canonical form of U−1 in time Opn¯.By Lemma1, the computational complexity is summarized in Table 1 for Alice and Table 2 for Bob.Table 1
Time complexity for Alice.
OperationsThe number of operationsTime complexityWord algorithm ofk1 timeOℓ2n¯logn¯k−11 inverse operationOpn¯k−mgm2m multiplicationO2mp2n¯logn¯k−mB′km−1A3 multiplicationsOp2n¯logn¯CBn¯k−11 timeOℓ5n¯6logn¯Table 2
Time complexity for Bob.
OperationsNumber of operationsTime complexityWord algorithm ofh1 timeOℓ2n¯logn¯h−11 inverse operationOpn¯h−ngn2n multiplicationO2np2n¯logn¯h−nA′hn−1B3 multiplicationsOp2n¯logn¯


## 5.3.2. Bit Complexity

While implementing our key exchange protocol algorithm, for Alice, a subgroupG′ of CBn¯k−1, A, km−1, mapping ϕkm, public key g, and shared secret key K needs be stored. For ∀a∈Bn¯, generators of CBn¯a are less than n¯n¯−1/2 (see [18]). If we let G′=CBn¯k−1, it is necessary to store n¯n¯−1/2 braids which is the worst case for storage space. For mapping ϕkm, it is enough to store the braid k−m.A braid withp canonical factors can be represented by a bit string of size pn¯logn¯, for braids a,b∈Bn¯, lenab≤lena+lenb (see [3]). In the worst case, the bit complexity is summarized in Table 3 for Alice and Table 4 for Bob.Table 3
Bit complexity for Alice.
BraidsBit complexityGenerators of subgroupG′pn¯2n¯−12logn¯km−1m−1pn¯logn¯Am−1mpn¯logn¯ϕkmmpn¯logn¯gpn¯logn¯K2m+npn¯logn¯Table 4
Bit complexity for Bob.
BraidsBit complexityhn−1n−1pn¯logn¯Bn−1npn¯logn¯ϕhnnpn¯logn¯gpn¯logn¯K2m+npn¯logn¯Therefore，the bit complexity is less thann¯n¯−1/2+m2+3m+2nlogn¯ for Alice and less than n2+3n+2mlogn¯ for Bob.


## 6. Concluding Remarks

Nowadays, the main trend in cryptography theory locates still on constructing the cryptosystem based on a hard mathematical problem. However, quantum computer is no longer a dream in the near future; by then, many cryptosystems may be crumbled. So, it is urgent to design the cryptosystem against the quantum computing attacks. In our opinion, as a platform, a non-abelian algebra structure may be a good option.In addition, developed in recent decades, bionic algorithms, such as evolutionary algorithm, neural network algorithm, genetic algorithm, meme algorithm, and DNA algorithm, have become an important way to transform traditional cryptography. In particular, the key evolution algorithm and meme algorithm have become the focus of research in recent years. The progress of evolutionary algorithms and the related problems in recent years refer to [23, 24], and the state for memetic algorithms can refer to [25–27]. In terms of methodology, it can be predicted that the bionic algorithms could be a promising research area of cryptography theory in the future. [14, 15].



---

*Source: 7942353-2022-03-24.xml*