# Non-commutative cryptography

**Non-commutative cryptography** is the area of cryptology where the cryptographic primitives, methods and systems are based on algebraic structures like semigroups, groups and rings which are non-commutative. One of the earliest applications of a non-commutative algebraic structure for cryptographic purposes was the use of braid groups to develop cryptographic protocols. Later several other non-commutative structures like Thompson groups, polycyclic groups, Grigorchuk groups, and matrix groups have been identified as potential candidates for cryptographic applications. In contrast to non-commutative cryptography, the currently widely used public-key cryptosystems like RSA cryptosystem, Diffie–Hellman key exchange and elliptic 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 like key exchange, encryption-decryption, and authentication. These protocols are very similar to the corresponding protocols in the commutative case.

## Some non-commutative cryptographic protocols[edit]

In these protocols it would be assumed that *G* is a non-abelian group. If *w* and *a* are elements of *G* the notation *w*^{a} would indicate the element *a ^{−1}wa*.

### Protocols for key exchange[edit]

#### Protocol due to Ko, Lee, et al.[edit]

The following protocol due to Ko, Lee, et al., establishes a common secret key *K* for Alice and Bob.

- An element
*w*of*G*is published. - Two subgroups
*A*and*B*of*G*such that*ab*=*ba*for all*a*in*A*and*b*in*B*are published. - Alice chooses an element
*a*from*A*and sends*w*to Bob. Alice keeps^{a}*a*private. - Bob chooses an element
*b*from*B*and sends*w*to Alice. Bob keeps^{b}*b*private. - Alice computes
*K*= (*w*^{b})^{a}=*w*^{ba}. - Bob computes
*K'*= (*w*^{a})^{b}=*w*^{ab}. - Since
*ab*=*ba*,*K*=*K'*. Alice and Bob share the common secret key*K*.

#### Anshel-Anshel-Goldfeld protocol[edit]

This a key exchange protocol using a non-abelian group *G*. It is significant because it does not require two commuting subgroups *A* and *B* of *G* as in the case of the protocol due to Ko, Lee, et al.

- Elements
*a*_{1},*a*_{2}, . . . ,*a*_{k},*b*_{1},*b*_{2}, . . . ,*b*_{m}from*G*are selected and published. - Alice picks a private
*x*in*G*as a word in*a*_{1},*a*_{2}, . . . ,*a*_{k}; that is,*x*=*x*(*a*_{1},*a*_{2}, . . . ,*a*_{k}). - Alice sends
*b*_{1}^{x},*b*_{2}^{x}, . . . ,*b*_{m}^{x}to Bob. - Bob picks a private
*y*in*G*as a word in*b*_{1},*b*_{2}, . . . ,*b*_{m}; that is*y*=*y*(*b*_{1},*b*_{2}, . . . ,*b*_{m}). - Bob sends
*a*_{1}^{y},*a*_{2}^{y}, . . . ,*a*_{k}^{y}to Alice. - Alice and Bob share the common secret key
*K*=*x*^{−1}*y*^{−1}*xy*. - Alice computes
*x*(*a*_{1}^{y},*a*_{2}^{y}, . . . ,*a*_{k}^{y}) =*y*^{−1}*xy*. Pre-multiplying it with*x*^{−1}, Alice gets*K*. - Bob computes
*y*(*b*_{1}^{x},*b*_{2}^{x}, . . . ,*b*_{m}^{x}) =*x*^{−1}*yx*. Pre-multiplying it with*y*^{−1}and then taking the inverse, Bob gets*K*.

#### Stickel's key exchange protocol[edit]

In the original formulation of this protocol the group used was the group of invertible matrices over a finite field.

- Let
*G*be a public non-abelian finite group. - Let
*a*,*b*be public elements of*G*such that*ab*≠*ba*. Let the orders of*a*and*b*be*N*and*M*respectively. - Alice chooses two random numbers
*n*<*N*and*m*<*M*and sends*u*=*a*^{m}*b*^{n}to Bob. - Bob picks two random numbers
*r*<*N*and*s*<*M*and sends*v*=*a*^{r}*b*^{s}to Alice. - The common key shared by Alice and Bob is
*K*=*a*^{m + r}*b*^{n + s}. - Alice computes the key by
*K*= a^{m}*vb*^{n}. - Bob computes the key by
*K*=*a*^{r}*ub*^{s}.

### Protocols for encryption and decryption[edit]

This protocol describes how to encrypt a secret message and then decrypt using a non-commutative group. Let Alice want to send a secret message *m* to Bob.

