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 wa 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.

  1. An element w of G is published.
  2. Two subgroups A and B of G such that ab = ba for all a in A and b in B are published.
  3. Alice chooses an element a from A and sends wa to Bob. Alice keeps a private.
  4. Bob chooses an element b from B and sends wb to Alice. Bob keeps b private.
  5. Alice computes K = (wb)a = wba.
  6. Bob computes K' = (wa)b=wab.
  7. 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.

  1. Elements a1, a2, . . . , ak, b1, b2, . . . , bm from G are selected and published.
  2. Alice picks a private x in G as a word in a1, a2, . . . , ak; that is, x = x( a1, a2, . . . , ak ).
  3. Alice sends b1x, b2x, . . . , bmx to Bob.
  4. Bob picks a private y in G as a word in b1, b2, . . . , bm; that is y = y ( b1, b2, . . . , bm ).
  5. Bob sends a1y, a2y, . . . , aky to Alice.
  6. Alice and Bob share the common secret key K = x−1y−1xy.
  7. Alice computes x ( a1y, a2y, . . . , aky ) = y−1 xy. Pre-multiplying it with x−1, Alice gets K.
  8. Bob computes y ( b1x, b2x, . . . , bmx) = x−1yx. 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.

  1. Let G be a public non-abelian finite group.
  2. Let a, b be public elements of G such that abba. Let the orders of a and b be N and M respectively.
  3. Alice chooses two random numbers n < N and m < M and sends u = anbm to Bob.
  4. Bob picks two random numbers r < N and s < M and sends v = arbs to Alice.
  5. The common key shared by Alice and Bob is K = am + rbn + s.
  6. Alice computes the key by K = amvbn.
  7. Bob computes the key by K = arubs.

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.

  1. 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.
  2. An element x from G is chosen and published.
  3. Alice chooses a secret key a from A and publishes y = xa as her public key.
  4. Bob chooses a secret key b from A and publishes z = xb as his public key.
  5. Alice chooses a random r from B and computes t = zr.
  6. 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.
  7. 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 authentication

Let Bob want to check whether the sender of a message is really Alice.

  1. 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.
  2. An element w from G is selected and published.
  3. Alice chooses a private s from A and publishes the pair ( w, t ) where t = w s.
  4. Bob chooses an r from B and sends a challenge w ' = wr to Alice.
  5. Alice sends the response w ' ' = (w ')s to Bob.
  6. Bob checks if w ' ' = tr. 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:

If no algorithm is known to solve the conjugacy search problem, then the function xux 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.

  1. The group G must be well-known and well-studied.
  2. 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.
  3. It should be impossible to recover the factors x and y from the product xy in G.
  4. 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

Main article: Braid group

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 group

Main article: Thompson groups

The Thompson's group is an infinite group F having the following infinite presentation:

Grigorchuk's group

Main article: 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

Main article: Artin group

An Artin group A(Γ) is a group with the following presentation:

where ( factors) and .

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.

See also

Further reading

  1. Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov (2008). Group-based Cryptography. Berlin: Birkhäuser Verlag. 
  2. Zhenfu Cao (2012). New Directions of Modern Cryptography. Boca Raton: CRC Press, Taylor & Francis Group. ISBN 978-1-4665-0140-9. 
  3. Benjamin Fine, et. al. "Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems". arXiv:1103.4093Freely accessible. 
  4. Alexei G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov (2011). Non-commutative Cryptography and Complexity of Group-theoretic Problems. American Mathematical Society. ISBN 9780821853603. 
This article is issued from Wikipedia - version of the 7/13/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.