Non-commutative cryptography

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 application 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[edit]

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[edit]

Protocol due to Ko, Lee, et. al.[edit]

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[edit]

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[edit]

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[edit]

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) \oplus m), where H is some hash function and \oplus 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) \oplus m ) \oplus H(t) = m.

Protocols for authentication[edit]

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 form A and publishes the pair ( w, t ) where t = w s.
  4. Bob chooses an r form 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[edit]

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-1 ux.
  • 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-1 ux.

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[edit]

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[edit]

Braid groups[edit]

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:

 B_n = \left\langle x_1, x_2, \ldots, x_{n-1} \big| x_ix_j=x_jx_i \text{ if } |i-j| >1 \text{ and } x_ix_jx_i=x_jx_ix_j \text{ if } |i-j|=1 \right\rangle

Thompson's group[edit]

Main article: Thompson groups

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_nx_k=x_{n+1} \text{ for } k<n \right\rangle

Grigorchuk's group[edit]

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:

  •  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}

Artin group[edit]

Main article: Artin group

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

 A(\Gamma) = \left\langle a_1, a_2, \ldots, a_n | \mu_{ij} = \mu_{ji} \text{ for } 1 \le i < j \le n \right\rangle

where \mu_{ij} = a_ia_ja_i\ldots (m_{ij} factors) and m_{ij} = m_{ji}.

Matrix groups[edit]

Let F be a finite field. Groups of matrices over F have been used as the platform groups of certain non-commutative cryptographic protocols.

Further reading[edit]

  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". Retrieved 6 June 2014. 
  4. Alexei G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov (2011). Non-commutative Cryptography and Complexity of Group-theoretic Problems. American Mathematical Society. ISBN 9780821853603.