# Novel Noncommutative Cryptography Scheme Using Extra Special Group

Authors: Gautam Kumar; Hemraj Saini
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Noncommutative cryptography (NCC) is truly a fascinating area with great hope of advancing performance and security for high end applications. It provides a high level of safety measures. The basis of this group is established on the hidden subgroup or subfield problem (HSP). The major focus in this manuscript is to establish the cryptographic schemes on the extra special group (ESG). ESG is showing one of the most appropriate noncommutative platforms for the solution of an open problem. The working principle is based on the random polynomials chosen by the communicating parties to secure key exchange, encryption-decryption, and authentication schemes. This group supports Heisenberg, dihedral order, and quaternion group. Further, this is enhanced from the general group elements to equivalent ring elements, known by the monomials generations for the cryptographic schemes. In this regard, special or peculiar matrices show the potential advantages. The projected approach is exclusively based on the typical sparse matrices, and an analysis report is presented fulfilling the central cryptographic requirements. The order of this group is more challenging to assail like length based, automorphism, and brute-force attacks.


---

## Body

## 1. Introduction

Cryptography is a discipline of computer science, where algorithms and security practices are acting as a central tool. This is traditionally based on the mathematical foundation. The practical applications contain the assurance of legitimacy, protection of information from confessing, and protected message communication systems for essential requirements. To enforce security, the cryptographic schemes are concerning the vital role responsiveness in the field of security for numerous relevant applications all over the world. The absolute measure of cryptographic approaches shows the full-fledged appropriateness. But the serenities fondness with an assortment of more arbitrariness and impulsiveness with statistical responses is the motivational issue.Public key cryptography (PKC) thought was first proposed by Diffie and Hellman [1]. Since then there are varieties of PKC algorithms that have been proposed, where Elliptic Curve Cryptography (ECC) [2, 3] in all of them has attracted the most attention in the cryptographic area. ECC has played a crucial role that made a big impact on the lower computational and communicational cost. Today ECC considered being tenable, but researchers are looking for alternative approaches for future security by not putting all the security protocols in one group only, that is, commutative group. On behalf of the open opinion, a brief analysis is presented below.Peter’s [4], in 1994, proposed a competent quantum algorithm for solving the discrete logarithm problem (DLP) and integer factorization problem (IFP). A Kitaev framework in 1996 [5] considered as a special case on DLP, called hidden subgroup or subfield problem (HSP). Stinson sensibly observed, in 2002, the most eternal PKCs belonging to a commutative or abelian group only, whose intention is susceptible in the forthcoming future. According to the same cryptographers Goldreich and Lee advised that we do not put all cryptographic protocols in one group. The reason was clear to introduce a new field of cryptography; this was only the opening of noncommutative cryptography [6]. Then afterwards for key exchange, encryption-decryption (ED) and authentication schemes for cryptographic protocols on noncommutative cryptography were developed for various problems. Those were analogous protocols like the commutative cases. The elliptic curve over the HSP [7] comprehensively resolved on DLP, as recognized by ECC-DLP. The random HSP over noncommutative groups are well organized on quantum algorithms, which are well responsive. Further, the evidences are recommending that HSP over noncommutative groups are much harder [8].The earlier structure of noncommutative cryptography was based on the braid based cryptography for the generalizations of the protocols. Afterward several other structures like Thompsons, polycyclic, Grigorchuk, or matrix groups/ring elements were proposed. The cryptographic primitives, methods, and systems of the noncommutative cryptography are based on algebraic structures of group, ring, and semiring elements. But in all of them matrix group of elements has shown the prospective advantages. In contrast, implementation in recent applications (protocols) using public key cryptographic approaches on Diffie-Hellman, RSA, and ECC is based on number theory. They are solving the various problems like session key establishments, encryption-decryption, and authentication schemes.The basis of noncommutative cryptography is based on∗ (contains reflection and/or rotation) operation on the noncommutative group G of (G,∗) that consists of group, ring, semiring, or some algebraic structural elements, in which two group elements a and b of G such that a∗b≠b∗a are known by noncommutative or nonabelian group. The group of these problems is broadly encompassed from mathematics and physics.


### 1.1. Background

The generation of noncommutative cryptographic approach has a solid backbone for security enhancements and performances. A course of numerous attempts has been made available for the same. A brief analysis is described below.(i)
Wagner and Magyarik in 1985 [9] proposed undecidable word problems on semigroup elements for public key cryptography (PKC). But Birget et al. [10] pointed out that it is not based on word problem and proposed a new system on finitely generated groups with a hard problem.(ii)
On braid based cryptography, there is a compact key established protocol proposed by Anshel et al. [11] in 1999. The basis was difficulty in solving equations over algebraic structures. In their research paper, they also recommended that braid groups may subsist to be a good alternate platform for PKC.(iii)
Afterwards, Ko et al. in 2000 [12] anticipated a new PKC by using braid groups. The Conjugacy Search Problem (CSP) is the intractability security foundation, such as effective canonical lengths and braid index when they are chosen suitably. Further, the area under consideration met with immediate successes by Dehornoy in 2004 [13], Anshel et al. in 2003 [14], Anshel et al. in 2006 [15], and Cha et al. in 2001 [16]. Despite the fact, 2001 to 2003, recurring cryptanalytic sensation, Ko et al. in 2002 [17] and Cheon and Jun in 2003 [18] diminished the initial buoyancy on the noteworthy theme, in Hughes and Tannenbaum in 2000 [19]. Many numbers of authors even proclaimed the impetuous death of the braid based PKC, Bohli et al. in 2006 [20] and Dehornoy in 2004 [21]. Dehornoy’s paper conducted a survey on the state of the subject with significant research, but still being desirable for accomplishing a definite final conclusion on the cryptographic prospective of braid groups.(iv)
In 2001, Paeng et al. [22] also published a new PKC built on finite nonabelian groups. Their method is based on the DLP in the inner automorphism group passing through the conjugation accomplishment. These were further improved, named MOR systems.(v)
In the meantime, one-way function and trapdoors generated on the finite fields were remarkable in group theory by Magliveras et al. in 2002 [23]. Later on, in 2002 Vasco et al. [24] confirmed an appropriate generality on factorization and a uniform description of several cryptographic primitives on convincing homomorphic cryptosystem; those were constructed in the first time for nonabelian groups. Meanwhile, Magliveras et al. in [25] proposed a new approach to designing public key cryptosystems using one-way functions and trapdoors in finite groups. Grigoriev and Ponomarenko [26] and Grigoriev and Ponomarenko [27], consequently, extended the difficulty of membership problems on integer matrices for a finitely generated random group of elements.(vi)
The arithmetic key exchange is enlightened by Eick and Kahrobaei 2004 [28] and an innovative cryptosystem on polycyclic groups is proposed by them. The structures of polycyclic groups are a complex of their own cyclic group. The algorithmic theory and investigation properties are more difficult which seems to have a more open proposal. The progression tenure is a succession of subgroups of a group G=G1⊳G2⊳⋯⊳Gn+1={1}. For each term of the series, succession not only is in the entire group but also is not contained in the former term. A group G is called polycyclic series with cyclic aspects; that is, Gi/Gi+1 is recurring for i=1,…,n.(vii)
Shpilrain and Ushakov in 2005 [29] recommended that Thompson’s group is a good proposal for building PKCs. The assumption under the decomposing problem is intractable, ancillary to the Conjugacy Search Problem, described over R.(viii)
In 2005, Mahalanobis [30] did not discriminate the D-H key exchange protocol from a cyclic group to a finitely presented nonabelian nilpotent group of class 2. The nilpotent group is a normal series to each quotient Hi/Hi+1 lying in the center of G/Hi+1 and supposed to be a central succession. A class of nilpotent group is the shortest series length with its shortest nilpotency degree. Engendered nilpotent finite groups are polycyclic groups and moreover have a central series with cyclic factors. Also in 2006 Dehornoy proposed an authentication scheme based on the left self-distributive (LD) systems. This idea was further developed by introducing the concept of the one-way LD system structured by Wang et al. in 2010 [31]. The algebraic association (A,∗) is called left self-distributive for all elements a,b,c∈A,   a∗b∗c=a∗b(a∗c).(ix)
To extract from a givena∗b and b, this system is said to be one way, if it is intractable. LD system, in general, is much different from groups or semigroups or semirings. Even the regarding facts are not associative, so solitarily describing a nontrivial LD system over any noncommutative group G via the mapping a∗b≜aba¯.(x)
Moreover, if the Conjugacy Search Problem (CSP) overG is intractable, the derivative of LD system is treated as being one way.(xi)
In 2007, Cao et al. [32] proposed a method to use polynomials over noncommutative rings or semigroups to build cryptographic scheme. This method is referred to as the Z-modular method. Further, the protocol application was based on nonabelian dihedral order 6 by Kubo in 2008 [33] which is the initial order for this group and construction is based on three-dimensional revolutions.(xii)
In 2008, Reddy et al. [34], Z-modular method was used to build signature schemes over noncommutative groups and division rings.(xiii)
The cryptographic protocol implementation was constructed on four-dimensional considerations by D. N. Moldovyan and N. A. Moldovyan in 2010 [35]. The perspectives were the generalizations for security enhancement on the basis of noncommutative groups.(xiv)
In 2014, Myasnikov and Ushakov [36] cryptanalyzed the authentication scheme proposed by Shpilrain and public key encryption to use the hardness of the Conjugacy Search Problem in noncommutative monoids. A heuristic algorithm, was devised by those to solve these problems and declared that these protocols are anxious.(xv)
Svozil in 2014 [37] proposed the metaphorical recognized hidden variable on noncontextual indecisiveness that cannot be comprehended by quantum systems. The cryptanalytic attacks are not accompanied and aligned by quasi configurations, and the theorems do not subsist assembled proofs reclining over the same.


### 1.2. Motivation and Our Contribution

The issues related to the ring structure of the group elements are one of the most motivational concerns. A typical semiring structure, such as sparse matrices, shows the potential advantages towards a possible way to avoid the various attacks. The initial order for general and monomials [original parameters are hidden, and monomials structures provably equivalent consideration takes part in computation process] structure on polynomialZ-modular noncommutative cryptography is the foundation.Our contribution is in multidisciplinary scenario on extra special group on the cryptographic protocol regarding the key exchange, encryption-decryption, and authentication in four-dimensional perspective. The key idea is based on a special case of prime order with more resistance to attacks, and proposed approach works on the bigger range of probabilistic theories.


### 1.3. Manuscript Organization

The content of manuscript is organized into its subsequent sections. The next section presents cryptographic preliminaries for modular polynomial assumptions on general scalar multiplication and monomials like scalar multiplication on group, ring, and semiring elements. Section3 presents the fundamental of the proposed work on the extra special group and its elementary analysis is elaborated. Sections 4 and 5 are our core parts, where our considerations are perfectly set aside on the general protocol schemes for the session key establishment, encryption-decryption, and authentication schemes; further similar schemes on monomials are presented on a combinational congruence on group, ring, or semiring elements. In Section 6, a brief idea is presented to achieve the bigger search space for the length based attack, which gives its security guarantees. Finally, the work concludes, along with references.


## 1.1. Background

The generation of noncommutative cryptographic approach has a solid backbone for security enhancements and performances. A course of numerous attempts has been made available for the same. A brief analysis is described below.(i)
Wagner and Magyarik in 1985 [9] proposed undecidable word problems on semigroup elements for public key cryptography (PKC). But Birget et al. [10] pointed out that it is not based on word problem and proposed a new system on finitely generated groups with a hard problem.(ii)
On braid based cryptography, there is a compact key established protocol proposed by Anshel et al. [11] in 1999. The basis was difficulty in solving equations over algebraic structures. In their research paper, they also recommended that braid groups may subsist to be a good alternate platform for PKC.(iii)
Afterwards, Ko et al. in 2000 [12] anticipated a new PKC by using braid groups. The Conjugacy Search Problem (CSP) is the intractability security foundation, such as effective canonical lengths and braid index when they are chosen suitably. Further, the area under consideration met with immediate successes by Dehornoy in 2004 [13], Anshel et al. in 2003 [14], Anshel et al. in 2006 [15], and Cha et al. in 2001 [16]. Despite the fact, 2001 to 2003, recurring cryptanalytic sensation, Ko et al. in 2002 [17] and Cheon and Jun in 2003 [18] diminished the initial buoyancy on the noteworthy theme, in Hughes and Tannenbaum in 2000 [19]. Many numbers of authors even proclaimed the impetuous death of the braid based PKC, Bohli et al. in 2006 [20] and Dehornoy in 2004 [21]. Dehornoy’s paper conducted a survey on the state of the subject with significant research, but still being desirable for accomplishing a definite final conclusion on the cryptographic prospective of braid groups.(iv)
In 2001, Paeng et al. [22] also published a new PKC built on finite nonabelian groups. Their method is based on the DLP in the inner automorphism group passing through the conjugation accomplishment. These were further improved, named MOR systems.(v)
In the meantime, one-way function and trapdoors generated on the finite fields were remarkable in group theory by Magliveras et al. in 2002 [23]. Later on, in 2002 Vasco et al. [24] confirmed an appropriate generality on factorization and a uniform description of several cryptographic primitives on convincing homomorphic cryptosystem; those were constructed in the first time for nonabelian groups. Meanwhile, Magliveras et al. in [25] proposed a new approach to designing public key cryptosystems using one-way functions and trapdoors in finite groups. Grigoriev and Ponomarenko [26] and Grigoriev and Ponomarenko [27], consequently, extended the difficulty of membership problems on integer matrices for a finitely generated random group of elements.(vi)
The arithmetic key exchange is enlightened by Eick and Kahrobaei 2004 [28] and an innovative cryptosystem on polycyclic groups is proposed by them. The structures of polycyclic groups are a complex of their own cyclic group. The algorithmic theory and investigation properties are more difficult which seems to have a more open proposal. The progression tenure is a succession of subgroups of a group G=G1⊳G2⊳⋯⊳Gn+1={1}. For each term of the series, succession not only is in the entire group but also is not contained in the former term. A group G is called polycyclic series with cyclic aspects; that is, Gi/Gi+1 is recurring for i=1,…,n.(vii)
Shpilrain and Ushakov in 2005 [29] recommended that Thompson’s group is a good proposal for building PKCs. The assumption under the decomposing problem is intractable, ancillary to the Conjugacy Search Problem, described over R.(viii)
In 2005, Mahalanobis [30] did not discriminate the D-H key exchange protocol from a cyclic group to a finitely presented nonabelian nilpotent group of class 2. The nilpotent group is a normal series to each quotient Hi/Hi+1 lying in the center of G/Hi+1 and supposed to be a central succession. A class of nilpotent group is the shortest series length with its shortest nilpotency degree. Engendered nilpotent finite groups are polycyclic groups and moreover have a central series with cyclic factors. Also in 2006 Dehornoy proposed an authentication scheme based on the left self-distributive (LD) systems. This idea was further developed by introducing the concept of the one-way LD system structured by Wang et al. in 2010 [31]. The algebraic association (A,∗) is called left self-distributive for all elements a,b,c∈A,   a∗b∗c=a∗b(a∗c).(ix)
To extract from a givena∗b and b, this system is said to be one way, if it is intractable. LD system, in general, is much different from groups or semigroups or semirings. Even the regarding facts are not associative, so solitarily describing a nontrivial LD system over any noncommutative group G via the mapping a∗b≜aba¯.(x)
Moreover, if the Conjugacy Search Problem (CSP) overG is intractable, the derivative of LD system is treated as being one way.(xi)
In 2007, Cao et al. [32] proposed a method to use polynomials over noncommutative rings or semigroups to build cryptographic scheme. This method is referred to as the Z-modular method. Further, the protocol application was based on nonabelian dihedral order 6 by Kubo in 2008 [33] which is the initial order for this group and construction is based on three-dimensional revolutions.(xii)
In 2008, Reddy et al. [34], Z-modular method was used to build signature schemes over noncommutative groups and division rings.(xiii)
The cryptographic protocol implementation was constructed on four-dimensional considerations by D. N. Moldovyan and N. A. Moldovyan in 2010 [35]. The perspectives were the generalizations for security enhancement on the basis of noncommutative groups.(xiv)
In 2014, Myasnikov and Ushakov [36] cryptanalyzed the authentication scheme proposed by Shpilrain and public key encryption to use the hardness of the Conjugacy Search Problem in noncommutative monoids. A heuristic algorithm, was devised by those to solve these problems and declared that these protocols are anxious.(xv)
Svozil in 2014 [37] proposed the metaphorical recognized hidden variable on noncontextual indecisiveness that cannot be comprehended by quantum systems. The cryptanalytic attacks are not accompanied and aligned by quasi configurations, and the theorems do not subsist assembled proofs reclining over the same.


