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⁻¹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₁, a₂, . . . , a_k, b₁, b₂, . . . , b_m from G are selected and published.
Alice picks a private x in G as a word in a₁, a₂, . . . , a_k; that is, x = x( a₁, a₂, . . . , a_k ).
Alice sends b₁^x, b₂^x, . . . , b_m^x to Bob.
Bob picks a private y in G as a word in b₁, b₂, . . . , b_m; that is y = y ( b₁, b₂, . . . , b_m ).
Bob sends a₁^y, a₂^y, . . . , a_k^y to Alice.
Alice and Bob share the common secret key K = x⁻¹y⁻¹xy.
Alice computes x ( a₁^y, a₂^y, . . . , a_k^y ) = y⁻¹ xy. Pre-multiplying it with x⁻¹, Alice gets K.
Bob computes y ( b₁^x, b₂^x, . . . , b_m^x) = x⁻¹yx. Pre-multiplying it with y⁻¹ 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ⁿb^m to Bob.
Bob picks two random numbers r < N and s < M and sends v = a^rb^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^mvbⁿ.
Bob computes the key by K = a^rub^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⁻¹ 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⁻¹ 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₁, x₂, . . . , 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

The 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},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}}$