- Let
*G*be a non-commutative group. Let*A*and*B*be public subgroups of*G*such that*ab*=*ba*for all*a*in*A*and*b*in*B*. - An element
*x*from*G*is chosen and published. - Bob chooses a secret key
*b*from*A*and publishes*z*=*x*^{b}as his public key. - Alice chooses a random
*r*from*B*and computes*t*=*z*^{r}. - The encrypted message is
*C*= (*x*^{r},*H*(*t*)*m*), where*H*is some hash function and denotes the XOR operation. Alice sends*C*to Bob. - To decrypt
*C*, Bob recovers*t*as follows: (*x*^{r})^{b}=*x*^{rb}=*x*^{br}= (*x*^{b})^{r}=*z*^{r}=*t*. The plain text message send by Alice is*P*= (*H*(*t*)*m*)*H*(*t*) =*m*.

### Protocols for authentication[edit]

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

- Let
*G*be a non-commutative group and let*A*and*B*be subgroups of*G*such that*ab*=*ba*for all*a*in*A*and*b*in*B*. - An element
*w*from*G*is selected and published. - Alice chooses a private
*s*from*A*and publishes the pair (*w*,*t*) where*t*=*w*^{s}. - Bob chooses an
*r*from*B*and sends a challenge*w*' =*w*^{r}to Alice. - Alice sends the response
*w*' ' = (*w*')^{s}to Bob. - Bob checks if
*w*' ' =*t*^{r}. If this true, then the identity of Alice is established.

## Security basis of the protocols[edit]

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

- The
*conjugacy decision problem*(also called the*conjugacy problem*): Given two elements*u*and*v*in a group*G*determine whether there exists an element*x*in*G*such that*v*=*u*^{x}, that is, such that*v*=*x*^{−1}*ux*. - The
*conjugacy search problem*: Given two elements*u*and*v*in a group*G*find an element*x*in*G*such that*v*=*u*^{x}, that is, such that*v*=*x*^{−1}*ux*.

If no algorithm is known to solve the conjugacy search problem, then the function *x* → *u*^{x} can be considered as a one-way function.

## Platform groups[edit]

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. Let *G* be a group suggested as a platform group for a certain non-commutative cryptographic system. The following is a list of the properties expected of *G*.

- The group
*G*must be well-known and well-studied. - The word problem in
*G*should have a fast solution by a deterministic algorithm. There should be an efficiently computable "normal form" for elements of*G*. - It should be impossible to recover the factors
*x*and*y*from the product*xy*in*G*. - The number of elements of length
*n*in*G*should grow faster than any polynomial in*n*. (Here "length*n*" is the length of a word representing a group element.)

## Examples of platform groups[edit]

### Braid groups[edit]

Let *n* be a positive integer. The braid group *B*_{n} is a group generated by *x*_{1}, *x*_{2}, . . . , *x*_{n-1} having the following presentation:

### Thompson's group[edit]

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

### Grigorchuk's group[edit]

Let *T* denote the infinite rooted binary tree. The set *V* of vertices is the set of all finite binary sequences. Let *A*(*T*) denote the set of all automorphisms of *T*. (An automorphism of *T* permutes vertices preserving connectedness.) The Grigorchuk's group Γ is the subgroup of *A*(*T*) generated by the automorphisms *a*, *b*, *c*, *d* defined as follows:

### Artin group[edit]

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

where ( factors) and .

### Matrix groups[edit]

Let *F* be a finite field. Groups of matrices over *F* have been used as the platform groups of certain non-commutative cryptographic protocols.

### Semidirect products[edit]

^{[1]}

## See also[edit]

## Further reading[edit]

- Alexei Myasnikov; Vladimir Shpilrain; Alexander Ushakov (2008).
*Group-based Cryptography*. Berlin: Birkhäuser Verlag. - Zhenfu Cao (2012).
*New Directions of Modern Cryptography*. Boca Raton: CRC Press, Taylor & Francis Group. ISBN 978-1-4665-0140-9. - Benjamin Fine; et al. (2011). "Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems". arXiv:1103.4093 [cs.CR].
- Alexei G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov (2011).
*Non-commutative Cryptography and Complexity of Group-theoretic Problems*. American Mathematical Society. ISBN 9780821853603.

## References[edit]

**^**M. Habeeb, D. Kahrobaei, C. Koupparis, V. Shpilrain, Public key exchange using semidirect product of (semi)groups, in: ACNS 2013, Lecture Notes Comp. Sc. 7954 (2013), 475--486.