## 1.2. Motivation and Our Contribution

The issues related to the ring structure of the group elements are one of the most motivational concerns. A typical semiring structure, such as sparse matrices, shows the potential advantages towards a possible way to avoid the various attacks. The initial order for general and monomials [original parameters are hidden, and monomials structures provably equivalent consideration takes part in computation process] structure on polynomialZ-modular noncommutative cryptography is the foundation.Our contribution is in multidisciplinary scenario on extra special group on the cryptographic protocol regarding the key exchange, encryption-decryption, and authentication in four-dimensional perspective. The key idea is based on a special case of prime order with more resistance to attacks, and proposed approach works on the bigger range of probabilistic theories.


## 1.3. Manuscript Organization

The content of manuscript is organized into its subsequent sections. The next section presents cryptographic preliminaries for modular polynomial assumptions on general scalar multiplication and monomials like scalar multiplication on group, ring, and semiring elements. Section3 presents the fundamental of the proposed work on the extra special group and its elementary analysis is elaborated. Sections 4 and 5 are our core parts, where our considerations are perfectly set aside on the general protocol schemes for the session key establishment, encryption-decryption, and authentication schemes; further similar schemes on monomials are presented on a combinational congruence on group, ring, or semiring elements. In Section 6, a brief idea is presented to achieve the bigger search space for the length based attack, which gives its security guarantees. Finally, the work concludes, along with references.


## 2. Preliminaries

### 2.1.Z-Modular Assumptions on Noncommutative Cryptography

The scalar multiplication is the basis for all cryptographic computations. The major goal of scalar multiplication is to generate the discrete logarithmic value. A new public key cryptography on polynomials scalar multiplication over the noncommutative ringR is proposed by Cao et al. in 2007 [32]. The developed scheme is based on modulo prime integers, named Z-modular method. The derived Z-modular structure on ring is Z(r), and this structure applies to positive Z+[r] and/or negative Z-[r] on noncommutative ring R elements, where r∈R is undetermined. Also, group and semiring are comprehensively applicable on Z-modular assumptions.


#### 2.1.1. Noncommutative Rings onZ-Modular Method

The integral coefficient polynomial on additive noncommutative characterization is defined on ring(R,+,0) and for multiplicative noncommutative (R,·,1); the scalar multiplication over R is well defined for k∈Z+ and r∈R:(1)kr≅r+⋯+r︸ktimes.Further, for k∈Z-, (2)kr≅-r+⋯+-r︸-ktimes.Finally, if it is to be defined on scalar k=0, it is likely to be kr=0.Proposition 1.
In general, scalar multiplication on noncommutative property followsar·bs≠bs·ar, when r≠s. Recall a polynomial with positive integral coefficient fx=a0+a1x+⋯+anxn∈Z+, for all x. To assign the component x as an element r∈R, then attain a precise element in ring R as(3)fr=∑i=0nairi=a0·1+a1·x+⋯+an·xn.In addition, suppose r to be undetermined; then polynomial over f(r) is univariable polynomial lying on R. The univariable polynomial over R as a whole set is denoted as Z+[r], and it is defined as follows for the respective functions on two different ring elements:(4)fr=∑i=0nairi∈Z+r,hr=∑j=0mbjrj∈Z+r.Again, if n≥m, then(5)∑i=0nairi+∑j=0mbjrj=∑i=0mai+biri+∑i=m+1nairiand according to the property of distributive law it generalizes the above equation as(6)∑i=0nairi+∑j=0mbjrj=∑i=0n+mpirj,where,(7)pi=∑j=0iajbi-jri=∑j+k=iajbk.Theorem 2.
f r · h r = h r · f r,   ⍱fr∈Z+[r] and ⍱hr∈Z+[r], where ⍱ signify for all elements.Proof.
Here ringr is a subset of ring R applying to polynomial functions of fr and hr, for all positive integers of Z+[r]. A ring is a set of elements with two binary operations of addition and multiplication satisfying the following case properties on commutative law, associative law, identity, inverse, and closure. In addition to the same some more properties are also satisfying for all ring elements as follows:(i)
Closure under multiplication: ifa and b belong to ring element, then ab is also in ring.(ii)
Associative law of multiplication:a(bc)=(ab)c for all a,b,c.(iii)
Distributive laws:a(b+c)=ab+ac or (a+b)c=ac+bc for all a,b,c.(iv)
Commutative multiplication:ab=ba for a,b.(v)
Multiplicative identity:a·1=1·a=a for all a.(vi)
No zero divisors: for alla and b in R and ab=0, then, either a=0 or b=0 and this does not follow on dividing by zero.Therefore, this theorem proofs itself on the above properties of (i), (iii), and (iv).


### 2.2. Two Well-Known Cryptographic Assumptions

The assumptions of security strength are due to the difficulty of the following two problems:(i)
Conjugacy Decisional Problem (CDP). It is, on the given two group elements a and b, to determine a random x to produce the value of other group elements, such that b=ax or to produce the same using the Conjugacy multiplicative inverse as b=x-1ax.(ii)
Conjugacy Search Problem (CSP). It is, for the two group elements of a and b in a group G, to find whether there exists x in G, such that b=ax or Conjugacy multiplicative inverse b=x-1ax.If no algorithm exists to solve the CSP, by applying x on one group of elements to determine the other group of elements, that is, a→bx, then this is considered to be a one-way function. In the contemporary computation, both problems on general noncommutative group G are too complicated enough to determine the assumptions on cryptographic primitives. The CSP assumptions are difficult enough to solve this problem on probabilistic polynomial time, whereas CDP assumptions are a unique representation for any group, ring, or semiring elements for cryptographic use. The CDP transition on all these assumptions finishing efficiently over each other is one of the major advantages.


### 2.3. Using Monomials inZ-Modular Method

The polynomials used inZ-modular method are constrained to be monomials; that is, if the original information of group elements is hidden with its equivalents ring or semiring elements, such participation in computation is viewed as a special case. Under these considerations new creations of public key encryption schemes from Conjugacy Search Problems are proposed.


#### 2.3.1. Conjugacy Search Problem

Let(G,·,1) be a noncommutative monomial for an element a∈G, the other group element being b∈G, such that a·b=b·a; then it assumed that group a is invertible, and call b an inverse of a. Not all elements in G are invertible. If the inverse of a exists, it is unique and denoted by a-1. In monomials, the positive power of a group element for n integer is described as follows: an=a+⋯+a︸ntimes for n>1. If b is the inverse of a, one can also define the negative power of a by setting a-1=b+⋯+b︸ntimesfor n>1. The Conjugacy Search Problem can be extended to monomials G, for ∀a∈G and ∀x∈G-1, xax-1 is a conjugate to a, and call x as conjugator of the pair (a,xax-1).Definition 3 (Conjugacy Search Problem (CSP)).
LetG be a noncommutative monomial; the two elements a,b∈G so that b=xax-1 for some unknown element x∈G-1, and the objective of the CSP in G is to find x∈G-1 such that b=x′ax′-1.Definition 4 (left self-distributive system).
Suppose thatS is a nonempty set, F:S×S→S is a well-defined function, and let one denote F(a,b) by Fa(b). If the rewritten formula FrFsp=FFrsFrp,∀p,r,s∈S holds then call F·(·) as a left self-distributive system (LD).Theorem 5.
LetG be noncommutative monomial, the function F on conjugate follows as F:G-1×G→G,a,b↦aba-1 and is known by LD system, also abbreviated as Conj-LD.Proof.
According to Definition4, the term LD is an analogical observation from Fr(s) as a binary operation in r∗s; then this is observed as r∗(s∗p)=(r∗s)∗(r∗p), where “∗” is left distributive with respect to itself. The proof of these observations is following from left-hand side to right-hand side as follows: FrFsp=Frs∗p=r∗s∗p=r∗s∗r∗p=Frs∗Frp=FFrsFrp. Here, it is satisfying the function F on FrFsp=FFrsFrp as an LD system. Thus, Theorem 5 proof is based on these observations.Proposition 6.
LetF be a Conj-LD system defined over a noncommutative monomial G; then for the given a∈G-1 and b,c∈G, the following proposals are well-defined, according to [38]:(i)
Faa=a.(ii)
Fab=c⇔Fa-1c=b.(iii)
Fabc=FabFac.Proof of (i).
Sinceaaa-1=a, so Faa=a.Proof of (ii).
F a b = c → y i e l d s a b a - 1 = c → y i e l d s a - 1 c a = b → y i e l d s F a - 1 c = b.Proof of (iii).
F a b c = a b c a - 1 = a b a - 1 a c a - 1 = F a b F a c.


### 2.4. Symmetry and Generalization Assumptions over Noncommutative Groups

To explain the symmetries, the generalizations on the noncommutative cryptography are the following problems on groupG:(i)
Symmetrical Decomposition Problem (SDP). Given (a,b)∈G and m,n∈Z, find x∈G such that b=xm·a·xn.(ii)
Generalized Symmetrical Decomposition Problem (GSDP). Given (a,b)∈G, S⊆G, and m,n∈Z, find x∈G such that b=xm·a·xn.The GSDP is evidently a sort of constrained SDP, and if subset S is large enough, then membership information in general does not help one to extract x from xm·a·xn. Now, it is understood that GSDP is at least as rigid as SDP. The following GSDP hypothesis says that it is not flexible to solve the same in probabilistic polynomial time with nonnegligible precision with respect to problem scale. In this regard these works are like discrete logarithm problem (DLP) over group G.


### 2.5. Computational Diffie-Hellman (CDH) Problem over Noncommutative GroupG

The CDH problem with respect to its subsetS on noncommutative group determines ax1x2 or ax2x1 for known a,ax1, and ax2, where x∈G,x1,x2∈S. The commutative law keeps an extraction property from x1∈G(x2), if it holds the relation for ax1x2=ax2x1. It is noticeable that DLP in GSDP over G is tractable. But the converse of the same is not true. At present, no clue is available to resolve this problem without extracting x1 (or x2) from a and ax1 (or ax2). Then, the CDH hypothesis over G says that problem over G is intractable. In this regard, no such probabilistic polynomial time algorithm exists to solve the dilemma with significant accuracy to problem extent. The same definition is also well distinct for a noncommutative semiring. Hence, DLP of GSDP and CDH assumptions over noncommutative semigroup are well appropriate.


## 2.1.Z-Modular Assumptions on Noncommutative Cryptography

The scalar multiplication is the basis for all cryptographic computations. The major goal of scalar multiplication is to generate the discrete logarithmic value. A new public key cryptography on polynomials scalar multiplication over the noncommutative ringR is proposed by Cao et al. in 2007 [32]. The developed scheme is based on modulo prime integers, named Z-modular method. The derived Z-modular structure on ring is Z(r), and this structure applies to positive Z+[r] and/or negative Z-[r] on noncommutative ring R elements, where r∈R is undetermined. Also, group and semiring are comprehensively applicable on Z-modular assumptions.


### 2.1.1. Noncommutative Rings onZ-Modular Method

The integral coefficient polynomial on additive noncommutative characterization is defined on ring(R,+,0) and for multiplicative noncommutative (R,·,1); the scalar multiplication over R is well defined for k∈Z+ and r∈R:(1)kr≅r+⋯+r︸ktimes.Further, for k∈Z-, (2)kr≅-r+⋯+-r︸-ktimes.Finally, if it is to be defined on scalar k=0, it is likely to be kr=0.Proposition 1.
In general, scalar multiplication on noncommutative property followsar·bs≠bs·ar, when r≠s. Recall a polynomial with positive integral coefficient fx=a0+a1x+⋯+anxn∈Z+, for all x. To assign the component x as an element r∈R, then attain a precise element in ring R as(3)fr=∑i=0nairi=a0·1+a1·x+⋯+an·xn.In addition, suppose r to be undetermined; then polynomial over f(r) is univariable polynomial lying on R. The univariable polynomial over R as a whole set is denoted as Z+[r], and it is defined as follows for the respective functions on two different ring elements:(4)fr=∑i=0nairi∈Z+r,hr=∑j=0mbjrj∈Z+r.Again, if n≥m, then(5)∑i=0nairi+∑j=0mbjrj=∑i=0mai+biri+∑i=m+1nairiand according to the property of distributive law it generalizes the above equation as(6)∑i=0nairi+∑j=0mbjrj=∑i=0n+mpirj,where,(7)pi=∑j=0iajbi-jri=∑j+k=iajbk.Theorem 2.
f r · h r = h r · f r,   ⍱fr∈Z+[r] and ⍱hr∈Z+[r], where ⍱ signify for all elements.Proof.
Here ringr is a subset of ring R applying to polynomial functions of fr and hr, for all positive integers of Z+[r]. A ring is a set of elements with two binary operations of addition and multiplication satisfying the following case properties on commutative law, associative law, identity, inverse, and closure. In addition to the same some more properties are also satisfying for all ring elements as follows:(i)
Closure under multiplication: ifa and b belong to ring element, then ab is also in ring.(ii)
Associative law of multiplication:a(bc)=(ab)c for all a,b,c.(iii)
Distributive laws:a(b+c)=ab+ac or (a+b)c=ac+bc for all a,b,c.(iv)
Commutative multiplication:ab=ba for a,b.(v)
Multiplicative identity:a·1=1·a=a for all a.(vi)
No zero divisors: for alla and b in R and ab=0, then, either a=0 or b=0 and this does not follow on dividing by zero.Therefore, this theorem proofs itself on the above properties of (i), (iii), and (iv).


