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−1wa".
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.
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.
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.
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.
Protocols for authentication.
Let Bob want to check whether the sender of a message is really Alice.
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:
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".
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:
Thompson's group.
Thompson's group is an infinite group "F" having the following infinite presentation:
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:
Artin group.
An Artin group "A"(Γ) is a group with the following presentation:
where formula_12 (formula_13 factors) and formula_14.
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.