Non-commutative cryptography

<h2 id="some-non-commutative-cryptographic-protocols">Some non-commutative cryptographic protocols</h2>
In these protocols it would be assumed that G is a <a href="/facts/Non-abelian_group/KQYHrwJl">non-abelian</a> group. If w and a are elements of G the notation wa would indicate the element a−1wa.

<h3>Protocols for key exchange</h3>
<h4>Protocol due to Ko, Lee, et al.</h4>
The following protocol due to Ko, Lee, et al., establishes a common <a href="/facts/Secret_key/5W5PAmT4">secret key</a> K for <a href="/facts/Alice_and_Bob/FSHudRmA">Alice and Bob</a>.

<ol><li>An element w of G is published.</li>
<li>Two <a href="/facts/Subgroup/r91mBgpa">subgroups</a> A and B of G such that ab = ba for all a in A and b in B are published.</li>
<li>Alice chooses an element a from A and sends wa to Bob. Alice keeps a private.</li>
<li>Bob chooses an element b from B and sends wb to Alice. Bob keeps b private.</li>
<li>Alice computes K = (wb)a = wba.</li>
<li>Bob computes K' = (wa)b=wab.</li>
<li>Since ab = ba, K = K'. Alice and Bob share the common secret key K.</li></ol>
<h4>Anshel-Anshel-Goldfeld protocol</h4>
Main article: <a href="/facts/Anshel-Anshel-Goldfeld_key_exchange/cMq0qvzU">Anshel-Anshel-Goldfeld key exchange</a>
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.

<ol><li>Elements a1, a2, . . . , ak, b1, b2, . . . , bm from G are selected and published.</li>
<li>Alice picks a private x in G as a <a href="/facts/Word_(group_theory)/u9jJeb9w">word</a> in a1, a2, . . . , ak; that is, x = x( a1, a2, . . . , ak ).</li>
<li>Alice sends b1x, b2x, . . . , bmx to Bob.</li>
<li>Bob picks a private y in G as a <a href="/facts/Word_(group_theory)/u9jJeb9w">word</a> in b1, b2, . . . , bm; that is y = y ( b1, b2, . . . , bm ).</li>
<li>Bob sends a1y, a2y, . . . , aky to Alice.</li>
<li>Alice and Bob share the common secret key K = x−1y−1xy.</li>
<li>Alice computes x ( a1y, a2y, . . . , aky ) = y−1 xy. Pre-multiplying it with x−1, Alice gets K.</li>
<li>Bob computes y ( b1x, b2x, . . . , bmx) = x−1yx. Pre-multiplying it with y−1 and then taking the inverse, Bob gets K.</li></ol>
<h4>Stickel's key exchange protocol</h4>
In the original formulation of this protocol the group used was the group of <a href="/facts/Invertible_matrix/fPqXk3V8">invertible matrices</a> over a <a href="/facts/Finite_field/UkMGJo3m">finite field</a>.

<ol><li>Let G be a public non-abelian <a href="/facts/Finite_group/vv2tvogB">finite group</a>.</li>
<li>Let a, b be public elements of G such that ab ≠ ba. Let the orders of a and b be N and M respectively.</li>
<li>Alice chooses two random numbers n < N and m < M and sends u = ambn to Bob.</li>
<li>Bob picks two random numbers r < N and s < M and sends v = arbs to Alice.</li>
<li>The common key shared by Alice and Bob is K = am + rbn + s.</li>
<li>Alice computes the key by K = amvbn.</li>
<li>Bob computes the key by K = arubs.</li></ol>
<h3>Protocols for encryption and decryption</h3>
This protocol describes how to <a href="/facts/Encryption/16q29Fdv">encrypt</a> a secret message and then <a href="/facts/Decryption/16q29Fdv">decrypt</a> using a non-commutative group. Let Alice want to send a secret message m to Bob.

<ol><li>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.</li>
<li>An element x from G is chosen and published.</li>
<li>Bob chooses a secret key b from A and publishes z = xb as his public key.</li>
<li>Alice chooses a random r from B and computes t = zr.</li>
<li>The encrypted message is C = (xr, H(t) 
 
 
 
 ⊕
 
 
 {\displaystyle \oplus }
 
 m), where H is some <a href="/facts/Hash_function/rk6MlCt3">hash function</a> and 
 
 
 
 ⊕
 
 
 {\displaystyle \oplus }
 
 denotes the <a href="/facts/XOR/FHyr7hGQ">XOR</a> operation. Alice sends C to Bob.</li>
<li>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) 
 
 
 
 ⊕
 
 
 {\displaystyle \oplus }
 
 m ) 
 
 
 
 ⊕
 
 
 {\displaystyle \oplus }
 
 H(t) = m.</li></ol>