## 2.1.1. Noncommutative Rings onZ-Modular Method

The integral coefficient polynomial on additive noncommutative characterization is defined on ring(R,+,0) and for multiplicative noncommutative (R,·,1); the scalar multiplication over R is well defined for k∈Z+ and r∈R:(1)kr≅r+⋯+r︸ktimes.Further, for k∈Z-, (2)kr≅-r+⋯+-r︸-ktimes.Finally, if it is to be defined on scalar k=0, it is likely to be kr=0.Proposition 1.
In general, scalar multiplication on noncommutative property followsar·bs≠bs·ar, when r≠s. Recall a polynomial with positive integral coefficient fx=a0+a1x+⋯+anxn∈Z+, for all x. To assign the component x as an element r∈R, then attain a precise element in ring R as(3)fr=∑i=0nairi=a0·1+a1·x+⋯+an·xn.In addition, suppose r to be undetermined; then polynomial over f(r) is univariable polynomial lying on R. The univariable polynomial over R as a whole set is denoted as Z+[r], and it is defined as follows for the respective functions on two different ring elements:(4)fr=∑i=0nairi∈Z+r,hr=∑j=0mbjrj∈Z+r.Again, if n≥m, then(5)∑i=0nairi+∑j=0mbjrj=∑i=0mai+biri+∑i=m+1nairiand according to the property of distributive law it generalizes the above equation as(6)∑i=0nairi+∑j=0mbjrj=∑i=0n+mpirj,where,(7)pi=∑j=0iajbi-jri=∑j+k=iajbk.Theorem 2.
f r · h r = h r · f r,   ⍱fr∈Z+[r] and ⍱hr∈Z+[r], where ⍱ signify for all elements.Proof.
Here ringr is a subset of ring R applying to polynomial functions of fr and hr, for all positive integers of Z+[r]. A ring is a set of elements with two binary operations of addition and multiplication satisfying the following case properties on commutative law, associative law, identity, inverse, and closure. In addition to the same some more properties are also satisfying for all ring elements as follows:(i)
Closure under multiplication: ifa and b belong to ring element, then ab is also in ring.(ii)
Associative law of multiplication:a(bc)=(ab)c for all a,b,c.(iii)
Distributive laws:a(b+c)=ab+ac or (a+b)c=ac+bc for all a,b,c.(iv)
Commutative multiplication:ab=ba for a,b.(v)
Multiplicative identity:a·1=1·a=a for all a.(vi)
No zero divisors: for alla and b in R and ab=0, then, either a=0 or b=0 and this does not follow on dividing by zero.Therefore, this theorem proofs itself on the above properties of (i), (iii), and (iv).


## 2.2. Two Well-Known Cryptographic Assumptions

The assumptions of security strength are due to the difficulty of the following two problems:(i)
Conjugacy Decisional Problem (CDP). It is, on the given two group elements a and b, to determine a random x to produce the value of other group elements, such that b=ax or to produce the same using the Conjugacy multiplicative inverse as b=x-1ax.(ii)
Conjugacy Search Problem (CSP). It is, for the two group elements of a and b in a group G, to find whether there exists x in G, such that b=ax or Conjugacy multiplicative inverse b=x-1ax.If no algorithm exists to solve the CSP, by applying x on one group of elements to determine the other group of elements, that is, a→bx, then this is considered to be a one-way function. In the contemporary computation, both problems on general noncommutative group G are too complicated enough to determine the assumptions on cryptographic primitives. The CSP assumptions are difficult enough to solve this problem on probabilistic polynomial time, whereas CDP assumptions are a unique representation for any group, ring, or semiring elements for cryptographic use. The CDP transition on all these assumptions finishing efficiently over each other is one of the major advantages.


## 2.3. Using Monomials inZ-Modular Method

The polynomials used inZ-modular method are constrained to be monomials; that is, if the original information of group elements is hidden with its equivalents ring or semiring elements, such participation in computation is viewed as a special case. Under these considerations new creations of public key encryption schemes from Conjugacy Search Problems are proposed.


### 2.3.1. Conjugacy Search Problem

Let(G,·,1) be a noncommutative monomial for an element a∈G, the other group element being b∈G, such that a·b=b·a; then it assumed that group a is invertible, and call b an inverse of a. Not all elements in G are invertible. If the inverse of a exists, it is unique and denoted by a-1. In monomials, the positive power of a group element for n integer is described as follows: an=a+⋯+a︸ntimes for n>1. If b is the inverse of a, one can also define the negative power of a by setting a-1=b+⋯+b︸ntimesfor n>1. The Conjugacy Search Problem can be extended to monomials G, for ∀a∈G and ∀x∈G-1, xax-1 is a conjugate to a, and call x as conjugator of the pair (a,xax-1).Definition 3 (Conjugacy Search Problem (CSP)).
LetG be a noncommutative monomial; the two elements a,b∈G so that b=xax-1 for some unknown element x∈G-1, and the objective of the CSP in G is to find x∈G-1 such that b=x′ax′-1.Definition 4 (left self-distributive system).
Suppose thatS is a nonempty set, F:S×S→S is a well-defined function, and let one denote F(a,b) by Fa(b). If the rewritten formula FrFsp=FFrsFrp,∀p,r,s∈S holds then call F·(·) as a left self-distributive system (LD).Theorem 5.
LetG be noncommutative monomial, the function F on conjugate follows as F:G-1×G→G,a,b↦aba-1 and is known by LD system, also abbreviated as Conj-LD.Proof.
According to Definition4, the term LD is an analogical observation from Fr(s) as a binary operation in r∗s; then this is observed as r∗(s∗p)=(r∗s)∗(r∗p), where “∗” is left distributive with respect to itself. The proof of these observations is following from left-hand side to right-hand side as follows: FrFsp=Frs∗p=r∗s∗p=r∗s∗r∗p=Frs∗Frp=FFrsFrp. Here, it is satisfying the function F on FrFsp=FFrsFrp as an LD system. Thus, Theorem 5 proof is based on these observations.Proposition 6.
LetF be a Conj-LD system defined over a noncommutative monomial G; then for the given a∈G-1 and b,c∈G, the following proposals are well-defined, according to [38]:(i)
Faa=a.(ii)
Fab=c⇔Fa-1c=b.(iii)
Fabc=FabFac.Proof of (i).
Sinceaaa-1=a, so Faa=a.Proof of (ii).
F a b = c → y i e l d s a b a - 1 = c → y i e l d s a - 1 c a = b → y i e l d s F a - 1 c = b.Proof of (iii).
F a b c = a b c a - 1 = a b a - 1 a c a - 1 = F a b F a c.


## 2.3.1. Conjugacy Search Problem

Let(G,·,1) be a noncommutative monomial for an element a∈G, the other group element being b∈G, such that a·b=b·a; then it assumed that group a is invertible, and call b an inverse of a. Not all elements in G are invertible. If the inverse of a exists, it is unique and denoted by a-1. In monomials, the positive power of a group element for n integer is described as follows: an=a+⋯+a︸ntimes for n>1. If b is the inverse of a, one can also define the negative power of a by setting a-1=b+⋯+b︸ntimesfor n>1. The Conjugacy Search Problem can be extended to monomials G, for ∀a∈G and ∀x∈G-1, xax-1 is a conjugate to a, and call x as conjugator of the pair (a,xax-1).Definition 3 (Conjugacy Search Problem (CSP)).
LetG be a noncommutative monomial; the two elements a,b∈G so that b=xax-1 for some unknown element x∈G-1, and the objective of the CSP in G is to find x∈G-1 such that b=x′ax′-1.Definition 4 (left self-distributive system).
Suppose thatS is a nonempty set, F:S×S→S is a well-defined function, and let one denote F(a,b) by Fa(b). If the rewritten formula FrFsp=FFrsFrp,∀p,r,s∈S holds then call F·(·) as a left self-distributive system (LD).Theorem 5.
LetG be noncommutative monomial, the function F on conjugate follows as F:G-1×G→G,a,b↦aba-1 and is known by LD system, also abbreviated as Conj-LD.Proof.
According to Definition4, the term LD is an analogical observation from Fr(s) as a binary operation in r∗s; then this is observed as r∗(s∗p)=(r∗s)∗(r∗p), where “∗” is left distributive with respect to itself. The proof of these observations is following from left-hand side to right-hand side as follows: FrFsp=Frs∗p=r∗s∗p=r∗s∗r∗p=Frs∗Frp=FFrsFrp. Here, it is satisfying the function F on FrFsp=FFrsFrp as an LD system. Thus, Theorem 5 proof is based on these observations.Proposition 6.
LetF be a Conj-LD system defined over a noncommutative monomial G; then for the given a∈G-1 and b,c∈G, the following proposals are well-defined, according to [38]:(i)
Faa=a.(ii)
Fab=c⇔Fa-1c=b.(iii)
Fabc=FabFac.Proof of (i).
Sinceaaa-1=a, so Faa=a.Proof of (ii).
F a b = c → y i e l d s a b a - 1 = c → y i e l d s a - 1 c a = b → y i e l d s F a - 1 c = b.Proof of (iii).
F a b c = a b c a - 1 = a b a - 1 a c a - 1 = F a b F a c.


## 2.4. Symmetry and Generalization Assumptions over Noncommutative Groups

To explain the symmetries, the generalizations on the noncommutative cryptography are the following problems on groupG:(i)
Symmetrical Decomposition Problem (SDP). Given (a,b)∈G and m,n∈Z, find x∈G such that b=xm·a·xn.(ii)
Generalized Symmetrical Decomposition Problem (GSDP). Given (a,b)∈G, S⊆G, and m,n∈Z, find x∈G such that b=xm·a·xn.The GSDP is evidently a sort of constrained SDP, and if subset S is large enough, then membership information in general does not help one to extract x from xm·a·xn. Now, it is understood that GSDP is at least as rigid as SDP. The following GSDP hypothesis says that it is not flexible to solve the same in probabilistic polynomial time with nonnegligible precision with respect to problem scale. In this regard these works are like discrete logarithm problem (DLP) over group G.


## 2.5. Computational Diffie-Hellman (CDH) Problem over Noncommutative GroupG

The CDH problem with respect to its subsetS on noncommutative group determines ax1x2 or ax2x1 for known a,ax1, and ax2, where x∈G,x1,x2∈S. The commutative law keeps an extraction property from x1∈G(x2), if it holds the relation for ax1x2=ax2x1. It is noticeable that DLP in GSDP over G is tractable. But the converse of the same is not true. At present, no clue is available to resolve this problem without extracting x1 (or x2) from a and ax1 (or ax2). Then, the CDH hypothesis over G says that problem over G is intractable. In this regard, no such probabilistic polynomial time algorithm exists to solve the dilemma with significant accuracy to problem extent. The same definition is also well distinct for a noncommutative semiring. Hence, DLP of GSDP and CDH assumptions over noncommutative semigroup are well appropriate.


## 3. Extra Special Group

The definition says that any primep to the power 1+2n, that is, p1+2n, sustains the twofold properties: (i) Heisenberg group and semidirect product of cyclic group order and/or (ii) dihedral order 8 and quaternion group. The two belonging group elements revolve around fixed center, known by extra special group [39]. These are based on finite size fields on modulo primes and analogues to group elements following sparse matrices properties. Due to this reason, group contains the dual identity, which meets the requirement for perfect cryptography. The quotients or remainders belong to nontrivial∗ (nontrivial∗ refers to terms or variables that are not equal to zero or identity after resultant) element, whose center is cyclic. Since its size is prime, so its classification is based on either prime p=2 or p=odd. The reason is clearly that any prime starts from 2, and the remaining primes only belong to odd numbers.Atp=odd. The extra special group, for p odd, is given below:(i)
The group of triangular3×3 matrices is over the field with p elements, with 1s on the diagonal. The group is exponent p for p odd. These are known by Heisenberg group elements.(ii)
There is the semidirect product of a cyclic group of orderp2 by a cyclic group of order p acting nontrivially on it.Again, if n is a positive integer, then for p odd the following is given.(i)
The central product ofn extra special group of order p3, all of exponent p: this extra special group also has exponent p.(ii)
The central product of orderp3: at least one of the exponents should be p2.Now, considerprime  p=2; the minimum order starts from n=1, so extra special group order 8=23 is described as follows:(i)
The dihedral groupD8 in order 8: this group has 4 elements of order 4.(ii)
The quaternion group of order8: it has six elements of order 4, for example,(8)1abc01de001f0001.Again, if we consider n as a positive integer for quaternion groups then,(i)
for an odd integer, the central product is in the quaternion group;(ii)
for an even integer, the central product is in the quaternion group.


### 3.1. Heisenberg Group

A group of3×3 upper triangular matrices contains the several representations in terms of functional spaces whose center acts nontrivially on it. A matrix multiplication is in the form(9)1ab01c001,where elements of a,b,c belong to commutative ring elements. Further, the real/integer numbers belong to ring structured elements, known by respective continuous/discrete Heisenberg group [40]. The continuous group comes from the description of quantum systems in one dimension. The association with n-dimensional systems is more general in this regard. The products of two Heisenberg matrices in the three-dimensional case are given by(10)1ab01c0011a′b′01c′001=1a+a′b+b′+ac′01c+c′001.The Heisenberg neutral element of group is the identity matrix. The discrete Heisenberg group x,y,z generator is the nonabelian group of ring elements on the integers a,b,c:(11)x=110010001,y=100011001and relations z=xx-1yy-1,   xz=zx, and   yz=zy, where z=101010001 is the generator with the center. A polynomial growth rate of order 3 using Bass’s theorem is used to generate any element through (12)x=1ab01c001=ybzcxa.The behavior of the Heisenberg group to modulo odd prime p over a finite field is called extra special group of exponent p.


#### 3.1.1. Security Strength of Heisenberg Group

The Heisenberg group on public key cryptography follows polycyclic behaviors if and only if a subseriesG1⊳G2⊳⋯⊳Gn+1=1 for a group G (where ⊳ denotes variations of G in cyclic form). Each positive integer of the nth elements of Heisenberg generates an infinite nonabelian form (using the binary addition and multiplication operations on matrix or sparse matrix elements), which makes the scheme of Heisenberg be practical choice for an efficient implementation on hardware and software. This gives a unique normal form just after group operations, so the group may be considered to be an effective solution provider for cryptographic use.


### 3.2. Dihedral Order 8

