Anshel–Anshel–Goldfeld key exchange

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 {\bf a}=(a_1,\ldots,a_n) in G.
• Alice's private key is a sequence of elements from {\bf a} and their inverses: a_{i_1}^{\varepsilon_1}, \ldots, a_{i_L}^{\varepsilon_L}, where a_{i_k}\in{\bf 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 {\bf b}=(b_1,\ldots,b_n) in G.
• Bob's private key is a sequence of elements from {\bf b} and their inverses: b_{j_1}^{\delta_1}, \ldots, b_{j_L}^{\delta_L}, where b_{j_k}\in{\bf 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{\bf a}}=(A^{-1}b_1A,\ldots,A^{-1}b_nA) to Bob.
• Bob sends a tuple {\overline{\bf 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 \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.
• Bob computes K as a product \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.

Security

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

Solving for a suitable A given the conjugation relations is called the conjugation problem, and substantial research has been done on attacks to the conjugacy problem on braid groups, although no full efficient solution has achieved.

References