Non-commutative cryptography is the area ofcryptology where thecryptographic primitives, methods and systems are based onalgebraic structures likesemigroups,groups andrings which arenon-commutative. One of the earliest applications of a non-commutative algebraic structure for cryptographic purposes was the use ofbraid groups to develop cryptographic protocols. Later several other non-commutative structures likeThompson groups,polycyclic groups,Grigorchuk groups, andmatrix groups have been identified as potential candidates for cryptographic applications. In contrast to non-commutative cryptography, the currently widely usedpublic-key cryptosystems likeRSA cryptosystem,Diffie–Hellman key exchange andelliptic curve cryptography are based on number theory and hence depend on commutative algebraic structures.

Non-commutative cryptographic protocols have been developed for solving various cryptographic problems likekey exchange,encryption-decryption, andauthentication. These protocols are very similar to the corresponding protocols in the commutative case.

In these protocols it would be assumed thatG is anon-abelian group. Ifw anda are elements ofG the notationw^a would indicate the elementa⁻¹wa.

The following protocol due to Ko, Lee, et al., establishes a commonsecret keyK forAlice and Bob.

1. An elementw ofG is published.
2. TwosubgroupsA andB ofG such thatab =ba for alla inA andb inB are published.
3. Alice chooses an elementa fromA and sendsw^a to Bob. Alice keepsa private.
4. Bob chooses an elementb fromB and sendsw^b to Alice. Bob keepsb private.
5. Alice computesK = (w^b)^a =w^ba.
6. Bob computesK' = (w^a)^b=w^ab.
7. Sinceab =ba,K =K'. Alice and Bob share the common secret keyK.

This a key exchange protocol using a non-abelian groupG. It is significant because it does not require two commuting subgroupsA andB ofG as in the case of the protocol due to Ko, Lee, et al.

1. Elementsa₁,a₂, . . . ,a_k,b₁,b₂, . . . ,b_m fromG are selected and published.
2. Alice picks a privatex inG as aword ina₁,a₂, . . . ,a_k; that is,x =x(a₁,a₂, . . . ,a_k ).
3. Alice sendsb₁^x,b₂^x, . . . ,b_m^x to Bob.
4. Bob picks a privatey inG as aword inb₁,b₂, . . . ,b_m; that isy =y (b₁,b₂, . . . ,b_m ).
5. Bob sendsa₁^y,a₂^y, . . . ,a_k^y to Alice.
6. Alice and Bob share the common secret keyK =x⁻¹y⁻¹xy.
7. Alice computesx (a₁^y,a₂^y, . . . ,a_k^y ) =y⁻¹xy. Pre-multiplying it withx⁻¹, Alice getsK.
8. Bob computesy (b₁^x,b₂^x, . . . ,b_m^x) =x⁻¹yx. Pre-multiplying it withy⁻¹ and then taking the inverse, Bob getsK.

In the original formulation of this protocol the group used was the group ofinvertible matrices over afinite field.

1. LetG be a public non-abelianfinite group.
2. Leta,b be public elements ofG such thatab ≠ba. Let the orders ofa andb beN andM respectively.
3. Alice chooses two random numbersn <N andm <M and sendsu =a^mbⁿ to Bob.
4. Bob picks two random numbersr <N ands <M and sendsv =a^rb^s to Alice.
5. The common key shared by Alice and Bob isK =a^{m +r}b^{n +s}.
6. Alice computes the key byK = a^mvbⁿ.
7. Bob computes the key byK =a^rub^s.

This protocol describes how toencrypt a secret message and thendecrypt using a non-commutative group. Let Alice want to send a secret messagem to Bob.

1. LetG be a non-commutative group. LetA andB be public subgroups ofG such thatab =ba for alla inA andb inB.
2. An elementx fromG is chosen and published.
3. Bob chooses a secret keyb fromA and publishesz =x^b as his public key.
4. Alice chooses a randomr fromB and computest =z^r.
5. The encrypted message isC = (x^r,H(t)${\displaystyle \oplus }$m), whereH is somehash function and${\displaystyle \oplus }$ denotes theXOR operation. Alice sendsC to Bob.
6. To decryptC, Bob recoverst as follows: (x^r)^b =x^rb =x^br = (x^b)^r =z^r =t. The plain text message send by Alice isP = (H(t)${\displaystyle \oplus }$m )${\displaystyle \oplus }$H(t) =m.

Let Bob want to check whether the sender of a message is really Alice.

1. LetG be a non-commutative group and letA andB be subgroups ofG such thatab =ba for alla inA andb inB.
2. An elementw fromG is selected and published.
3. Alice chooses a privates fromA and publishes the pair (w,t ) wheret =w^s.
4. Bob chooses anr fromB and sends a challengew′ =w^r to Alice.
5. Alice sends the responsew′′ = (w′)^s to Bob.
6. Bob checks ifw′′ =t^r. If this true, then the identity of Alice is established.

The basis for the security and strength of the various protocols presented above is the difficulty of the following two problems:

• Theconjugacy decision problem (also called theconjugacy problem): Given two elementsu andv in a groupG determine whether there exists an elementx inG such thatv =u^x, that is, such thatv =x⁻¹ux.
• Theconjugacy search problem: Given two elementsu andv in a groupG find an elementx inG such thatv =u^x, that is, such thatv =x⁻¹ux.

If no algorithm is known to solve the conjugacy search problem, then the functionx →u^x can be considered as aone-way function.

A non-commutative group that is used in a particular cryptographic protocol is called the platform group of that protocol. Only groups having certain properties can be used as the platform groups for the implementation of non-commutative cryptographic protocols. LetG be a group suggested as a platform group for a certain non-commutative cryptographic system. The following is a list of the properties expected ofG.

1. The groupG must be well-known and well-studied.
2. Theword problem inG should have a fast solution by a deterministic algorithm. There should be an efficiently computable "normal form" for elements ofG.
3. It should be impossible to recover the factorsx andy from the productxy inG.
4. The number of elements of lengthn inG should grow faster than any polynomial inn. (Here "lengthn" is the length of a word representing a group element.)

Letn be a positive integer. The braid groupB_n is a group generated byx₁,x₂, . . . ,x_n−1 having the following presentation:

${\displaystyle B_n=⟨x_1,x_2,\dots ,x_{n-1}|x_i{x}_j=x_j{x}_i\text{ if }|i-j|>1\text{ and }{x}_i{x}_j{x}_i=x_j{x}_i{x}_j\text{ if }|i-j|=1⟩}$

Thompson's group is an infinite groupF having the following infinite presentation:

LetT denote the infiniterootedbinary tree. The setV of vertices is the set of all finite binary sequences. LetA(T) denote the set of all automorphisms ofT. (An automorphism ofT permutes vertices preserving connectedness.) The Grigorchuk's group Γ is the subgroup ofA(T) generated by the automorphismsa,b,c,d defined as follows:

• ${\displaystyle a(b_1,b_2,\dots ,b_n)=(1-b_1,b_2,\dots ,b_n)}$
• 
• 
• 

An Artin groupA(Γ) is a group with the following presentation:

where${\displaystyle {\mu }_{ij}=a_i{a}_j{a}_i\dots }$ (${\displaystyle m_{ij}}$ factors) and${\displaystyle m_{ij}=m_{ji}}$.

LetF be a finite field. Groups of matrices overF have been used as the platform groups of certain non-commutative cryptographic protocols.

^[1]

• Group-based cryptography

• Public-key cryptography