View source for Anshel–Anshel–Goldfeld key exchange

'''Anshel–Anshel–Goldfeld protocol''', also known as a '''commutator key exchange''', is a key-exchange protocol using [[nonabelian group]]s. It was invented by Drs. Michael Anshel, Iris Anshel, and [[Dorian M. Goldfeld|Dorian Goldfeld]]. Unlike other group-based protocols, it does not employ any commuting or commutative subgroups of a given platform group and can use any nonabelian group with efficiently computable normal forms. It is often discussed specifically in application of [[braid groups]], which notably are infinite (and the group elements can take variable quantities of space to represent). The computed shared secret is an element of the group, so in practice this scheme must be accompanied with a sufficiently secure compressive hash function to normalize the group element to a usable bitstring.

== Description ==
Let <math>G</math> be a fixed nonabelian [[Group (mathematics)|group]] called a ''platform group''.

'''Alice's public/private information:'''

* ''Alice's public key'' is a tuple of elements <math>{\bf a}=(a_1,\ldots,a_n)</math> in <math>G</math>. 
* ''Alice's private key'' is a sequence of elements from <math>{\bf a}</math> and their inverses: <math>a_{i_1}^{\varepsilon_1}, \ldots, a_{i_L}^{\varepsilon_L}</math>, where <math>a_{i_k}\in{\bf a}</math> and <math>\varepsilon_k=\pm 1</math>. Based on that sequence she computes the product <math>A = a_{i_1}^{\varepsilon_1} \ldots a_{i_L}^{\varepsilon_L}</math>.

'''Bob's public/private information:'''

* ''Bob's public key'' is a tuple of elements <math>{\bf b}=(b_1,\ldots,b_n)</math> in <math>G</math>. 
* ''Bob's private key'' is a sequence of elements from <math>{\bf b}</math> and their inverses: <math>b_{j_1}^{\delta_1}, \ldots, b_{j_L}^{\delta_L}</math>, where <math>b_{j_k}\in{\bf b}</math> and <math>\delta_k=\pm 1</math>. Based on that sequence he computes the product <math>B = b_{j_1}^{\delta_1} \ldots b_{j_L}^{\delta_L}</math>.

'''Transitions:'''

* Alice sends a tuple <math>{\overline{\bf a}}=(A^{-1}b_1A,\ldots,A^{-1}b_nA)</math> to Bob.
* Bob sends a tuple <math>{\overline{\bf b}}=(B^{-1}a_1B,\ldots,B^{-1}a_nB)</math> to Alice.

'''Shared key:'''

The key shared by Alice and Bob is the group element <math>K = A^{-1} B^{-1} A B \in G</math> called the [[commutator]] of <math>A</math> and <math>B</math>.

* Alice computes <math>K</math> as a product <math>A^{-1} \cdot \left(B^{-1}a_{i_1}^{\varepsilon_1}B\right)\cdots \left(B^{-1}a_{i_L}^{\varepsilon_L}B\right) = A^{-1} B^{-1} A B</math>.
* Bob computes <math>K</math> as a product <math>\left(A^{-1}b_{j_L}^{-\delta_L}A\right) \cdots \left(A^{-1} b_{j_1}^{-\delta_1}A^{}\right) \cdot B = A^{-1} B^{-1} A B</math>.

==Security==
From the standpoint of an attacker trying to attack the protocol, they usually learn the public keys <math>\bf a</math> and <math>\bf b</math>, and the conjugated public keys <math>\overline{\bf a}</math> and <math>\overline{\bf b}</math>. A direct attack then consists of trying to find a suitable <math>A</math> that is generated by the elements of <math>\bf a</math>, and that produces the appropriate conjugations <math>\overline{\bf a}</math> when applied. (An 'indirect' attack would consist of trying to find <math>K</math> directly, which would require some additional special structure of the group.) For this reason the public keys <math>\bf a</math> and <math>\bf b</math> must be chosen to generate a large subgroup of <math>G</math> — ideally, they form a full set of generators, so that <math>A</math> cannot be constrained just by knowing that is generated from <math>\bf a</math>.

Solving for a suitable <math>A</math> given the conjugation relations is called the ''conjugation problem'', and substantial research has been done on attacks to the conjugacy problem on [[braid group]]s, although no full efficient solution has achieved.

==See also==
* [[Algebraic Eraser]]
* [[Group-based cryptography]]

== References ==
*{{cite journal |first1=I. |last1=Anshel |first2=M. |last2=Anshel |first3=D. |last3=Goldfeld |title=An algebraic method for public-key cryptography |journal=Math. Res. Lett. |volume=6 |issue= 3|pages=287–291 |date=1999 |doi= 10.4310/MRL.1999.v6.n3.a3|url=https://www.intlpress.com/site/pub/files/_fulltext/journals/mrl/1999/0006/0003/MRL-1999-0006-0003-a003.pdf |citeseerx=10.1.1.25.8355}}

== Further reading ==
* Baev, D., et al. (2021). [https://iopscience.iop.org/article/10.1088/1742-6596/2131/2/022079/pdf "Modification of Anshel-Anshel-Goldfeld Postquantum Algorithm / Protocol Based on Algebraic Braid Groups, in Order to the Span–Cyberattack Neutralization"], J. Phys.: Conf. Ser. 2131 022079. 2021.

== External links ==
* [https://sites.google.com/site/mikeanshel/ Michael Anshel's website]

{{DEFAULTSORT:Anshel-Anshel-Goldfeld key exchange}}
[[Category:Cryptographic protocols]]