Scenario optimization

Anshel–Anshel–Goldfeld protocol, also known as a commutator key exchange, is a key-exchange protocol using nonabelian groups. It was invented by Drs. Michael Anshel, Iris Anshel, and Dorian Goldfeld. Unlike other group-based protocols it does not employ any commuting or commutative subgroups of a given platform group and can, in fact, use any nonabelian group with efficiently computable normal forms.

Description

Let G be a fixed nonabelian group called a platform group.

Alice's public/private information:

• Alice's public key is a tuple of elements $\bar{a}=(a_1,\dots ,a_n)$ in G.
• Alice's private key is a sequence of elements from $\bar{a}$ and their inverses: $a_{i_1}^{{\epsilon }_1},\dots ,a_{i_L}^{{\epsilon }_L}$, where $a_{i_k}\in \bar{a}$ and ${\epsilon }_k=\pm 1$. Based on that sequence she computes the product $A=a_{i_1}^{{\epsilon }_1}\dots a_{i_L}^{{\epsilon }_L}$.

Bob's public/private information:

• Bob's public key is a tuple of elements $\bar{b}=(b_1,\dots ,b_n)$ in $G$.
• Bob's private key is a sequence of elements from $\bar{b}$ and their inverses: $b_{j_1}^{{\delta }_1},\dots ,b_{j_L}^{{\delta }_L}$, where $b_{j_k}\in \bar{b}$ and ${\delta }_k=\pm 1$. Based on that sequence she computes the product $B=b_{j_1}^{{\delta }_1}\dots b_{j_L}^{{\delta }_L}$.

Transitions:

• Alice sends a tuple $\bar{b}=(A^{-1}{b}_{1}A,\dots ,A^{-1}{b}_{n}A)$ to Bob.
• Bob sends a tuple $\bar{b}=(B^{-1}{a}_{1}B,\dots ,B^{-1}{a}_{n}B)$ to Alice.

Shared key:

The key shared by Alice and Bob is the group element $K=A^{-1}{B}^{-1}AB\in G$ called the commutator of $A$ and $B$.

• Alice computes $K$ as a product $A^{-1}\cdot B^{-1}{a}_{i_1}^{{\epsilon }_1}B\cdots B^{-1}{a}_{i_L}^{{\epsilon }_L}B$.
• Bob computes $K$ as a product $(A^{-1}{b}_{i_1}^{{\epsilon }_1}A\cdots A^{-1}{b}_{i_L}^{{\epsilon }_L}A{)}^{-1}\cdot B=A^{-1}{B}^{-1}AB$.

See also

• Group-based cryptography

References

• I. Anshel, M. Anshel, and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999), pp. 287–291.