The dihedral order is a group of operations on a finite set of elements that includes the problems of mathematics and physics. A cycle of rotations and reflections on group elements is the basis that forms the properties of this group. One of the simplest examples of nonabelian group is dihedral order 6 [41].In the proposed work the minimum order is dihedral order 8, denoted byD8 (or also called D4) [42]. The subgroups of this (dihedral order group G) are generated by rotations and/or reflections; those are forming a cyclic subgroup which is one of the key advantages. For representing the dihedral order 8, a glass square of certain thickness with letter “F” is considered. The identity element is denoted by e. The letter “F” makes a visible difference upon rotation on 0°, 90°, 180°, and 270° in clockwise directions, as shown in Figure 1; it is further used in cryptographic purposes.Figure 1
Symmetries of dihedral order 8.One more “b” (reflection) operation is used relative to its corresponding above four rotations. Further, to define the composition movement such as “ba,” first do the operation for “a” and after that apply “b” as shown. For the remaining two of ba2 and ba3 are working as the previous one, now, after the corresponding operation, the same can be represented in four dimensions, as depicted in Figure 2. The group element is a property whose center and derived subgroup are fixed on explicit limitations under it.Figure 2
Four-dimensional representations.The abstract movements of all operations are fixed on certain boundaries, and these are generally represented by Cayley graph. The graph is mixed with eight vertices, four edges, and eight arrows. This is one of the fundamental tools in combinatorial theory to make group elements revolve around the fixed axis, as elaborated in Figure3.Figure 3
Cayley graph ofD4.Again, a table known by Cayley table is presented for a finite set of elements in all possible permutations by arranging its products in a square table reminiscent to multiplication. For the same, the dihedral order 8 based Cayley table is shown in Table1.Table 1
Cayley table.
e a a 2 a 3 b b a b a 2 b a 3 e e a a 2 a 3 b b a b a 2 b a 3 a a a 2 a 3 e b a 3 b b a b a 2 a 2 a 2 a 3 e a b a 2 b a 3 b b a a 3 a 3 e a a 2 b a b a 2 b a 3 b b b b a b a 2 b a 3 e a 3 a 2 a b a b a b a 2 b a 3 b a e a 3 a 2 b a 2 b a 2 b a 3 b b a a 2 a e a 3 b a 3 b a 3 b b a b a 2 a 3 a 2 a eFinally, we are correlating the same concept from mathematics. Here, the composition of eight different but interrelated operations forD8 is particularly specified for the mathematical suites that will be used in cryptographic applications, where mathematics is the foundation for almost all applications. Here is a similar consideration of the above concept on square glass; a different perspective to distinguish the same for the cryptography purposes is presented as a schematic representation in Figure 4. These are in the ordered group elements from G1 to G8 for rotations/movements and reflections in e,a,a2,a3,b,ba,ba2,ba3, as a resultant. A detailed cryptographic application scheme is considered in Sections 5.3 and 5.4.Figure 4
Schematic representation on dihedral order 8.


### 3.3. Quaternion Group

The quaternion group [43] is a nonabelian order of eight elements that forms of four-dimensional vector space over the real numbers. These are isomorphic to a subset of certain eight elements under multiplication. The group is generally indicated by Q or Q8 and is given by the group representation Q=-1,i,j,k∣-12=1,i2=j2=k2=ijk=-1, where 1 is the identity element and -1 commutes with the same. This is the same order as dihedral order D8, but the only difference is in its structure. So, it may be considered an immoderation of dihedral order 8. Depicted in Table 2 is a Cayley table for Q8.Table 2
Cayley table (quaternion group).
1 - 1 i - i j - j k - k 1 1 - 1 i - i j - j k - k - 1 - 1 1 - i i - j j - k k i i - i - 1 1 k - k - j j - i - i I 1 - 1 - k k j - j j j - j - k k - 1 1 i - i - j - j J k - k 1 - 1 - i i k k - k j - j - i i - 1 1 - k - k k - j j i - i 1 - 1


#### 3.3.1. Security Strength of Quaternion Group

Quaternion group using number theory gives multifold security properties in cryptography. The real beauty of quaternion is noncommutative nature and multiplication on these groups lies on a sphere in four-dimensional space. Due this nature, highest level of probable confusion can be achieved in applied applications and it can derive for enormous applications. The used matrices and algebra (where multiplication order is important for end user applications) make quaternion natured group elements bigger significance for the future security proposals. The resultant of quaternion easily converts to other representations just like the two original unit quaternions, where from the adversary side it is likely to be impossible to break such kind of scheme. Further, still analysis and implementation in cryptography are the need, which may give a high security specification on the quaternion group.


## 3.1. Heisenberg Group

A group of3×3 upper triangular matrices contains the several representations in terms of functional spaces whose center acts nontrivially on it. A matrix multiplication is in the form(9)1ab01c001,where elements of a,b,c belong to commutative ring elements. Further, the real/integer numbers belong to ring structured elements, known by respective continuous/discrete Heisenberg group [40]. The continuous group comes from the description of quantum systems in one dimension. The association with n-dimensional systems is more general in this regard. The products of two Heisenberg matrices in the three-dimensional case are given by(10)1ab01c0011a′b′01c′001=1a+a′b+b′+ac′01c+c′001.The Heisenberg neutral element of group is the identity matrix. The discrete Heisenberg group x,y,z generator is the nonabelian group of ring elements on the integers a,b,c:(11)x=110010001,y=100011001and relations z=xx-1yy-1,   xz=zx, and   yz=zy, where z=101010001 is the generator with the center. A polynomial growth rate of order 3 using Bass’s theorem is used to generate any element through (12)x=1ab01c001=ybzcxa.The behavior of the Heisenberg group to modulo odd prime p over a finite field is called extra special group of exponent p.


### 3.1.1. Security Strength of Heisenberg Group

The Heisenberg group on public key cryptography follows polycyclic behaviors if and only if a subseriesG1⊳G2⊳⋯⊳Gn+1=1 for a group G (where ⊳ denotes variations of G in cyclic form). Each positive integer of the nth elements of Heisenberg generates an infinite nonabelian form (using the binary addition and multiplication operations on matrix or sparse matrix elements), which makes the scheme of Heisenberg be practical choice for an efficient implementation on hardware and software. This gives a unique normal form just after group operations, so the group may be considered to be an effective solution provider for cryptographic use.


## 3.1.1. Security Strength of Heisenberg Group

The Heisenberg group on public key cryptography follows polycyclic behaviors if and only if a subseriesG1⊳G2⊳⋯⊳Gn+1=1 for a group G (where ⊳ denotes variations of G in cyclic form). Each positive integer of the nth elements of Heisenberg generates an infinite nonabelian form (using the binary addition and multiplication operations on matrix or sparse matrix elements), which makes the scheme of Heisenberg be practical choice for an efficient implementation on hardware and software. This gives a unique normal form just after group operations, so the group may be considered to be an effective solution provider for cryptographic use.


## 3.2. Dihedral Order 8

The dihedral order is a group of operations on a finite set of elements that includes the problems of mathematics and physics. A cycle of rotations and reflections on group elements is the basis that forms the properties of this group. One of the simplest examples of nonabelian group is dihedral order 6 [41].In the proposed work the minimum order is dihedral order 8, denoted byD8 (or also called D4) [42]. The subgroups of this (dihedral order group G) are generated by rotations and/or reflections; those are forming a cyclic subgroup which is one of the key advantages. For representing the dihedral order 8, a glass square of certain thickness with letter “F” is considered. The identity element is denoted by e. The letter “F” makes a visible difference upon rotation on 0°, 90°, 180°, and 270° in clockwise directions, as shown in Figure 1; it is further used in cryptographic purposes.Figure 1
Symmetries of dihedral order 8.One more “b” (reflection) operation is used relative to its corresponding above four rotations. Further, to define the composition movement such as “ba,” first do the operation for “a” and after that apply “b” as shown. For the remaining two of ba2 and ba3 are working as the previous one, now, after the corresponding operation, the same can be represented in four dimensions, as depicted in Figure 2. The group element is a property whose center and derived subgroup are fixed on explicit limitations under it.Figure 2
Four-dimensional representations.The abstract movements of all operations are fixed on certain boundaries, and these are generally represented by Cayley graph. The graph is mixed with eight vertices, four edges, and eight arrows. This is one of the fundamental tools in combinatorial theory to make group elements revolve around the fixed axis, as elaborated in Figure3.Figure 3
Cayley graph ofD4.Again, a table known by Cayley table is presented for a finite set of elements in all possible permutations by arranging its products in a square table reminiscent to multiplication. For the same, the dihedral order 8 based Cayley table is shown in Table1.Table 1
Cayley table.
e a a 2 a 3 b b a b a 2 b a 3 e e a a 2 a 3 b b a b a 2 b a 3 a a a 2 a 3 e b a 3 b b a b a 2 a 2 a 2 a 3 e a b a 2 b a 3 b b a a 3 a 3 e a a 2 b a b a 2 b a 3 b b b b a b a 2 b a 3 e a 3 a 2 a b a b a b a 2 b a 3 b a e a 3 a 2 b a 2 b a 2 b a 3 b b a a 2 a e a 3 b a 3 b a 3 b b a b a 2 a 3 a 2 a eFinally, we are correlating the same concept from mathematics. Here, the composition of eight different but interrelated operations forD8 is particularly specified for the mathematical suites that will be used in cryptographic applications, where mathematics is the foundation for almost all applications. Here is a similar consideration of the above concept on square glass; a different perspective to distinguish the same for the cryptography purposes is presented as a schematic representation in Figure 4. These are in the ordered group elements from G1 to G8 for rotations/movements and reflections in e,a,a2,a3,b,ba,ba2,ba3, as a resultant. A detailed cryptographic application scheme is considered in Sections 5.3 and 5.4.Figure 4
Schematic representation on dihedral order 8.


## 3.3. Quaternion Group

The quaternion group [43] is a nonabelian order of eight elements that forms of four-dimensional vector space over the real numbers. These are isomorphic to a subset of certain eight elements under multiplication. The group is generally indicated by Q or Q8 and is given by the group representation Q=-1,i,j,k∣-12=1,i2=j2=k2=ijk=-1, where 1 is the identity element and -1 commutes with the same. This is the same order as dihedral order D8, but the only difference is in its structure. So, it may be considered an immoderation of dihedral order 8. Depicted in Table 2 is a Cayley table for Q8.Table 2
Cayley table (quaternion group).
1 - 1 i - i j - j k - k 1 1 - 1 i - i j - j k - k - 1 - 1 1 - i i - j j - k k i i - i - 1 1 k - k - j j - i - i I 1 - 1 - k k j - j j j - j - k k - 1 1 i - i - j - j J k - k 1 - 1 - i i k k - k j - j - i i - 1 1 - k - k k - j j i - i 1 - 1


### 3.3.1. Security Strength of Quaternion Group

Quaternion group using number theory gives multifold security properties in cryptography. The real beauty of quaternion is noncommutative nature and multiplication on these groups lies on a sphere in four-dimensional space. Due this nature, highest level of probable confusion can be achieved in applied applications and it can derive for enormous applications. The used matrices and algebra (where multiplication order is important for end user applications) make quaternion natured group elements bigger significance for the future security proposals. The resultant of quaternion easily converts to other representations just like the two original unit quaternions, where from the adversary side it is likely to be impossible to break such kind of scheme. Further, still analysis and implementation in cryptography are the need, which may give a high security specification on the quaternion group.


## 3.3.1. Security Strength of Quaternion Group

Quaternion group using number theory gives multifold security properties in cryptography. The real beauty of quaternion is noncommutative nature and multiplication on these groups lies on a sphere in four-dimensional space. Due this nature, highest level of probable confusion can be achieved in applied applications and it can derive for enormous applications. The used matrices and algebra (where multiplication order is important for end user applications) make quaternion natured group elements bigger significance for the future security proposals. The resultant of quaternion easily converts to other representations just like the two original unit quaternions, where from the adversary side it is likely to be impossible to break such kind of scheme. Further, still analysis and implementation in cryptography are the need, which may give a high security specification on the quaternion group.


## 4. Noncommutative Cryptography on Groups and Rings

The mathematical rationalization over matrix group or ring is exemplified onMZN, based on N=p·q, where p and q are two secure primes. This is intractable, in view of the fact that A=a000∈MZN,a∈ZN, from A2=a2000∈MZN with no significant factors of N [32].The above-mentioned ring can be enhanced with respect to security by using special or peculiar sparse matrices of rings elements, as our contribution, which shows the stronger security specifications on described Sections3.1.1 and 3.3.1 which are based on Heisenberg and quaternion group, respectively. Further, noncommutative nature of generated semiring elements for dihedral order of 8 (presented in next section) also satisfies the properties of N very well.


### 4.1. Key Exchange Algorithm on Noncommutative Cryptography

The noncommutative key exchange cryptography works reminiscent of Diffie-Hellman key exchange [44] similar to a commutative case, but the major distinction is the itinerary actions on selection of global parameters, generation of private keys, production rule for shared secret session keys, and encryption-decryption. The effectiveness of the algorithm depends on the impenetrability of computing the DLP. The security of the algorithm lies in the prime factorization on two secure primes, random private polynomial chosen by user A and user B, respectively. A detailed elaboration through the numerical example on ring and quaternion group for key exchange and encryption-decryption is presented in this section, which belongs to the extra special group.The key exchange agreement over matrix ring elements is depicted as follows.Key Exchange on Noncommutative RingGlobal Public Parameters m , n: integers Z+ a , b: ring elementsUser A Key Generation (i)
Select private random polynomial:f(x). (ii)
Iff(a)≠0, then f(a) is considered as private key. (iii)
Generation of public keyXA: XA=f(a)m·b·f(a)n.User B Key Generation (i)
Select private random polynomial:h(x). (ii)
Ifh(a)≠0, then h(a) is considered as private key. (iii)
Generation of public keyXB: XB=h(a)m·b·h(a)n.Generation of Secret Key by User A K A = f ( a ) m · X B · f ( a ) n.Generation of Secret Key by User B K B = h ( a ) m · X A · h ( a ) n.The global parameters are(13)m=3,n=5,a=17574,b=1932,N=7∗11.User A chose their random polynomial fx=3x3+4x2+5x+1. Evaluate the polynomial fa; if fa≠0 then the polynomial will be considered as a private key for user A. The A’s private key is as follows:(14)fa=3175743+4175742+517574+1·I=19202844mod⁡77.Now, the generation of public key XA by user A is as follows:(15)XA=fam·b·fan=192028443·1932·192028445=35692mod⁡77.At the other end user B chose their own random polynomial hx=x5+5x+1. Further, evaluate the polynomial ha, and if ha≠0 then this polynomial value will be considered as private key:(16)ha=175745+517574+1·I=70524258mod⁡77and the generation of public key for user B is as follows: (17)XB=ham·b·han=705242583·1932·705242585=0393568mod⁡77.Finally, the session key is extracted by the user A as KA:(18)KA=fam·XB·fan=192028443·0393568·192028445=21374969mod⁡77and the session key is extracted from user B as KB:(19)KB=ham·XA·han=705242483·35692·705242485=21374969mod⁡77.


