# 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

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
#### Protocol due to Ko, Lee, et al.

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$^a$ to Bob. Alice keeps a private.
* Bob chooses an element b from B and sends w$^b$ to Alice. Bob keeps 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

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

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

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) $\oplus$ m), where H is some hash function and $\oplus$ 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) $\oplus$ m ) $\oplus$ H(t) = m.

### Protocols for authentication

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

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

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
### Braid groups

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:
    $B_{n}=\left\langle x_{1},x_{2},\ldots ,x_{n-1}{\big |}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\right\rangle$

### Thompson's group

Thompson's group is an infinite group F having the following infinite presentation:
    $F=\left\langle x_{0},x_{1},x_{2},\ldots {\big |}x_{k}^{-1}x_{n}x_{k}=x_{n+1}{\text{ for }}k<n\right\rangle$

### Grigorchuk's group

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:
* $a(b_{1},b_{2},\ldots ,b_{n})=(1-b_{1},b_{2},\ldots ,b_{n})$
* $b(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},c(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}$
* $c(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},1-b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},d(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}$
* $d(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{1},b_{2},\ldots ,b_{n})&{\text{ if }}b_{1}=0\\(b_{1},b(b_{2},\ldots ,b_{n}))&{\text{ if }}b_{1}=1\end{cases}}$

### Artin group

An Artin group A(Γ) is a group with the following presentation:
    $A(\Gamma )=\left\langle a_{1},a_{2},\ldots ,a_{n}|\mu _{ij}=\mu _{ji}{\text{ for }}1\leq i<j\leq n\right\rangle$
where $\mu _{ij}=a_{i}a_{j}a_{i}\ldots$ ($m_{ij}$ factors) and $m_{ij}=m_{ji}$.

### Matrix groups

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