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 protocolsedit
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.
Protocols for key exchangeedit
Protocol due to Ko, Lee, et al.edit
The following protocol due to Ko, Lee, et al., establishes a common secret keyK for Alice and Bob.
An element w of G is published.
Two subgroupsA 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 protocoledit
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.
Alice picks a private x in G as a word in a1, a2, . . . , ak; that is, x = x( a1, a2, . . . , ak ).
Alice sends b1x, b2x, . . . , bmx to Bob.
Bob picks a private y in G as a word in b1, b2, . . . , bm; that is y = y ( b1, b2, . . . , bm ).
Bob sends a1y, a2y, . . . , aky to Alice.
Alice and Bob share the common secret key K = x−1y−1xy.
Alice computes x ( a1y, a2y, . . . , aky ) = y−1xy. Pre-multiplying it with x−1, Alice gets K.
Bob computes y ( b1x, b2x, . . . , bmx) = x−1yx. Pre-multiplying it with y−1 and then taking the inverse, Bob gets K.
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 = ambn to Bob.
Bob picks two random numbers r < N and s < M and sends v = arbs to Alice.
The common key shared by Alice and Bob is K = am + rbn + s.
Alice computes the key by K = amvbn.
Bob computes the key by K = arubs.
Protocols for encryption and decryptionedit
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 = xb as his public key.
Alice chooses a random r from B and computes t = zr.
The encrypted message is C = (xr, 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: (xr)b = xrb = xbr = (xb)r = zr = t. The plain text message send by Alice is P = ( H(t) m ) H(t) = m.
Protocols for authenticationedit
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 = ws.
Bob chooses an r from B and sends a challenge w ' = wr to Alice.
Alice sends the response w ' ' = (w ')s to Bob.
Bob checks if w ' ' = tr. If this true, then the identity of Alice is established.
Security basis of the protocolsedit
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 = ux, that is, such that v = x−1ux.
The conjugacy search problem: Given two elements u and v in a group G find an element x in G such that v = ux, that is, such that v = x−1ux.
If no algorithm is known to solve the conjugacy search problem, then the function x → ux can be considered as a one-way function.
Platform groupsedit
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 groupsedit
Braid groupsedit
Let n be a positive integer. The braid group Bn is a group generated by x1, x2, . . . , xn-1 having the following presentation:
Thompson's groupedit
Thompson's group is an infinite group F having the following infinite presentation:
Grigorchuk's groupedit
Let T denote the infinite rootedbinary 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 groupedit
An Artin group A(Γ) is a group with the following presentation:
where ( factors) and .
Matrix groupsedit
Let F be a finite field. Groups of matrices over F have been used as the platform groups of certain non-commutative cryptographic protocols.
^Habeeb, M.; Kahrobaei, D.; Koupparis, C.; Shpilrain, V. (2013). "Public Key Exchange Using Semidirect Product of (Semi)Groups". Applied Cryptography and Network Security. ACNS 2013. Lecture Notes in Computer Science. Vol. 7954. Springer. pp. 475–486. arXiv:1304.6572. CiteSeerX10.1.1.769.1289. doi:10.1007/978-3-642-38980-1_30. ISBN 978-3-642-38980-1.
Further readingedit
Myasnikov, Alexei; Shpilrain, Vladimir; Ushakov, Alexander (2008). Group-based Cryptography. Birkhäuser Verlag. ISBN 9783764388270.
Cao, Zhenfu (2012). New Directions of Modern Cryptography. CRC Press. 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].
Myasnikov, Alexei G.; Shpilrain, Vladimir; Ushakov, Alexander (2011). Non-commutative Cryptography and Complexity of Group-theoretic Problems. American Mathematical Society. ISBN 9780821853603.