### 4.2. Key Exchange Using Heisenberg Group (Upper Triangular Matrices)

Further, we applied the same algorithm for session key establishment over a Heisenberg group. It is demonstrated on the global parameters, where assumptions are(20)m=3,n=5,a=157014001,b=169013001,N=7∗11.For user A, a random polynomial is chosen: fx=3x3+4x2+5x+6. Evaluate the polynomial on fa, and if fa≠0 then polynomial value is considered as a private key for user A:(21)fa=31570140013+41570140012+5157014001+6I=183329018110018mod⁡77.The generation of public key XA by user A is as follows:(22)XA=fam·b·fan=1833290181100183·169013001·1833290181100185=932100971009mod⁡77.At the other end user B chose their own random polynomial hx=x5+5x+1. Evaluating the polynomial ha, the private key is as follows:(23)ha=1570140015+5157014001+1I=750390740007mod⁡77and the generation of public key for user B is as follows:(24)XB=ham·b·han=7503907400073·169013001·7503907400075=42563504200042mod⁡77.Finally, the session key extracted by the user A as KA is as follows:(25)KA=fam·XB·fan=1833290181100183·42563504200042·1833290181100185=70422807000070mod⁡77and the session key extracted by user B as KB is as follows:(26)KB=ham·XA·han=7503907400073·932100971009·7503907400075=70422807000070mod⁡77.


### 4.3. Encryption-Decryption Algorithm on Heisenberg Group

The encryption-decryption procedure on Heisenberg group is offered as follows.Encryption-Decryption Algorithm on Noncommutative RingGlobal Public Parameters m , n: integers Z+ a , b: ring elements M: message H ( M ): hashed messageUser A Key Generation (i)
Select private random polynomial:f(x). (ii)
Iff(a)≠0, then f(a) is considered as private key. (iii)
Generation of public keyXA: XA=f(a)m·b·f(a)n.User B Key Generation (i)
Select private random polynomial:h(x). (ii)
Ifh(a)≠0, then h(a) is considered as private key. (iii)
Generation of public keyXB: XB=h(a)m·b·h(a)n.Encryption (by Sender B ) C: ciphertext D: decryption key C = h ( a ) m · b · h ( a ) n, D=H(ham·XA·han)⊕MDecryption M = H ( f a m · C · f a n ) ⊕ DThe approach of noncommutative cryptography works like the general case, where our assumptions are as(27)m=3,n=5,a=159019001,b=195013001,N=7∗11,M=27192534874559.User A randomly chose a random polynomial fx=3x3+4x2+5x+6; then f(a) is considered to be private key:(28)fa=31590190013+41590190012+5159019001+6I=183313018440018mod⁡77.The generation of public key is as follows:(29)XA=fam·b·fan=1833130184400183·195013001·1833130184400185=959420949009mod⁡77.Moving onwards, user B randomly chose their own random polynomial hx=x5+5x+1 and computes private key if h(a)≠0:(30)ha=1590190015+5159019001+1·I=75010713007mod⁡77and the public key generated for user B is as follows: (31)XB=ham·b·han=750107130073·195013001·750107130075=422835042350042mod⁡77.The sender of the public key is treated as ciphertext C (in our case user B is sender): (32)
C
=
h
a
m
·
b
·
h
a
n
=
42
28
35
0
42
35
0
0
42
,
D
=
H
h
a
m
·
X
A
·
h
a
n
⊕
M
=
H
7
50
1
0
7
13
0
0
7
3
·
9
59
42
0
9
49
0
0
9
·
9
59
42
0
9
49
0
0
9
5
⊕
27
19
25
34
8
7
45
5
9
=
H
70
21
35
0
70
7
0
0
70
⊕
27
19
25
34
8
7
45
5
9
=
12
42
57
35
31
52
44
4
30
.The original message is as follows:(33)
M
′
=
H
f
a
m
·
C
·
f
a
n
⊕
D
=
H
18
33
13
0
18
44
0
0
18
3
·
42
28
35
0
42
35
0
0
42
·
18
33
13
0
18
44
0
0
18
5
⊕
12
42
57
35
31
52
44
4
30
=
27
19
25
34
8
7
45
5
9
.


### 4.4. Analysis and Strength of Proposed Scheme

We are now explaining the computational hardness or complexity analysis with its related strength as security and performance considerations (mostly on each parameter of algorithms).Prime Factors of N. The proposed procedure stands on hidden prime factorization of N (N is absent in the proposed algorithm, but due to explicit clarification it is shown wherever needed) being the points mentioned below in support of strong security analysis.(i)
SinceN=7∗11 is based on two prime factors and factorization of N has extreme difficulty in finding its exact factors due its computer intensive nature for large primes, to find an algorithm which does it fast is one of unsolved problems of computer science.(ii)
The time required into prime factor grows exponentially, so if the algorithm uses large prime based integers, it is unrealistic to crack it down.(iii)
Prime factorization is mostly a unique problem, and all integers (except1 and 0) are made up of primes, because this ingeniousness allows hardly encoding any information of any length as a single integer is inflexible.Private Keys. A secret key generation is based on random chosen polynomial f(x) or h(x), since polynomial is called irreducible if and only if it cannot be expressed as product of two polynomials. An integer analogy of irreducible polynomial is called a prime polynomial. A polynomial contains the three classes of polynomials such as(i)
ordinary polynomial,(ii)
modulo prime based polynomial,(iii)
modulo prime based polynomial defined on another polynomial whose power is in some integern.In class (i) arithmetic operation (addition, subtraction, and multiplication) performs on polynomials using the ordinary rules of algebra, and division is only possible if the field elements are coefficients of the same. Class (ii) contains the arithmetic operations as of (i), but the division result is used (in general) in quotient and remainder forms. This represents a special significance in cryptography because it gives a unique solution for the above prime factorization on specified problem. Here class (iii) is not elaborated, because proposed approach is working on (i) and/or (ii).Public Keys. The polynomial functions of f(x) or h(x) to the power of m and n with two multiplications on modulo prime are the basis for public key generation for respective senders and receivers. The generated public key (which passed into the medium) is represented as a Discrete Log Problem (DLP) for the algorithm since it is established on modulo prime based polynomials that are irreducible in these contexts. Adversaries try to conceptualize the secret key on the global parameters and public key; those are freely available. According to proposed scheme, a large prime factor of N (standard length 160bits) may be sufficient for making adversaries against getting fruitful ideas or valid secret keys.Timing Attack. Timing attacks is a stunning way abstracting the pattern generated from the cryptographic algorithm and trying to access the security appearance from electromagnetic signals released from the computer systems. The release of signals and transmissions are the part of computer operations. The signals are alarming in the two senses: (i) a random interference comes first, which can be only be burglars, and (ii) these signals can be amplified through some auxiliary equipment for some useful purposes. A report is available suggesting electromagnetic radiation interference with radio navigation devices, as (i) it is a general procedure and it is not a point to be considerable issue and (ii) it applies to those interested in such pattern of abstractions for decoding that may lead to vulnerable information safeties, feedbacks observations, and/or secret information leakage, where an adversary tries to determine the private key by keeping track on how long a computer takes to decipher the secrets messages.In practice, polynomial modular exponentiation implementation does lead to extreme timing variations. Therefore, the uniqueness nature of polynomial based cryptographic measures makes a practical choice for future security work, with specific addition to noncommutative properties. Instead of the same, there are some countermeasures, which may lead to strengthening the measures in timing variation effects.Polynomial Exponentiation Time. Since all exponentials take different amount of time before returning to final result, this one is simply fix, so performance analysis does not degrade its efficiency with its variances.Random Delay. One can get a better performance by adding a random delay to the exponentials in applied algorithms and may confuse the timing attacks.Blinding. It can confuse the adversary by multiplying a random number into the ciphertext before performing exponentiation. This can be one way to make adversaries outreach from original ciphers.Brute-Force Attacks. The brute-force attacks refer to finding all the possible secret keys. The defense against attacks shows larger randomness and unpredictability behavior on a shorter key length on our proposed approach; since it is a special case of Elliptic Curve Cryptography (ECC), therefore the algorithm sufficiently works on a smaller length keys. The execution time of smaller length key takes a shorter time, so it reflects a big impact on efficiency. A lot of reports are available regarding the computational performance for ECC and RSA algorithms, where our approach (noncommutative) regarding the efficiency, speed, and cryptanalysis is better in them.Chosen Ciphertext Attacks. This attack is a form of active attack, where adversaries try to find plaintext corresponding to its ciphertexts by its choice. The first choice may experience decryption module on a random chosen ciphertext, before the actual ciphertext sent for an interested use. The second choice involves the same module on input of one’s choice at any time, where all these are recorded and try to gain the actual plaintexts. The presented algorithm experienced a blind feedback, where the noncommutative cryptography is not a vulnerable one to chosen ciphertext attacks (CCA) especially for ring or semiring, group, and Heisenberg elements, because in CCA an adversary chooses a number of ciphertexts and tries decryption with targeted private keys, where the chosen ciphertext is hashed with the corresponding polynomial exponentials.Simulation and Importance of Hash Uses. The simulation of hash H is based on power of 2 functions on Matlab tool, where the importance of hash function dictates the following properties: (i) output of hash generates pseudorandomness for the standard cryptographic tests, (ii) hash is relatively easy to compute for any given input that makes a practical use for hardware and software implementation, (iii) for any given hash H, it is computationally infeasible to find y such that H(y)=x, (iv) for any pair (x,y) it is computationally infeasible to find H(x)=H(y) is a strong collision resistant property, and (v) for any block x, it is computationally infeasible to find y≠x is a weak collision resistant property.


## 4.1. Key Exchange Algorithm on Noncommutative Cryptography

The noncommutative key exchange cryptography works reminiscent of Diffie-Hellman key exchange [44] similar to a commutative case, but the major distinction is the itinerary actions on selection of global parameters, generation of private keys, production rule for shared secret session keys, and encryption-decryption. The effectiveness of the algorithm depends on the impenetrability of computing the DLP. The security of the algorithm lies in the prime factorization on two secure primes, random private polynomial chosen by user A and user B, respectively. A detailed elaboration through the numerical example on ring and quaternion group for key exchange and encryption-decryption is presented in this section, which belongs to the extra special group.The key exchange agreement over matrix ring elements is depicted as follows.Key Exchange on Noncommutative RingGlobal Public Parameters m , n: integers Z+ a , b: ring elementsUser A Key Generation (i)
Select private random polynomial:f(x). (ii)
Iff(a)≠0, then f(a) is considered as private key. (iii)
Generation of public keyXA: XA=f(a)m·b·f(a)n.User B Key Generation (i)
Select private random polynomial:h(x). (ii)
Ifh(a)≠0, then h(a) is considered as private key. (iii)
Generation of public keyXB: XB=h(a)m·b·h(a)n.Generation of Secret Key by User A K A = f ( a ) m · X B · f ( a ) n.Generation of Secret Key by User B K B = h ( a ) m · X A · h ( a ) n.The global parameters are(13)m=3,n=5,a=17574,b=1932,N=7∗11.User A chose their random polynomial fx=3x3+4x2+5x+1. Evaluate the polynomial fa; if fa≠0 then the polynomial will be considered as a private key for user A. The A’s private key is as follows:(14)fa=3175743+4175742+517574+1·I=19202844mod⁡77.Now, the generation of public key XA by user A is as follows:(15)XA=fam·b·fan=192028443·1932·192028445=35692mod⁡77.At the other end user B chose their own random polynomial hx=x5+5x+1. Further, evaluate the polynomial ha, and if ha≠0 then this polynomial value will be considered as private key:(16)ha=175745+517574+1·I=70524258mod⁡77and the generation of public key for user B is as follows: (17)XB=ham·b·han=705242583·1932·705242585=0393568mod⁡77.Finally, the session key is extracted by the user A as KA:(18)KA=fam·XB·fan=192028443·0393568·192028445=21374969mod⁡77and the session key is extracted from user B as KB:(19)KB=ham·XA·han=705242483·35692·705242485=21374969mod⁡77.


## 4.2. Key Exchange Using Heisenberg Group (Upper Triangular Matrices)

Further, we applied the same algorithm for session key establishment over a Heisenberg group. It is demonstrated on the global parameters, where assumptions are(20)m=3,n=5,a=157014001,b=169013001,N=7∗11.For user A, a random polynomial is chosen: fx=3x3+4x2+5x+6. Evaluate the polynomial on fa, and if fa≠0 then polynomial value is considered as a private key for user A:(21)fa=31570140013+41570140012+5157014001+6I=183329018110018mod⁡77.The generation of public key XA by user A is as follows:(22)XA=fam·b·fan=1833290181100183·169013001·1833290181100185=932100971009mod⁡77.At the other end user B chose their own random polynomial hx=x5+5x+1. Evaluating the polynomial ha, the private key is as follows:(23)ha=1570140015+5157014001+1I=750390740007mod⁡77and the generation of public key for user B is as follows:(24)XB=ham·b·han=7503907400073·169013001·7503907400075=42563504200042mod⁡77.Finally, the session key extracted by the user A as KA is as follows:(25)KA=fam·XB·fan=1833290181100183·42563504200042·1833290181100185=70422807000070mod⁡77and the session key extracted by user B as KB is as follows:(26)KB=ham·XA·han=7503907400073·932100971009·7503907400075=70422807000070mod⁡77.


## 4.3. Encryption-Decryption Algorithm on Heisenberg Group

The encryption-decryption procedure on Heisenberg group is offered as follows.Encryption-Decryption Algorithm on Noncommutative RingGlobal Public Parameters m , n: integers Z+ a , b: ring elements M: message H ( M ): hashed messageUser A Key Generation (i)
Select private random polynomial:f(x). (ii)
Iff(a)≠0, then f(a) is considered as private key. (iii)
Generation of public keyXA: XA=f(a)m·b·f(a)n.User B Key Generation (i)
Select private random polynomial:h(x). (ii)
Ifh(a)≠0, then h(a) is considered as private key. (iii)
Generation of public keyXB: XB=h(a)m·b·h(a)n.Encryption (by Sender B ) C: ciphertext D: decryption key C = h ( a ) m · b · h ( a ) n, D=H(ham·XA·han)⊕MDecryption M = H ( f a m · C · f a n ) ⊕ DThe approach of noncommutative cryptography works like the general case, where our assumptions are as(27)m=3,n=5,a=159019001,b=195013001,N=7∗11,M=27192534874559.User A randomly chose a random polynomial fx=3x3+4x2+5x+6; then f(a) is considered to be private key:(28)fa=31590190013+41590190012+5159019001+6I=183313018440018mod⁡77.The generation of public key is as follows:(29)XA=fam·b·fan=1833130184400183·195013001·1833130184400185=959420949009mod⁡77.Moving onwards, user B randomly chose their own random polynomial hx=x5+5x+1 and computes private key if h(a)≠0:(30)ha=1590190015+5159019001+1·I=75010713007mod⁡77and the public key generated for user B is as follows: (31)XB=ham·b·han=750107130073·195013001·750107130075=422835042350042mod⁡77.The sender of the public key is treated as ciphertext C (in our case user B is sender): (32)
C
=
h
a
m
·
b
·
h
a
n
=
42
28
35
0
42
35
0
0
42
,
D
=
H
h
a
m
·
X
A
·
h
a
n
⊕
M
=
H
7
50
1
0
7
13
0
0
7
3
·
9
59
42
0
9
49
0
0
9
·
9
59
42
0
9
49
0
0
9
5
⊕
27
19
25
34
8
7
45
5
9
=
H
70
21
35
0
70
7
0
0
70
⊕
27
19
25
34
8
7
45
5
9
=
12
42
57
35
31
52
44
4
30
.The original message is as follows:(33)
M
′
=
H
f
a
m
·
C
·
f
a
n
⊕
D
=
H
18
33
13
0
18
44
0
0
18
3
·
42
28
35
0
42
35
0
0
42
·
18
33
13
0
18
44
0
0
18
5
⊕
12
42
57
35
31
52
44
4
30
=
27
19
25
34
8
7
45
5
9
.


