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.
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 of that consists of group, ring, semiring, or some algebraic structural elements, in which two group elements and of such that 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 . 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 is called polycyclic series with cyclic aspects; that is, is recurring for .(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 .(viii)In 2005, Mahalanobis [30] did not discriminate the 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 lying in the center of 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 is called left self-distributive for all elements , .(ix)To extract from a given and , 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 via the mapping .(x)Moreover, if the Conjugacy Search Problem (CSP) over 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 -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], -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 polynomial -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. Section 3 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. -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 ring is proposed by Cao et al. in 2007 [32]. The developed scheme is based on modulo prime integers, named -modular method. The derived -modular structure on ring is , and this structure applies to positive and/or negative on noncommutative ring elements, where is undetermined. Also, group and semiring are comprehensively applicable on -modular assumptions.
2.1.1. Noncommutative Rings on -Modular Method
The integral coefficient polynomial on additive noncommutative characterization is defined on ring and for multiplicative noncommutative ; the scalar multiplication over is well defined for and :Further, for , Finally, if it is to be defined on scalar , it is likely to be .
Proposition 1. In general, scalar multiplication on noncommutative property follows , when . Recall a polynomial with positive integral coefficient , for all . To assign the component as an element , then attain a precise element in ring asIn addition, suppose to be undetermined; then polynomial over is univariable polynomial lying on . The univariable polynomial over as a whole set is denoted as , and it is defined as follows for the respective functions on two different ring elements:Again, if , thenand according to the property of distributive law it generalizes the above equation aswhere,
Theorem 2. , and , where signify for all elements.
Proof. Here ring is a subset of ring applying to polynomial functions of and , for all positive integers of . 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: if and belong to ring element, then is also in ring.(ii)Associative law of multiplication: for all .(iii)Distributive laws: or for all .(iv)Commutative multiplication: for .(v)Multiplicative identity: for all .(vi)No zero divisors: for all and in and , then, either or 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 and , to determine a random to produce the value of other group elements, such that or to produce the same using the Conjugacy multiplicative inverse as .(ii)Conjugacy Search Problem (CSP). It is, for the two group elements of and in a group , to find whether there exists in , such that or Conjugacy multiplicative inverse .If no algorithm exists to solve the CSP, by applying on one group of elements to determine the other group of elements, that is, , then this is considered to be a one-way function. In the contemporary computation, both problems on general noncommutative group 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 in -Modular Method
The polynomials used in -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 be a noncommutative monomial for an element , the other group element being , such that ; then it assumed that group is invertible, and call an inverse of . Not all elements in are invertible. If the inverse of exists, it is unique and denoted by . In monomials, the positive power of group element for integer is described as follows: for . If is the inverse of , one can also define the negative power of by setting for . The Conjugacy Search Problem can be extended to monomials , for and , is a conjugate to , and call as conjugator of the pair .
Definition 3 (Conjugacy Search Problem (CSP)). Let be a noncommutative monomial; the two elements so that for some unknown element , and the objective of the CSP in is to find such that .
Definition 4 (left self-distributive system). Suppose that is a nonempty set, is a well-defined function, and let one denote by . If the rewritten formula holds then call as a left self-distributive system (LD).
Theorem 5. Let be noncommutative monomial, the function on conjugate follows as and is known by LD system, also abbreviated as Conj-LD.
Proof. According to Definition 4, the term LD is an analogical observation from as a binary operation in ; then this is observed as , 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: . Here, it is satisfying the function on as an LD system. Thus, Theorem 5 proof is based on these observations.
Proposition 6. Let be a Conj-LD system defined over a noncommutative monomial ; then for the given and , the following proposals are well-defined, according to [38]:(i).(ii).(iii).
Proof of (i). Since , so .
Proof of (ii). .
Proof of (iii). .
2.4. Symmetry and Generalization Assumptions over Noncommutative Groups
To explain the symmetries, the generalizations on the noncommutative cryptography are the following problems on group :(i)Symmetrical Decomposition Problem (SDP). Given and , find such that .(ii)Generalized Symmetrical Decomposition Problem (GSDP). Given , , and , find such that .The GSDP is evidently a sort of constrained SDP, and if subset is large enough, then membership information in general does not help one to extract from . 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 .
2.5. Computational Diffie-Hellman (CDH) Problem over Noncommutative Group
The CDH problem with respect to its subset on noncommutative group determines or for known , and , where . The commutative law keeps an extraction property from , if it holds the relation for . It is noticeable that DLP in GSDP over is tractable. But the converse of the same is not true. At present, no clue is available to resolve this problem without extracting (or ) from and (or ). Then, the CDH hypothesis over says that problem over 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 prime to the power , that is, , 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 ( 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 or . The reason is clearly that any prime starts from , and the remaining primes only belong to odd numbers.
At . The extra special group, for odd, is given below:(i)The group of triangular matrices is over the field with elements, with 1 on the diagonal. The group is exponent for odd. These are known by Heisenberg group elements.(ii)There is the semidirect product of a cyclic group of order by a cyclic group of order acting nontrivially on it.Again, if is a positive integer, then for odd the following is given.(i)The central product of extra special group of order , all of exponent : this extra special group also has exponent .(ii)The central product of order : at least one of the exponents should be .Now, consider prime ; the minimum order starts from , so extra special group order is described as follows:(i)The dihedral group in order : this group has elements of order .(ii)The quaternion group of order : it has six elements of order , for example,Again, if we consider 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 of upper triangular matrices contains the several representations in terms of functional spaces whose center acts nontrivially on it. A matrix multiplication is in the formwhere elements of 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 -dimensional systems is more general in this regard. The products of two Heisenberg matrices in the three-dimensional case are given byThe Heisenberg neutral element of group is the identity matrix. The discrete Heisenberg group generator is the nonabelian group of ring elements on the integers :and relations , , and , where is the generator with the center. A polynomial growth rate of order 3 using Bass’s theorem is used to generate any element through The behavior of the Heisenberg group to modulo odd prime over a finite field is called extra special group of exponent .
3.1.1. Security Strength of Heisenberg Group
The Heisenberg group on public key cryptography follows polycyclic behaviors if and only if a subseries for a group (where denotes variations of in cyclic form). Each positive integer of the th 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 by (or also called ) [42]. The subgroups of this (dihedral order group ) 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 . 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.
One more “” (reflection) operation is used relative to its corresponding above four rotations. Further, to define the composition movement such as “,” first do the operation for “” and after that apply “” as shown. For the remaining two of and 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.
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 Figure 3.
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 Table 1.
Finally, we are correlating the same concept from mathematics. Here, the composition of eight different but interrelated operations for 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 to for rotations/movements and reflections in , as a resultant. A detailed cryptographic application scheme is considered in Sections 5.3 and 5.4.
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 or and is given by the group representation , where is the identity element and commutes with the same. This is the same order as dihedral order , 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 .
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 on , based on , where and are two secure primes. This is intractable, in view of the fact that , from with no significant factors of [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 Sections 3.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 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 and user , 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 Ring
Global Public Parameters : integers : ring elements
User Key Generation(i)Select private random polynomial: .(ii)If , then is considered as private key.(iii)Generation of public key : .
User Key Generation(i)Select private random polynomial: .(ii)If , then is considered as private key.(iii)Generation of public key : .
Generation of Secret Key by User .
Generation of Secret Key by User .The global parameters areUser chose their random polynomial . Evaluate the polynomial ; if then the polynomial will be considered as a private key for user . The ’s private key is as follows:Now, the generation of public key by user is as follows:At the other end user chose their own random polynomial . Further, evaluate the polynomial , and if then this polynomial value will be considered as private key:and the generation of public key for user is as follows: Finally, the session key is extracted by the user as :and the session key is extracted from user as :
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 areFor user , a random polynomial is chosen: . Evaluate the polynomial on , and if then polynomial value is considered as a private key for user :The generation of public key by user is as follows:At the other end user chose their own random polynomial . Evaluating the polynomial , the private key is as follows:and the generation of public key for user is as follows:Finally, the session key extracted by the user as is as follows:and the session key extracted by user as is as follows:
4.3. Encryption-Decryption Algorithm on Heisenberg Group
The encryption-decryption procedure on Heisenberg group is offered as follows.
Encryption-Decryption Algorithm on Noncommutative Ring
Global Public Parameters : integers : ring elements : message : hashed message
User Key Generation(i)Select private random polynomial: .(ii)If , then is considered as private key.(iii)Generation of public key : .
User Key Generation(i)Select private random polynomial: .(ii)If , then is considered as private key.(iii)Generation of public key : .
Encryption (by Sender ) : ciphertext : decryption key ,
Decryption The approach of noncommutative cryptography works like the general case, where our assumptions are asUser randomly chose a random polynomial ; then is considered to be private key:The generation of public key is as follows:Moving onwards, user randomly chose their own random polynomial and computes private key if :and the public key generated for user is as follows: The sender of the public key is treated as ciphertext (in our case user is sender): The original message is as follows:
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 . The proposed procedure stands on hidden prime factorization of ( 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)Since is based on two prime factors and factorization of 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 (except and ) 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 or , 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 integer .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 or to the power of and 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 (standard length bits) 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 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 , it is computationally infeasible to find such that , (iv) for any pair it is computationally infeasible to find is a strong collision resistant property, and (v) for any block , it is computationally infeasible to find is a weak collision resistant property.
5. Monomials Based Cryptography Using Noncommutative Groups and Semirings
The polynomial used in -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 and ring elements , monomials generations that are possible through the use of group and ring elements can be defined as . The inverse map is also a well-defined monomial. If , then it is true for ; from the same one can assign a new element as which is possible. Here is called as a quasi-sum of and and is denoted by [31]. Similarly, for and , if , then one can assign a new element as ) and call as quasi-multiple of , denoted by . Then, the monomial in a linear sense holds the following equalities:For and , function can be defined asNow, assign a new element asIf it holds to find the inverse of polynomials, call as quasi-polynomial of on , denoted by . For, arbitrary and , , , and are not always well defined. Theorem 7 is natural and general scheme, which works for noncommutative monomials.
Theorem 7. For some and some , if and are well defined, then (i) and (ii) .
Proof. (i) Due to property of monomials on quasi-polynomial, the group element for any function applies with its equivalent ring elements, so in the intermediary function results in ring or semiring and is observed on numerical analysis; it results in the same elements of ring . It can also be validated on LHS and RHS consideration.
LHSRHS(ii)
5.2. Further Assumptions on Noncommutative Groups
Consider the assumption on polynomial version over the noncommutative group, for any randomly picked-up element of and to define a polynomial set by: .
Then, the definition on group over says the following.(i)Polynomial Symmetrical Decomposition (PSD) Problems over Noncommutative Group G. Given and , find such that .(ii)Polynomial Diffie-Hellman (PDH) Problems over Noncommutative Group G. Compute or for given and , where and .The PSD or PDH on cryptographic assumptions over 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 special -group over the monomials is free from attacks.
Proof. Suppose the group on with is a noncommutative group and semiring on is semiring and its monomials are defined as , 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 -group is an example of hidden subgroup or subfield problem. Hence, the theorem proves the generalized extra special -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 Ring
Global Public Parameters : integers : group elements from ring Supposing is a noncommutative group, is ring, and is monomorphism
User Key Generation(i) is random polynomial chosen by .(ii)Select at random so that is well defined; that is, ; then user takes as private key : .
User Key Generation(i) is random polynomial chosen by .(ii)Select at random so that is well defined; that is, ; then user takes as private key : .
Generation of Secret Shared Session Key by User .
Generation of Secret Shared Session Key by User ,where our assumptions are as follows: and the relative monomials of group elements are represented below, respectively. At dihedral group of order 8 there is a possibility of 8 groups; we assumed the same from to and its corresponding ring monomials from to . Such group and ring elements are assigned in sequence as , , , , , , , and . These all will be used in cryptographic primitives. 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 is negative modulo prime of .
Proof. By inspection, it is observed that the negative modulo prime on results in the variations of , 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 user chooses a random polynomial and on the secret/private key elected for user asThe generation of public key is as follows:Further, a random polynomial is chosen by user as and computes private key:and generation of public key for user afterwards sends it to user :Now, user extracts the session key asand user extracts the session key as
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-Decryption
Global Public Parameters : integers : group elements from ring : secure primes : generator function : message Supposing is a noncommutative group, is ring, and is monomorphism
User Key Generation(i) is random polynomial chosen by .(ii)Select at random so that is well defined; that is, ; then user takes as private key : .
User Key Generation(i) is random polynomial chosen by .(ii)Select at random so that is well defined; that is, ; then user takes as private key: .
Encryption (User ) Ciphertext: Decryption key: : sender public key :
Decryption (User ) Original message :
The algorithm is presented on two random primes and , such that , and generator function is an order of and message . The numerical dictation is elaborating here, where global assumptions areThe random polynomial is chosen by user ; the private key is as follows: The public key generated as is as follows: Moving ahead, user chose their own random polynomial and computes private key asThe public key generation for user as is as follows: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
Proof. By hypothesis for hash assumed by Cao et al. 2007 [32], which is based on dihedral order of 6 for hash , 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 user is sender, then, according to our proposed algorithm its public key is treated as our ciphertext. The decryption key is assigned asNow, the receiver decrypts the encrypted message as:
5.5. Security Analysis on Monomials
The security strength analysis as presented in Section 4 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 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, , it first computes and then its inversion and finally takes two multiplications in the underlying implementation. Here represents either or for the polynomial function . When is considered to be a big digit, the computer arithmetic successively does doubling, rather than multiplying “” for times, so in this case the performance evaluation takes times to complete the task. In the present scenario 160-bit long is enough to resist exhaustive attacks. The assumptions apply on length of group elements (here proposed extra special group with one of the latest and longest group lengths) such as 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 group element is unique. Otherwise the scheme (proposed) cannot work.(ii)The transition from group elements to its equivalent ring elements finishes efficiently. Otherwise, the scheme is impractical.(iii) does not reveal any information regarding polynomial . 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, ; a number of elements play an enormous role of generation of a subset of group elements defined as . We consider a random input series , for length . On choosing input sequence, the operation performs on -ary tree. It begins with an empty word 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 input of length chosen for satisfies, as shown in Figure 5. This is based on the level that contains leaf-nodes elements. Each leaf-node is likely to be a potential value for . 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.
For example, during the process of searching, if there are two children-nodes and 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 for all word per each level length, on the success or failure attempts.
The process of attack is reversed, for instance, searching for the -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 .
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 being . 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 -child nodes from the subtrees, the width of search memory increases which chooses the shortest ones as the roots of the subtrees for the next computations. As a result, the search width is enhanced from to . 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 candidates, then the algorithm may degenerate to exponential. If a random input is chosen from an adversary that multiplies for a word (or key) length , the necessary and sufficient condition may be incorporation on , where to , and left multiplying to forms its length reduction. So, it can be considered, as corrected node is not included in the 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 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 -level subtree is . The algorithm increases in length of multiple right nodes for -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 from to 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.
Competing Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.