<h3>Protocols for authentication</h3>
Let Bob want to check whether the sender of a message is really Alice.

<ol><li>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.</li>
<li>An element w from G is selected and published.</li>
<li>Alice chooses a private s from A and publishes the pair ( w, t ) where t = w s.</li>
<li>Bob chooses an r from B and sends a challenge w ' = wr to Alice.</li>
<li>Alice sends the response w ' ' = (w ')s to Bob.</li>
<li>Bob checks if w ' ' = tr. If this true, then the identity of Alice is established.</li></ol>
<h2 id="security-basis-of-the-protocols">Security basis of the protocols</h2>
The basis for the security and strength of the various protocols presented above is the difficulty of the following two problems:

<ul><li>The <a href="/facts/Conjugacy_problem/E951lR5q">conjugacy decision problem</a> (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.</li>
<li>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.</li></ul>
If no algorithm is known to solve the conjugacy search problem, then the function x → ux can be considered as a <a href="/facts/One-way_function/rGtcumDW">one-way function</a>.

<h2 id="platform-groups">Platform groups</h2>
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.

<ol><li>The group G must be well-known and well-studied.</li>
<li>The <a href="/facts/Word_problem_for_groups/eKBrkBPv">word problem</a> in G should have a fast solution by a deterministic algorithm. There should be an efficiently computable "normal form" for elements of G.</li>
<li>It should be impossible to recover the factors x and y from the product xy in G.</li>
<li>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.)</li></ol>
<h2 id="examples-of-platform-groups">Examples of platform groups</h2>
<h3>Braid groups</h3>
Main article: <a href="/facts/Braid_group/rn5323Kx">Braid group</a>
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
          
        
        =
        
          ⟨
          
            
              x
              
                1
              
            
            ,
            
              x
              
                2
              
            
            ,
            …
            ,
            
              x
              
                n
                −
                1
              
            
            
              
                |
              
            
            
              x
              
                i
              
            
            
              x
              
                j
              
            
            =
            
              x
              
                j
              
            
            
              x
              
                i
              
            
            
               if 
            
            
              |
            
            i
            −
            j
            
              |
            
            >
            1
            
               and 
            
            
              x
              
                i
              
            
            
              x
              
                j
              
            
            
              x
              
                i
              
            
            =
            
              x
              
                j
              
            
            
              x
              
                i
              
            
            
              x
              
                j
              
            
            
               if 
            
            
              |
            
            i
            −
            j
            
              |
            
            =
            1
          
          ⟩
        
      
    
    {\displaystyle B_{n}=\left\langle x_{1},x_{2},\ldots ,x_{n-1}{\big |}x_{i}x_{j}=x_{j}x_{i}{\text{ if }}|i-j|>1{\text{ and }}x_{i}x_{j}x_{i}=x_{j}x_{i}x_{j}{\text{ if }}|i-j|=1\right\rangle }

<h3>Thompson's group</h3>
Main article: <a href="/facts/Thompson_groups/gGa03pvd">Thompson groups</a>
Thompson's group is an infinite group F having the following infinite presentation:

F
 =
 
 ⟨
 
 
 x
 
 0
 
 
 ,
 
 x
 
 1
 
 
 ,
 
 x
 
 2
 
 
 ,
 …
 
 
 |
 
 
 
 x
 
 k
 
 
 −
 1
 
 
 
 x
 
 n
 
 
 
 x
 
 k
 
 
 =
 
 x
 
 n
 +
 1
 
 
 
  for 
 
 k
 <
 n
 
 ⟩
 
 
 
 {\displaystyle F=\left\langle x_{0},x_{1},x_{2},\ldots {\big |}x_{k}^{-1}x_{n}x_{k}=x_{n+1}{\text{ for }}k<n\right\rangle }

<h3>Grigorchuk's group</h3>
Main article: <a href="/facts/Grigorchuk%27s_group/HahdoDWp">Grigorchuk's group</a>
Let T denote the infinite <a href="/facts/Rooted_tree/TCWk4Joy">rooted</a> <a href="/facts/Binary_tree/TDV7GMpu">binary tree</a>. 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:

<ul><li>
 
 
 
 a
 (
 
 b
 
 1
 
 
 ,
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 =
 (
 1
 −
 
 b
 
 1
 
 
 ,
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 
 
 {\displaystyle a(b_{1},b_{2},\ldots ,b_{n})=(1-b_{1},b_{2},\ldots ,b_{n})}
 
</li>
<li>
 
 
 
 b
 (
 
 b
 
 1
 
 
 ,
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 =
 
 
 {
 
 
 
 (
 
 b
 
 1
 
 
 ,
 1
 −
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 
 
 
  if 
 
 
 b
 
 1
 
 
 =
 0
 
 
 
 
 (
 
 b
 
 1
 
 
 ,
 c
 (
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 )
 
 
 
  if 
 
 
 b
 
 1
 
 
 =
 1
 
 
 
 
 
 
 
 
 {\displaystyle 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}}}
 
</li>
<li>
 
 
 
 c
 (
 
 b
 
 1
 
 
 ,
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 =
 
 
 {
 
 
 
 (
 
 b
 
 1
 
 
 ,
 1
 −
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 
 
 
  if 
 
 
 b
 
 1
 
 
 =
 0
 
 
 
 
 (
 
 b
 
 1
 
 
 ,
 d
 (
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 )
 
 
 
  if 
 
 
 b
 
 1
 
 
 =
 1
 
 
 
 
 
 
 
 
 {\displaystyle 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}}}
 
</li>
<li>
 
 
 
 d
 (
 
 b
 
 1
 
 
 ,
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 =
 
 
 {
 
 
 
 (
 
 b
 
 1
 
 
 ,
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 
 
 
  if 
 
 
 b
 
 1
 
 
 =
 0
 
 
 
 
 (
 
 b
 
 1
 
 
 ,
 b
 (
 
 b
 
 2
 
 
 ,
 …
 ,
 
 b
 
 n
 
 
 )
 )
 
 
 
  if 
 
 
 b
 
 1
 
 
 =
 1
 
 
 
 
 
 
 
 
 {\displaystyle d(b_{1},b_{2},\ldots ,b_{n})={\begin{cases}(b_{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}}}
 
</li></ul>
<h3>Artin group</h3>
Main article: <a href="/facts/Artin_group/9BQbTGE8">Artin group</a>
An Artin group A(Γ) is a group with the following presentation:

A
 (
 Γ
 )
 =
 
 ⟨
 
 
 a
 
 1
 
 
 ,
 
 a
 
 2
 
 
 ,
 …
 ,
 
 a
 
 n
 
 
 
 |
 
 
 μ
 
 i
 j
 
 
 =
 
 μ
 
 j
 i
 
 
 
  for 
 
 1
 ≤
 i
 <
 j
 ≤
 n
 
 ⟩
 
 
 
 {\displaystyle A(\Gamma )=\left\langle a_{1},a_{2},\ldots ,a_{n}|\mu _{ij}=\mu _{ji}{\text{ for }}1\leq i<j\leq n\right\rangle }

where 
 
 
 
 
 μ
 
 i
 j
 
 
 =
 
 a
 
 i
 
 
 
 a
 
 j
 
 
 
 a
 
 i
 
 
 …
 
 
 {\displaystyle \mu _{ij}=a_{i}a_{j}a_{i}\ldots }
 
 (
 
 
 
 
 m
 
 i
 j
 
 
 
 
 {\displaystyle m_{ij}}
 
 factors) and 
 
 
 
 
 m
 
 i
 j
 
 
 =
 
 m
 
 j
 i
 
 
 
 
 {\displaystyle m_{ij}=m_{ji}}
 
.

<h3>Matrix groups</h3>
Main article: <a href="/facts/Matrix_group/wVzG0sa3">Matrix group</a>
Let F be a finite field. Groups of matrices over F have been used as the platform groups of certain non-commutative cryptographic protocols.

<h3>Semidirect products</h3>
Main article: <a href="/facts/Semidirect_product/Uqf87k1I">Semidirect product</a>
<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Group-based_cryptography/4dfsz05G">Group-based cryptography</a></li></ul>

<h2 id="further-reading">Further reading</h2>

<ol><li>Myasnikov, Alexei; Shpilrain, Vladimir; Ushakov, Alexander (2008). <a href="https://books.google.com/books?id=mEa3BAAAQBAJ&pg=PR7">Group-based Cryptography</a>. Birkhäuser Verlag. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9783764388270.</li>
<li>Cao, Zhenfu (2012). New Directions of Modern Cryptography. CRC Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4665-0140-9.</li>
<li>Benjamin Fine; et al. (2011). "Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems". <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1103.4093">1103.4093</a> [<a href="https://arxiv.org/archive/cs.CR">cs.CR</a>].</li>
<li>Myasnikov, Alexei G.; Shpilrain, Vladimir; Ushakov, Alexander (2011). Non-commutative Cryptography and Complexity of Group-theoretic Problems. American Mathematical Society. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780821853603.</li></ol>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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. CiteSeerX 10.1.1.769.1289. doi:10.1007/978-3-642-38980-1_30. ISBN 978-3-642-38980-1. <a href="978-3-642-38980-1" target="_blank">978-3-642-38980-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Non-commutative cryptography open-in-new

Non-commutative cryptography