## 4.4. Analysis and Strength of Proposed Scheme

We are now explaining the computational hardness or complexity analysis with its related strength as security and performance considerations (mostly on each parameter of algorithms).Prime Factors of N. The proposed procedure stands on hidden prime factorization of N (N is absent in the proposed algorithm, but due to explicit clarification it is shown wherever needed) being the points mentioned below in support of strong security analysis.(i)
SinceN=7∗11 is based on two prime factors and factorization of N has extreme difficulty in finding its exact factors due its computer intensive nature for large primes, to find an algorithm which does it fast is one of unsolved problems of computer science.(ii)
The time required into prime factor grows exponentially, so if the algorithm uses large prime based integers, it is unrealistic to crack it down.(iii)
Prime factorization is mostly a unique problem, and all integers (except1 and 0) are made up of primes, because this ingeniousness allows hardly encoding any information of any length as a single integer is inflexible.Private Keys. A secret key generation is based on random chosen polynomial f(x) or h(x), since polynomial is called irreducible if and only if it cannot be expressed as product of two polynomials. An integer analogy of irreducible polynomial is called a prime polynomial. A polynomial contains the three classes of polynomials such as(i)
ordinary polynomial,(ii)
modulo prime based polynomial,(iii)
modulo prime based polynomial defined on another polynomial whose power is in some integern.In class (i) arithmetic operation (addition, subtraction, and multiplication) performs on polynomials using the ordinary rules of algebra, and division is only possible if the field elements are coefficients of the same. Class (ii) contains the arithmetic operations as of (i), but the division result is used (in general) in quotient and remainder forms. This represents a special significance in cryptography because it gives a unique solution for the above prime factorization on specified problem. Here class (iii) is not elaborated, because proposed approach is working on (i) and/or (ii).Public Keys. The polynomial functions of f(x) or h(x) to the power of m and n with two multiplications on modulo prime are the basis for public key generation for respective senders and receivers. The generated public key (which passed into the medium) is represented as a Discrete Log Problem (DLP) for the algorithm since it is established on modulo prime based polynomials that are irreducible in these contexts. Adversaries try to conceptualize the secret key on the global parameters and public key; those are freely available. According to proposed scheme, a large prime factor of N (standard length 160bits) may be sufficient for making adversaries against getting fruitful ideas or valid secret keys.Timing Attack. Timing attacks is a stunning way abstracting the pattern generated from the cryptographic algorithm and trying to access the security appearance from electromagnetic signals released from the computer systems. The release of signals and transmissions are the part of computer operations. The signals are alarming in the two senses: (i) a random interference comes first, which can be only be burglars, and (ii) these signals can be amplified through some auxiliary equipment for some useful purposes. A report is available suggesting electromagnetic radiation interference with radio navigation devices, as (i) it is a general procedure and it is not a point to be considerable issue and (ii) it applies to those interested in such pattern of abstractions for decoding that may lead to vulnerable information safeties, feedbacks observations, and/or secret information leakage, where an adversary tries to determine the private key by keeping track on how long a computer takes to decipher the secrets messages.In practice, polynomial modular exponentiation implementation does lead to extreme timing variations. Therefore, the uniqueness nature of polynomial based cryptographic measures makes a practical choice for future security work, with specific addition to noncommutative properties. Instead of the same, there are some countermeasures, which may lead to strengthening the measures in timing variation effects.Polynomial Exponentiation Time. Since all exponentials take different amount of time before returning to final result, this one is simply fix, so performance analysis does not degrade its efficiency with its variances.Random Delay. One can get a better performance by adding a random delay to the exponentials in applied algorithms and may confuse the timing attacks.Blinding. It can confuse the adversary by multiplying a random number into the ciphertext before performing exponentiation. This can be one way to make adversaries outreach from original ciphers.Brute-Force Attacks. The brute-force attacks refer to finding all the possible secret keys. The defense against attacks shows larger randomness and unpredictability behavior on a shorter key length on our proposed approach; since it is a special case of Elliptic Curve Cryptography (ECC), therefore the algorithm sufficiently works on a smaller length keys. The execution time of smaller length key takes a shorter time, so it reflects a big impact on efficiency. A lot of reports are available regarding the computational performance for ECC and RSA algorithms, where our approach (noncommutative) regarding the efficiency, speed, and cryptanalysis is better in them.Chosen Ciphertext Attacks. This attack is a form of active attack, where adversaries try to find plaintext corresponding to its ciphertexts by its choice. The first choice may experience decryption module on a random chosen ciphertext, before the actual ciphertext sent for an interested use. The second choice involves the same module on input of one’s choice at any time, where all these are recorded and try to gain the actual plaintexts. The presented algorithm experienced a blind feedback, where the noncommutative cryptography is not a vulnerable one to chosen ciphertext attacks (CCA) especially for ring or semiring, group, and Heisenberg elements, because in CCA an adversary chooses a number of ciphertexts and tries decryption with targeted private keys, where the chosen ciphertext is hashed with the corresponding polynomial exponentials.Simulation and Importance of Hash Uses. The simulation of hash H is based on power of 2 functions on Matlab tool, where the importance of hash function dictates the following properties: (i) output of hash generates pseudorandomness for the standard cryptographic tests, (ii) hash is relatively easy to compute for any given input that makes a practical use for hardware and software implementation, (iii) for any given hash H, it is computationally infeasible to find y such that H(y)=x, (iv) for any pair (x,y) it is computationally infeasible to find H(x)=H(y) is a strong collision resistant property, and (v) for any block x, it is computationally infeasible to find y≠x is a weak collision resistant property.


## 5. Monomials Based Cryptography Using Noncommutative Groups and Semirings

The polynomial used inZ-modular method for noncommutative cryptography is based on the group elements running at the back end and its equivalent semirings elements work from the front, known by the monomials generated schemes. In this regard the original information is hidden, where for an adversary it will be practically impossible to decipher the original information. Such kind of participation in computation is viewed as a special case. We have formulated the semiring elements that are working perfectly under the assumptions of our dihedral order 8, which is a part of extra special group. The section is first exploring the basic assumptions on monomials and then proposed works are detailed.


### 5.1. Extension of Noncommutative Groups

For a noncommutative group(G,·,1G) and ring elements (R,+,·,1R), monomials generations that are possible through the use of group and ring elements can be defined as τ:(G,·,1G)→(R,·,1R). The inverse map τ-1:τ(G)→G  is also a well-defined monomial. If a,b∈G, then it is true for τa+τ(b)∈τ(G); from the same one can assign a new element c∈G as c≜τ-1τa+τ(b) which is possible. Here c is called as a quasi-sum of a and b and is denoted by c=a⊞b [31]. Similarly, for k∈R and a∈G, if k·τa∈τ(G), then one can assign a new element d∈G as d≅τ-1(k·τa) and call d as quasi-multiple of a, denoted by d=k⊠a. Then, the monomial τ in a linear sense holds the following equalities:(34)τk⊠a⊞b=τk⊠a⊞b=τd⊞b=ττ-1τd⊞τb=ττ-1ττ-1k·τa⊞τb=ττ-1k·τa⊞τb=k·τa+τb.For a,b∈G and k·τa+τb∈τG, function fx=z0+z1x+⋯+znxn∈Zx can be defined as(35)fτa=z0·1R+z1·τa+⋯zn·τan∈τG.Now, assign a new element e∈G as(36)e=τ-1fa=τ-1z0·1R+z1·τa+⋯zn·τan.If it holds to find the inverse of polynomials, call e as quasi-polynomial of f on a, denoted by e=f(a). For, arbitrary a,b∈G,k∈R and f(x)∈Z[x], a⊞b,  k⊠a, and f(a) are not always well defined. Theorem 7 is natural and general scheme, which works for noncommutative monomials.Theorem 7.
For somea∈G and some f(x),h(x)∈Z[x], if f(a) and h(a) are well defined, then (i) τfa=fτa and (ii) fa·ha=ha·f(a).Proof.
(i) Due to property of monomials on quasi-polynomial, the group element for any functionf applies with its equivalent ring elements, so in the intermediary function f results in ring or semiring R and is observed on numerical analysis; it results in the same elements of ring R. It can also be validated on LHS and RHS consideration.
LHS  (37) τ f a   = τ G  ∵ f a = G , is  group  elements = R  ∵ τ is  a  monomial,  so τ G → R , since R is  inverse  of  Group
RHS (38) f τ a   = f R  ∵ τ a = R , is  ring  elements = R  ∵ f R generates  ring  elements .
(ii)(39)fa·ha=ττ-1fa·ττ-1ha∵ττ-1g=g,g∈G=ττ-1fa·τ-1ha∵τis  a  monomial=ττ-1fa·ha∵τ-1is  monomial=ττ-1ha·fa∵Theorem2=ττ-1ha·τ-1fa=ττ-1ha·ττ-1fa=ha·fa.


### 5.2. Further Assumptions on Noncommutative Groups

Consider the assumption on polynomial version over the noncommutative group, for any randomly picked-up element ofa∈G and to define a polynomial set Pa∈G by: Pa≅fa∈τG:f(x)∈Z[x].Then, the definition on groupG over (G,·) says the following.(i)
Polynomial Symmetrical Decomposition (PSD) Problems over Noncommutative Group G. Given (a,x,y)∈G3 and m,n∈Z, find z∈Pa such that y=zm·x·zn.(ii)
Polynomial Diffie-Hellman (PDH) Problems over Noncommutative Group G. Compute xz1z2 or xz2z1 for given a,x,xz1 and xz2, where a,x∈G and z1,z2∈Pa.The PSD or PDH on cryptographic assumptions over (G,·) is intractable, and there is not any probabilistic polynomial time algorithm subsisting to solve this problem with accurateness admiration [31].Theorem 8.
The generalized extra specialp-group over the monomials is free from attacks.Proof.
Suppose the group onG with (G,·,1G) is a noncommutative group and semiring R on (R,·,1R) is semiring and its monomials are defined as Ʈ:(G,·,1G)→(R,·,1R), such that the group elements are always working at the back end, and computation is only defined on the monomials semiring elements. In this regard, the original extent of the algorithm is always hidden. The working of this prime p-group is an example of hidden subgroup or subfield problem. Hence, the theorem proves the generalized extra special p-group over the monomials is free from attacks.


### 5.3. Monomials Like Key Exchange Algorithm

The global parameters of the proposed algorithm, at dihedral order 8, for key exchange using monomials are presented as follows.Monomials Key Exchange on Noncommutative RingGlobal Public Parameters m ,  n: integers Z+ a ,  b: group elements from ring Supposing(G,·,1G) is a noncommutative group, (R,·,1R) is ring, and Ʈ:(G,·,1G)→(R,·,1R) is monomorphismUser A Key Generation (i)
f ( x ) is random polynomial chosen by A. (ii)
Selectfx∈Z(x) at random so that f(a) is well defined; that is, fƮa∈Ʈ(G); then user A takes f(a) as private key XA: XA=f(a)m·b·f(a)n.User B Key Generation (i)
h ( a ) is random polynomial chosen by B. (ii)
Selecthx∈Z(x) at random so that h(a) is well defined; that is, hƮa∈Ʈ(G); then user B takes h(a) as private key XB: XB=h(a)m·b·h(a)n.Generation of Secret Shared Session Key by User A K A = f ( a ) m · X B · f ( a ) n.Generation of Secret Shared Session Key by User B K B = h ( a ) m · X A · h ( a ) n,where our assumptions are as follows: (40)m=16,n=55,a=12341243,b=12314342and the relative monomials of group elements Ʈ:(G,·,1G)→R,·,1R are represented below, respectively. At dihedral group of order 8 there is a possibility of 8 groups; we assumed the same from G1 to G8 and its corresponding ring monomials from R1 to R8. Such group and ring elements are assigned in sequence as G1→R1, G2→R2, G3→R3, G4→R4, G5→R5, G6→R6, G7→R7, and G8→R8. These all will be used in cryptographic primitives. (41)G1=12341234,G2=12344123,G3=12343412,G4=12342341,G5=12344321,G6=12343214,G7=12342143,G8=12341432,R1=1001,R2=01-10,R3=100-1,R4=-1001,R5=0-1-10,R6=0-110,R7=-100-1,R8=100-1.In the computation process, ring elements are generated on negative modulo prime, where Lemma 9 is well distinct.Lemma 9.
The variability generation for equivalent monomials ring structured elements in the range of{-1,0,1} is negative modulo prime of (-2).Proof.
By inspection, it is observed that the negative modulo prime on(-2) results in the variations of {-1,0,1}, which well suits equivalence in the monomials like generation elements to our proposed scheme of dihedral order of 8 (where dihedral order 8 is specially a part of extra special group).
The userA chooses a random polynomial fx=4x2+x+2 and on fa≠0 the secret/private key elected for user A as(42)fa=τ-1fτa=τ-1401-102+01-10+2=τ-1-231-2mod⁡-2∵Lemma  9=τ-10-1-10→R5→G512344321.The generation of public key XA is as follows:(43)XA=fam·b·fan=1234432116.12341432.1234432155=12343214.Further, a random polynomial is chosen by user B as hx=3x4+x3+4x2+3x+4 and computes private key:(44)
h
a
=
τ
-
1
h
τ
A
=
τ
-
1
3
0
1
-
1
0
4
+
0
1
-
1
0
3
+
4
0
1
-
1
0
2
+
3
0
1
-
1
0
+
4
=
τ
-
1
3
6
2
3
mod
⁡
-
2
∵
Lemma  9
=
τ
-
1
-
1
0
0
-
1
→
R
7
→
G
7
1
2
3
4
2
1
4
3and generation of public key for user B afterwards sends it to user A:(45)XB=ham·b·han=1234214316.12341432.1234214355=12342341.Now, user A extracts the session key as(46)KA=fam·XB·fan=1234432116·12342341·1234432155=12344123and user B extracts the session key as(47)KB=ham·XA·han=1234214316·12343214·1234214355=12344123.


