Anshel–Anshel–Goldfeld key exchange

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 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 ${\overline{a}}=(a_1,\ldots,a_n)$ in G.
• Alice's private key is a sequence of elements from ${\overline{a}}$ and their inverses: $a_{i_1}^{\varepsilon_1}, \ldots, a_{i_L}^{\varepsilon_L}$, where $a_{i_k}\in{\overline{a}}$ and $\varepsilon_k=\pm 1$. Based on that sequence she computes the product $A = a_{i_1}^{\varepsilon_1} \ldots a_{i_L}^{\varepsilon_L}$.

Bob's public/private information:

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

Transitions:

• Alice sends a tuple ${\overline{a}}=(A^{-1}b_1A,\ldots,A^{-1}b_nA)$ to Bob.
• Bob sends a tuple ${\overline{b}}=(B^{-1}a_1B,\ldots,B^{-1}a_nB)$ to Alice.

Shared key:

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

• Alice computes $K$ as a product $A^{-1} \cdot B^{-1}a_{i_1}^{\varepsilon_1}B\cdots B^{-1}a_{i_L}^{\varepsilon_L}B$.
• Bob computes $K$ as a product $(A^{-1}b_{i_1}^{\varepsilon_1}A \cdots A^{-1} b_{i_L}^{\varepsilon_L}A)^{-1} \cdot B = A^{-1} B^{-1} A B$.

See also

• Algebraic Eraser
• 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.