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. In these protocols it would be assumed that G is a non-abelian group. If w and a are elements of G the notation wa would indicate the element a−1wa. 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 wa to Bob. Alice keeps a private. Bob chooses an element b from B and sends wb to Alice. Bob keeps b private. Alice computes K = (wb)a = wba. Bob computes K''' = (wa)b=wab. Since ab = ba, K = K'. Alice and Bob share the common secret key K. Anshel-Anshel-Goldfeld key exchange 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 a1, a2, . . . , ak, b1, b2, . . . , bm from G are selected and published.