### 5.4. Monomials Like Encryption-Decryption Algorithm on Noncommutative Cryptography

The way for encryption and decryption module for monomials algorithm is presented at dihedral order 8, as follows on step-by-step procedure (as carried out below).Monomials based Noncommutative Algorithm for Encryption-DecryptionGlobal Public Parameters m , n: integers Z+ a , b: group elements from ring p , q: secure primes g: generator function M: message Supposing(G,·,1G) is a noncommutative group, (R,·,1R) is ring, and Ʈ:(G,·,1G)→(R,·,1R) is monomorphismUser A Key Generation (i)
f ( x ) is random polynomial chosen by A. (ii)
Selectfx∈Z(x) at random so that f(a) is well defined; that is, fƮa∈Ʈ(G); then user A takes f(a) as private key XA: XA=f(a)m·b·f(a)n.User B Key Generation (i)
h ( a ) is random polynomial chosen by B. (ii)
Selecthx∈Z(x) at random so that h(a) is well defined; that is, hƮa∈Ʈ(G); then user B takes h(a) as private keyXB: XB=h(a)m·b·h(a)n.Encryption (User B ) Ciphertext:C Decryption key:D C: sender public key D: H(ham·XA·han)⊕MDecryption (User A ) Original messageM′: H(ham·C·han)⊕MThe algorithm is presented on two random primesp and q, such that q∣p-1≠0, and generator function g is an order of q and message M. The numerical dictation is elaborating here, where global assumptions are(48)m=12,n=19,a=12343214,b=12341432,p=23,q=11,g=6,M=17.The random polynomial fx=2x5-5x2+3 is chosen by user A; the private key is as follows: (49)fa=τ-1fτa=τ-12·0-1105-5·0-1102+3=τ-18158mod⁡-2∵Lemma  9=τ-10-1-10⟹R5→G512344321.The public key generated as XA is as follows: (50)XA=fam·b·fan=1234432112·12341432·1234432119=12343214.Moving ahead, user B chose their own random polynomial hx=9x4+x3+4x2+9x+4 and computes private key as(51)
h
a
=
τ
-
1
h
τ
A
=
τ
-
1
9
0
-
1
1
0
4
+
0
-
1
1
0
3
+
4
0
-
1
1
0
2
+
9
0
-
1
1
0
+
4
=
τ
-
1
9
-
4
12
9
mod
⁡
-
2
∵
Lemma  9
=
τ
-
1
-
1
0
0
-
1
⟹
R
7
→
G
7
1
2
3
4
2
1
4
3
.The public key generation for user B as XB is as follows:(52)XB=ham·b·han=1234214312·12341432·1234214319=12342341.In the next step, we need to use a hash function, where we are exploring the same through Lemma 10.Lemma 10.
Then hash function is defined on(53)H:1234σ1σ2σ3σ4⟶g20·σ1+21·σ2+22·σ3+23·σ4mod⁡p.Proof.
By hypothesis for hashH assumed by Cao et al. 2007 [32], which is based on dihedral order of 6 for hash H:123σ1σ2σ3, in the present work, as a contribution, the authenticity of hash is preserved by applying to dihedral order of 8 (a part of extra special group) without hampering the original concepts.
Suppose userB is sender, then, according to our proposed algorithm its public key is treated as our ciphertext. The decryption key D is assigned as(54)D=Hhxm·XA·hxn⊕M=H-100-112.0-110.-100-119⊕17=H01-10⊕17⟹R2→G2g20·4+21·1+22·2+23·3mod⁡p⊕17∵Lemma  10=620·4+21·1+22·2+23·3mod⁡23⊕17=638mod⁡23⊕17=6⊕17=23.Now, the receiver A decrypts the encrypted message as:(55)=Hfxm·Cipher·fxn⊕D=H0-1-1012.-1001.0-1-1019⊕23=H01-10⊕23⟹R2→G2g20·4+21·1+22·2+23·3mod⁡p⊕23∵Lemma  10=620·4+21·1+22·2+23·3mod⁡23⊕23=638mod⁡23⊕23=6⊕23=17.


### 5.5. Security Analysis on Monomials

The security strength analysis as presented in Section4 for general structure schemes also works in a similar fashion for monomials structures like schemes. The following factors in correlation with the same play a crucial role for the cryptographic schemes generation such as the following: (i) One is generation of equivalent monomials ring elements on negative modulo prime behaving like semiring elements and these are considered as a natural generalization of noncommutative scheme in the sense that the binary addition and multiplication operations are not required to be commutative. The semigroup action suggests the exponential growth on key, which does not make any chance to find the solution. (ii) In hash generation (as Lemma 10) prime factorization of P keeps all the similar analysis results for cryptographic existence as presented in previous section. (iii) As the generation of private keys and public keys is based on monomials like structured elements, where the working scheme is initiated on monomials semiring elements for equivalent group elements, this means the original information of the group elements is totally in hidden form. The original elements are used for verification purposes only in proposed work. The generated discrete log value does not keep any significant information for adversaries. (iv) DLP provides a big conflict of interests on randomness and unpredictability generation for secret keys that also maintains a balance between key sizes and security extents. Therefore, with regard to the above-mentioned points, brute-force attacks and chosen ciphertext attacks are extremely resistant against the proposed scheme.


### 5.6. Efficiency Issues on General and Monomials Noncommutative Schemes

For noncommutative monoid,Fatb=at·b·at-, it first computes at and then its inversion at- and finally takes two multiplications in the underlying implementation. Here t represents either m or n for the polynomial function F. When t is considered to be a big digit, the computer arithmetic successively does doubling, rather than multiplying “a” for t times, so in this case the performance evaluation takes Olog2⁡t times to complete the task. In the present scenario 160-bit long t is enough to resist exhaustive attacks. The assumptions apply on length of group elements G (here proposed extra special group with one of the latest and longest group lengths) such as a,b,at,Fatb being a polynomial as a system security parameter, where the results are generated using the conventional (bit-by-bit) operations.Moreover, for the secure and efficient architecture of the group elements, it represents the following facts regarding the same:(i)
Using the above described representation of groupG element is unique. Otherwise the scheme (proposed) cannot work.(ii)
The transition from groupG elements to its equivalent ring elements finishes efficiently. Otherwise, the scheme is impractical.(iii)
Fatb does not reveal any information regarding polynomial at. Otherwise, the proposed assumptions (in algorithm) can suffer from the length based attacks.


## 5.1. Extension of Noncommutative Groups

For a noncommutative group(G,·,1G) and ring elements (R,+,·,1R), monomials generations that are possible through the use of group and ring elements can be defined as τ:(G,·,1G)→(R,·,1R). The inverse map τ-1:τ(G)→G  is also a well-defined monomial. If a,b∈G, then it is true for τa+τ(b)∈τ(G); from the same one can assign a new element c∈G as c≜τ-1τa+τ(b) which is possible. Here c is called as a quasi-sum of a and b and is denoted by c=a⊞b [31]. Similarly, for k∈R and a∈G, if k·τa∈τ(G), then one can assign a new element d∈G as d≅τ-1(k·τa) and call d as quasi-multiple of a, denoted by d=k⊠a. Then, the monomial τ in a linear sense holds the following equalities:(34)τk⊠a⊞b=τk⊠a⊞b=τd⊞b=ττ-1τd⊞τb=ττ-1ττ-1k·τa⊞τb=ττ-1k·τa⊞τb=k·τa+τb.For a,b∈G and k·τa+τb∈τG, function fx=z0+z1x+⋯+znxn∈Zx can be defined as(35)fτa=z0·1R+z1·τa+⋯zn·τan∈τG.Now, assign a new element e∈G as(36)e=τ-1fa=τ-1z0·1R+z1·τa+⋯zn·τan.If it holds to find the inverse of polynomials, call e as quasi-polynomial of f on a, denoted by e=f(a). For, arbitrary a,b∈G,k∈R and f(x)∈Z[x], a⊞b,  k⊠a, and f(a) are not always well defined. Theorem 7 is natural and general scheme, which works for noncommutative monomials.Theorem 7.
For somea∈G and some f(x),h(x)∈Z[x], if f(a) and h(a) are well defined, then (i) τfa=fτa and (ii) fa·ha=ha·f(a).Proof.
(i) Due to property of monomials on quasi-polynomial, the group element for any functionf applies with its equivalent ring elements, so in the intermediary function f results in ring or semiring R and is observed on numerical analysis; it results in the same elements of ring R. It can also be validated on LHS and RHS consideration.
LHS  (37) τ f a   = τ G  ∵ f a = G , is  group  elements = R  ∵ τ is  a  monomial,  so τ G → R , since R is  inverse  of  Group
RHS (38) f τ a   = f R  ∵ τ a = R , is  ring  elements = R  ∵ f R generates  ring  elements .
(ii)(39)fa·ha=ττ-1fa·ττ-1ha∵ττ-1g=g,g∈G=ττ-1fa·τ-1ha∵τis  a  monomial=ττ-1fa·ha∵τ-1is  monomial=ττ-1ha·fa∵Theorem2=ττ-1ha·τ-1fa=ττ-1ha·ττ-1fa=ha·fa.


## 5.2. Further Assumptions on Noncommutative Groups

Consider the assumption on polynomial version over the noncommutative group, for any randomly picked-up element ofa∈G and to define a polynomial set Pa∈G by: Pa≅fa∈τG:f(x)∈Z[x].Then, the definition on groupG over (G,·) says the following.(i)
Polynomial Symmetrical Decomposition (PSD) Problems over Noncommutative Group G. Given (a,x,y)∈G3 and m,n∈Z, find z∈Pa such that y=zm·x·zn.(ii)
Polynomial Diffie-Hellman (PDH) Problems over Noncommutative Group G. Compute xz1z2 or xz2z1 for given a,x,xz1 and xz2, where a,x∈G and z1,z2∈Pa.The PSD or PDH on cryptographic assumptions over (G,·) is intractable, and there is not any probabilistic polynomial time algorithm subsisting to solve this problem with accurateness admiration [31].Theorem 8.
The generalized extra specialp-group over the monomials is free from attacks.Proof.
Suppose the group onG with (G,·,1G) is a noncommutative group and semiring R on (R,·,1R) is semiring and its monomials are defined as Ʈ:(G,·,1G)→(R,·,1R), such that the group elements are always working at the back end, and computation is only defined on the monomials semiring elements. In this regard, the original extent of the algorithm is always hidden. The working of this prime p-group is an example of hidden subgroup or subfield problem. Hence, the theorem proves the generalized extra special p-group over the monomials is free from attacks.


## 5.3. Monomials Like Key Exchange Algorithm

The global parameters of the proposed algorithm, at dihedral order 8, for key exchange using monomials are presented as follows.Monomials Key Exchange on Noncommutative RingGlobal Public Parameters m ,  n: integers Z+ a ,  b: group elements from ring Supposing(G,·,1G) is a noncommutative group, (R,·,1R) is ring, and Ʈ:(G,·,1G)→(R,·,1R) is monomorphismUser A Key Generation (i)
f ( x ) is random polynomial chosen by A. (ii)
Selectfx∈Z(x) at random so that f(a) is well defined; that is, fƮa∈Ʈ(G); then user A takes f(a) as private key XA: XA=f(a)m·b·f(a)n.User B Key Generation (i)
h ( a ) is random polynomial chosen by B. (ii)
Selecthx∈Z(x) at random so that h(a) is well defined; that is, hƮa∈Ʈ(G); then user B takes h(a) as private key XB: XB=h(a)m·b·h(a)n.Generation of Secret Shared Session Key by User A K A = f ( a ) m · X B · f ( a ) n.Generation of Secret Shared Session Key by User B K B = h ( a ) m · X A · h ( a ) n,where our assumptions are as follows: (40)m=16,n=55,a=12341243,b=12314342and the relative monomials of group elements Ʈ:(G,·,1G)→R,·,1R are represented below, respectively. At dihedral group of order 8 there is a possibility of 8 groups; we assumed the same from G1 to G8 and its corresponding ring monomials from R1 to R8. Such group and ring elements are assigned in sequence as G1→R1, G2→R2, G3→R3, G4→R4, G5→R5, G6→R6, G7→R7, and G8→R8. These all will be used in cryptographic primitives. (41)G1=12341234,G2=12344123,G3=12343412,G4=12342341,G5=12344321,G6=12343214,G7=12342143,G8=12341432,R1=1001,R2=01-10,R3=100-1,R4=-1001,R5=0-1-10,R6=0-110,R7=-100-1,R8=100-1.In the computation process, ring elements are generated on negative modulo prime, where Lemma 9 is well distinct.Lemma 9.
The variability generation for equivalent monomials ring structured elements in the range of{-1,0,1} is negative modulo prime of (-2).Proof.
By inspection, it is observed that the negative modulo prime on(-2) results in the variations of {-1,0,1}, which well suits equivalence in the monomials like generation elements to our proposed scheme of dihedral order of 8 (where dihedral order 8 is specially a part of extra special group).
The userA chooses a random polynomial fx=4x2+x+2 and on fa≠0 the secret/private key elected for user A as(42)fa=τ-1fτa=τ-1401-102+01-10+2=τ-1-231-2mod⁡-2∵Lemma  9=τ-10-1-10→R5→G512344321.The generation of public key XA is as follows:(43)XA=fam·b·fan=1234432116.12341432.1234432155=12343214.Further, a random polynomial is chosen by user B as hx=3x4+x3+4x2+3x+4 and computes private key:(44)
h
a
=
τ
-
1
h
τ
A
=
τ
-
1
3
0
1
-
1
0
4
+
0
1
-
1
0
3
+
4
0
1
-
1
0
2
+
3
0
1
-
1
0
+
4
=
τ
-
1
3
6
2
3
mod
⁡
-
2
∵
Lemma  9
=
τ
-
1
-
1
0
0
-
1
→
R
7
→
G
7
1
2
3
4
2
1
4
3and generation of public key for user B afterwards sends it to user A:(45)XB=ham·b·han=1234214316.12341432.1234214355=12342341.Now, user A extracts the session key as(46)KA=fam·XB·fan=1234432116·12342341·1234432155=12344123and user B extracts the session key as(47)KB=ham·XA·han=1234214316·12343214·1234214355=12344123.


## 5.4. Monomials Like Encryption-Decryption Algorithm on Noncommutative Cryptography

The way for encryption and decryption module for monomials algorithm is presented at dihedral order 8, as follows on step-by-step procedure (as carried out below).Monomials based Noncommutative Algorithm for Encryption-DecryptionGlobal Public Parameters m , n: integers Z+ a , b: group elements from ring p , q: secure primes g: generator function M: message Supposing(G,·,1G) is a noncommutative group, (R,·,1R) is ring, and Ʈ:(G,·,1G)→(R,·,1R) is monomorphismUser A Key Generation (i)
f ( x ) is random polynomial chosen by A. (ii)
Selectfx∈Z(x) at random so that f(a) is well defined; that is, fƮa∈Ʈ(G); then user A takes f(a) as private key XA: XA=f(a)m·b·f(a)n.User B Key Generation (i)
h ( a ) is random polynomial chosen by B. (ii)
Selecthx∈Z(x) at random so that h(a) is well defined; that is, hƮa∈Ʈ(G); then user B takes h(a) as private keyXB: XB=h(a)m·b·h(a)n.Encryption (User B ) Ciphertext:C Decryption key:D C: sender public key D: H(ham·XA·han)⊕MDecryption (User A ) Original messageM′: H(ham·C·han)⊕MThe algorithm is presented on two random primesp and q, such that q∣p-1≠0, and generator function g is an order of q and message M. The numerical dictation is elaborating here, where global assumptions are(48)m=12,n=19,a=12343214,b=12341432,p=23,q=11,g=6,M=17.The random polynomial fx=2x5-5x2+3 is chosen by user A; the private key is as follows: (49)fa=τ-1fτa=τ-12·0-1105-5·0-1102+3=τ-18158mod⁡-2∵Lemma  9=τ-10-1-10⟹R5→G512344321.The public key generated as XA is as follows: (50)XA=fam·b·fan=1234432112·12341432·1234432119=12343214.Moving ahead, user B chose their own random polynomial hx=9x4+x3+4x2+9x+4 and computes private key as(51)
h
a
=
τ
-
1
h
τ
A
=
τ
-
1
9
0
-
1
1
0
4
+
0
-
1
1
0
3
+
4
0
-
1
1
0
2
+
9
0
-
1
1
0
+
4
=
τ
-
1
9
-
4
12
9
mod
⁡
-
2
∵
Lemma  9
=
τ
-
1
-
1
0
0
-
1
⟹
R
7
→
G
7
1
2
3
4
2
1
4
3
.The public key generation for user B as XB is as follows:(52)XB=ham·b·han=1234214312·12341432·1234214319=12342341.In the next step, we need to use a hash function, where we are exploring the same through Lemma 10.Lemma 10.
Then hash function is defined on(53)H:1234σ1σ2σ3σ4⟶g20·σ1+21·σ2+22·σ3+23·σ4mod⁡p.Proof.
By hypothesis for hashH assumed by Cao et al. 2007 [32], which is based on dihedral order of 6 for hash H:123σ1σ2σ3, in the present work, as a contribution, the authenticity of hash is preserved by applying to dihedral order of 8 (a part of extra special group) without hampering the original concepts.
Suppose userB is sender, then, according to our proposed algorithm its public key is treated as our ciphertext. The decryption key D is assigned as(54)D=Hhxm·XA·hxn⊕M=H-100-112.0-110.-100-119⊕17=H01-10⊕17⟹R2→G2g20·4+21·1+22·2+23·3mod⁡p⊕17∵Lemma  10=620·4+21·1+22·2+23·3mod⁡23⊕17=638mod⁡23⊕17=6⊕17=23.Now, the receiver A decrypts the encrypted message as:(55)=Hfxm·Cipher·fxn⊕D=H0-1-1012.-1001.0-1-1019⊕23=H01-10⊕23⟹R2→G2g20·4+21·1+22·2+23·3mod⁡p⊕23∵Lemma  10=620·4+21·1+22·2+23·3mod⁡23⊕23=638mod⁡23⊕23=6⊕23=17.


## 5.5. Security Analysis on Monomials

The security strength analysis as presented in Section4 for general structure schemes also works in a similar fashion for monomials structures like schemes. The following factors in correlation with the same play a crucial role for the cryptographic schemes generation such as the following: (i) One is generation of equivalent monomials ring elements on negative modulo prime behaving like semiring elements and these are considered as a natural generalization of noncommutative scheme in the sense that the binary addition and multiplication operations are not required to be commutative. The semigroup action suggests the exponential growth on key, which does not make any chance to find the solution. (ii) In hash generation (as Lemma 10) prime factorization of P keeps all the similar analysis results for cryptographic existence as presented in previous section. (iii) As the generation of private keys and public keys is based on monomials like structured elements, where the working scheme is initiated on monomials semiring elements for equivalent group elements, this means the original information of the group elements is totally in hidden form. The original elements are used for verification purposes only in proposed work. The generated discrete log value does not keep any significant information for adversaries. (iv) DLP provides a big conflict of interests on randomness and unpredictability generation for secret keys that also maintains a balance between key sizes and security extents. Therefore, with regard to the above-mentioned points, brute-force attacks and chosen ciphertext attacks are extremely resistant against the proposed scheme.


## 5.6. Efficiency Issues on General and Monomials Noncommutative Schemes

For noncommutative monoid,Fatb=at·b·at-, it first computes at and then its inversion at- and finally takes two multiplications in the underlying implementation. Here t represents either m or n for the polynomial function F. When t is considered to be a big digit, the computer arithmetic successively does doubling, rather than multiplying “a” for t times, so in this case the performance evaluation takes Olog2⁡t times to complete the task. In the present scenario 160-bit long t is enough to resist exhaustive attacks. The assumptions apply on length of group elements G (here proposed extra special group with one of the latest and longest group lengths) such as a,b,at,Fatb being a polynomial as a system security parameter, where the results are generated using the conventional (bit-by-bit) operations.Moreover, for the secure and efficient architecture of the group elements, it represents the following facts regarding the same:(i)
Using the above described representation of groupG element is unique. Otherwise the scheme (proposed) cannot work.(ii)
The transition from groupG elements to its equivalent ring elements finishes efficiently. Otherwise, the scheme is impractical.(iii)
Fatb does not reveal any information regarding polynomial at. Otherwise, the proposed assumptions (in algorithm) can suffer from the length based attacks.


## 6. Basic Length Based Attacks

It is a heuristic procedure for finding the recipient’s secret keys and is representing one of the procedures for recovering each of the conjugating factors as a major goal. The successful procedure results in actual conjugator as a product of group elements. The length based attack [45, 46] on dihedral order 6 is presented in [38]. Our proposed approach is based on dihedral order 8, that is, k=4; a number of elements play an enormous role of generation of a subset of 8 group elements defined as SG={g1±1,g2±1,g3±1,g4±1}. We consider a random input series y=g1g2-1g3g4-1, for length n=4. On choosing input sequence, the operation performs on 2k-ary tree. It begins with an empty word e and searches for one of the child nodes of 8 group elements, with successful generation of 8 individual groups. For each element presented in input sequence is traced on successful generation, this procedure repeats until some n input of yn length chosen for y=y1y2⋯yn satisfies, as shown in Figure 5. This is based on the nth level that contains (2k)n leaf-nodes elements. Each leaf-node is likely to be a potential value for y. The fact behind solving the CDP is easy but the fact to solve the CSP is unavailable, so it can be considered to be secure against the brute-force search.Figure 5
Process of generatingy=g1g2-1g3g4-1.For example, during the process of searching, if there are two children-nodesP and Q with equal length and if the algorithm wrongly predicts any node in one of them, it makes the algorithm fall into an exponential search in the worst case for negligible solution. On average, 8 candidates (in dihedral order 8) nodes in each level represent the time complexity of attack algorithm on O(82n) for all n word per each level length, on the success or failure attempts.The process of attack is reversed, for instance, searching for the2k-ary tree. This means attack is a reversal procedure, which works on successful cryptanalysis; at first level it should satisfy 64 elements from 8 groups; similarly for the second level, it should again satisfy the same, and it should repeat to word length input. An example is dictated on the target nodes represented as a dark node that forms the optimal search path (as shown in Figure 6). The best result of an attack algorithm is to find this path which indicates decomposition of y.Figure 6
Process of decomposingy=g1g2-1g3g4-1.


### 6.1. Analysis on Length Based Attacks

Dihedral order of 8 uses 4 (four) elements to form one group of 8 elements each (a total of 8 groups' formation with a total of 64 elements), so adversaries (attackers) try to obtain the input sequence on level by level; at the first level an adversary needs to satisfy 64 corresponding elements and again for the second level needs to satisfy the next 64 corresponding elements and it will continue to repeat until length does not reach to maximum length. So, one can represent its complexity in the worst case beingO(82n). Here Conjugacy Decisional Problem (CDP) is easy to apply according to algorithm for the same, but Conjugacy Search Problem (CSP) does not work correctly. The CDP and CSP are the two advantageous approaches for making the exponential impulsiveness and arbitrariness for nonnegligible solution. Here no such Conjugacy Search Problem exists to solve such larger scaled problems. Therefore, in the concluding remarks it can be mention that our proposed problem is making a big impact with regard to cryptographic schemes.Further, the performance may also improve using the following artillery variations by using memory uses, repetitions avoidance, look-ahead, alternative solutions, and automorphism attacks implementation into the algorithms. A brief idea is presented below.Memory Uses. To compute the 2kn-child nodes from the N subtrees, the width of search memory increases which chooses the shortest N ones as the roots of the subtrees for the next computations. As a result, the search width is enhanced from 1 to N. According to principle the algorithm becomes efficient, but it is still exponential. For example, if in any loop the right node is not included in the M candidates, then the algorithm may degenerate to exponential. If a random input yj is chosen from an adversary that multiplies for a word (or key) length wj, the necessary and sufficient condition may be incorporation on lyjwj+1<l(wj+1), where wj+1=yj+1 to yn, and yj left multiplying to wj+1 forms its length reduction. So, it can be considered, as corrected node is not included in the N candidates list, because length of child-node increases, which happens incorrectly, and therefore perceptibly on successful attacks (rate) will decrease.Repetitions Avoidance. Avoiding repetition is an improvement usually seen in research. The algorithm maintains a hash table of recorded values of visited nodes, and the chance may be that the two nodes in the search tree have the same value. If the same node value appears again, then from the candidate list node value will be cancelled for same. So, to improve the algorithm, avoiding repetition method used in list not only improves efficiency but also prevents the algorithm from trapping into a closed loop.Look-Ahead. This increases depth of searching. The original algorithm searches one level each time, while the method searches n levels each time; here is a possible way to make a practical choice to avoid attacks. For better algorithm this is one of the promising optional problems; the cost of traversing time at n-level subtree is (2k)n. The algorithm increases in length of multiple right nodes for n-steps; the look-ahead problem never finds the right node. Thus, the algorithm again falls in exponential search.Alternative Solutions. The alternative solution is a specific one, generated on the monomials like cryptographic schemes. This type of improvement is much more efficient, and in addition it does not change the search complexity. It helps to infinitely decrease the search time to find the right nodes. But one of the basic conditions involved with this algorithm is that search direction should be correct. A large possibility is available to make the algorithm fall into an exponential search, if once it enters into a wrong subtree.Automorphism Attacks. Under the parameters selected, the random automorphism functions are extremely allied to each other on random polynomial chosen for participants, so the generation of these values is considered to be negligible.


## 6.1. Analysis on Length Based Attacks

Dihedral order of 8 uses 4 (four) elements to form one group of 8 elements each (a total of 8 groups' formation with a total of 64 elements), so adversaries (attackers) try to obtain the input sequence on level by level; at the first level an adversary needs to satisfy 64 corresponding elements and again for the second level needs to satisfy the next 64 corresponding elements and it will continue to repeat until length does not reach to maximum length. So, one can represent its complexity in the worst case beingO(82n). Here Conjugacy Decisional Problem (CDP) is easy to apply according to algorithm for the same, but Conjugacy Search Problem (CSP) does not work correctly. The CDP and CSP are the two advantageous approaches for making the exponential impulsiveness and arbitrariness for nonnegligible solution. Here no such Conjugacy Search Problem exists to solve such larger scaled problems. Therefore, in the concluding remarks it can be mention that our proposed problem is making a big impact with regard to cryptographic schemes.Further, the performance may also improve using the following artillery variations by using memory uses, repetitions avoidance, look-ahead, alternative solutions, and automorphism attacks implementation into the algorithms. A brief idea is presented below.Memory Uses. To compute the 2kn-child nodes from the N subtrees, the width of search memory increases which chooses the shortest N ones as the roots of the subtrees for the next computations. As a result, the search width is enhanced from 1 to N. According to principle the algorithm becomes efficient, but it is still exponential. For example, if in any loop the right node is not included in the M candidates, then the algorithm may degenerate to exponential. If a random input yj is chosen from an adversary that multiplies for a word (or key) length wj, the necessary and sufficient condition may be incorporation on lyjwj+1<l(wj+1), where wj+1=yj+1 to yn, and yj left multiplying to wj+1 forms its length reduction. So, it can be considered, as corrected node is not included in the N candidates list, because length of child-node increases, which happens incorrectly, and therefore perceptibly on successful attacks (rate) will decrease.Repetitions Avoidance. Avoiding repetition is an improvement usually seen in research. The algorithm maintains a hash table of recorded values of visited nodes, and the chance may be that the two nodes in the search tree have the same value. If the same node value appears again, then from the candidate list node value will be cancelled for same. So, to improve the algorithm, avoiding repetition method used in list not only improves efficiency but also prevents the algorithm from trapping into a closed loop.Look-Ahead. This increases depth of searching. The original algorithm searches one level each time, while the method searches n levels each time; here is a possible way to make a practical choice to avoid attacks. For better algorithm this is one of the promising optional problems; the cost of traversing time at n-level subtree is (2k)n. The algorithm increases in length of multiple right nodes for n-steps; the look-ahead problem never finds the right node. Thus, the algorithm again falls in exponential search.Alternative Solutions. The alternative solution is a specific one, generated on the monomials like cryptographic schemes. This type of improvement is much more efficient, and in addition it does not change the search complexity. It helps to infinitely decrease the search time to find the right nodes. But one of the basic conditions involved with this algorithm is that search direction should be correct. A large possibility is available to make the algorithm fall into an exponential search, if once it enters into a wrong subtree.Automorphism Attacks. Under the parameters selected, the random automorphism functions are extremely allied to each other on random polynomial chosen for participants, so the generation of these values is considered to be negligible.


## 7. Conclusion

In the manuscript, the noncommutative cryptographic scheme on the extra special group for the multidisciplinary perspective has been considered. Regarding this the minimum group of the dihedral changes fromD3 to D4 enhances the search space, and two additional group benefits of Heisenberg and quaternion groups make the proposal stronger than all the previously predicted groups. The scheme is processed at the noncommutative platform for the prospective advantages of typical sparse matrices for general structures like group, ring, or semiring elements. The proposed security assumptions are based on the hidden subgroup or subfields problem (HSP) on the random polynomials chosen for end users, and monomials generation is presented where Conjugacy Search Problem (CSP) is likely to be intractable. For the adversary, the attacks like length based, brute-force, automorphism, are being negligible.



---

*Source: 9036382-2017-01-12.xml*