Diffie–Hellman Key Exchange from Commutativity to Group Laws

The celebrated Diffie–Hellman key exchange [39] is a public-key protocol allowing two parties to agree on a common key. This protocol is of significant historical importance and is widely used in practice.

Let us quickly review this protocol. For a prime $p$, let $C_p$ be a cyclic group of order $p$ and $\gamma \in C_p$ a generator of $C_p$. Alice (resp. Bob) randomly sample $a\in [p-1]:=\{1,\mathrm{\dots },p-1\}$ (resp. $b\in [p-1]$). Alice computes ${\gamma }^a$ and sends it to Bob. Bob computes ${\gamma }^b$ and sends it to Alice. Alice computes ${({\gamma }^b)}^a={\gamma }^{ba}$ as her key. Bob computes ${({\gamma }^a)}^b={\gamma }^{ab}$ as his key.

It is readily seen that the commutativity of $ab=ba$ ensures that ${\gamma }^{ba}={\gamma }^{ab}$ so Alice and Bob share the same key. The role of commutativity is natural and crucial, so various attempts to generalize Diffie–Hellman tried to exploit commutativity in one way or another, even when dealing with non-commutative objects [70, 72].

An intriguing question is then whether commutativity could be generalized or relaxed for reaching key agreement in the Diffie–Hellman-type key exchange protocols. Our goal in this article is to propose a natural generalization via group laws in the framework of group action based cryptography [26, 58].

Cryptography based on group actions was first studied as a framework by Brassard and Yung [26], who proposed the definition of one-way group actions and presented some cryptographic applications. Couveignes developed this framework further but with a focus on commutative groups in [35], and one contribution of Couveignes is the proposal of using class group actions on elliptic curves in cryptography.

Diffie–Hellman key exchange can be formulated via group actions, as observed by Brassard and Yung [26] and Couveignes [35]. Using the notation in the description above, define the set $S$ to be $C_p\setminus \{\mathrm{id}\}$, the cyclic group $C_p$ excluding the identity element $\mathrm{id}$. The group $G:=\mathrm{Aut}(C_p)$ is the automorphism group of $C_p$. Note that $G$ is isomorphic to ${(\mathbb{Z}/p\mathbb{Z})}^{\ast }$, the multiplicative group of $\mathbb{Z}/p\mathbb{Z}$, so we can identify $a\in G$ as an element in ${(\mathbb{Z}/p\mathbb{Z})}^{\ast }$. The group action is then $a\in {(\mathbb{Z}/p\mathbb{Z})}^{\ast }$ sending $\delta \in S=C_p\setminus \{\mathrm{id}\}$ to ${\delta }^a$.

Recently, two works [58, 2] further developed this framework by introducing new notions such as pseudorandom group actions (which naturally generalizes the Decisional Diffie–Hellman assumption [21]) and devising more cryptographic applications. In addition, more candidate group actions suitable for cryptographic uses were proposed. In [58], the general linear group action on tensors was suggested as a candidate for pseudorandom group actions. In [2], the group actions are class group actions with variations such as in [31, 17].

A major application of group action based cryptography is digital signatures. This construction is based on the Goldreich–Micali–Wigderson (GMW) zero-knowledge protocol for graph isomorphism [50] and the Fiat–Shamir (FS) transformation [48]. This GMW-FS construction has seen a recent revival as evidenced by the works [18, 34, 81] for actions by symmetric and general linear groups, and the works [17, 46] for class group actions. See also [22, 19, 14] for recent progress and surveys.

We recall some concrete group actions proposed for use in cryptography, besides the group action underlying discrete logarithm.

On the commutative (abelian) group side, a main candidate is the action of the ideal-class group $\text{cl}(𝒪)$ on the set of ${𝔽}_q$-isomorphism classes of ordinary elliptic curves over ${𝔽}_q$ whose endomorphism ring is a given order $𝒪$ in an imaginary quadratic field. It was later adapted by Castryck et al. [31] to the case of supersingular elliptic curves resulting in an efficient key exchange protocol called CSIDH. Based on CSIDH, many isogeny-based cryptographic constructions are built, such as digital signatures SeaSign [46] and CSI-FiSh [17], threshold signature [47], ring signatures [16], group signatures [15], blind signatures [59], updatable encryption [63], and password-authenticated key exchange (PAKE) [1, 57].

On the non-commutative (non-abelian) group side, there are three problem families, namely linear code equivalence [13, 18], tensor isomorphism and its variations [58, 51, 34, 81], and lattice isomorphism [53, 11, 42]. These are based on actions by monomial groups, general linear groups over finite fields, and general linear groups over $\mathbb{Z}$. Four digital signature schemes, LESS [18], MEDS [34], ALTEQ [20], and Hawk [42], were submitted to the NIST’s call for post-quantum digital signature schemes, with LESS and Hawk making into round 2.

When groups are commutative, then key exchange protocols and public-key encryptions can be realized following Diffie–Hellman [39] and ElGamal [45].

When groups are non-commutative, key exchange and public-key encryption seem much harder to achieve. To devise a public-key encryption scheme based on non-commutative group actions was proposed in [58] as an open problem. In a recent breakthrough [55], Hhan, Morimae and Yamakawa proposed the first public-key encryption scheme based on cryptographic non-commutative group actions, albeit requiring the ciphertexts to be quantum. Regarding key exchange, to the best of our knowledge, there were no proposals in vein of the Diffie–Hellman key exchange protocols before this work. Indeed, as discussed above, commutativity is used crucially in the original Diffie–Hellman protocol to ensure the key agreement.

While commutative groups admit more cryptographic functionalities more easily, there are several reasons to pursue non-commutative group actions, particularly in post-quantum cryptography. In the context of quantum algorithms, algorithmic problems underlying commutative group actions can usually be formulated as instances of the abelian hidden shift problem [33]. This allows for adapting the Kuperberg’s dihedral hidden subgroup algorithm [61] to obtain quantum subexponential-time algorithms such as for constructing elliptic curve isogenies [32] and some recent attacks [73, 23] on CSIDH [31].

On the other hand, the non-abelian group actions used in cryptography, such as linear code equivalence [18] and tensor isomorphism [58, 34, 81], can be cast as instances of the hidden subgroup problem with the ambient groups being symmetric and general linear groups. For such hidden subgroup problems, there is strong negative evidence [52, 68, 40, 41] for using the standard techniques from Shor’s algorithms [78] and Kuperberg’s sieve techniques [61] to obtain a polynomial-time or even subexponential-time quantum algorithm. These are referred to as the “strongest such insights we have about the limits of quantum algorithms” by Moore, Russell, and Vazirani [69].

Besides these considerations from quantum algorithms, the group action computation for CSIDH is relatively slow, and to speed it up requires considerable research (see e.g. [17, 56]). On the other hand, those non-abelian group actions based on lattices, tensors, and linear codes are fast to compute.

More advanced functionalities based on non-abelian group actions can be achieved in the context of quantum cryptography. We already mentioned the public-key encryption scheme with quantum ciphertexts by Hhan, Morimae and Yamakawa [55]. Another exciting recent development is the quantum money scheme based on non-abelian group action by Bostanci, Nehoran, and Zhandry [24].

A law in a group $G$ is an equation that is satisfied by any assignments of variables by group elements in $G$. For example, $xy=yx$ is a law in abelian groups, or put in another way, abelian groups are groups satisfying the commutative law $xy=yx$. Therefore, on the one hand, laws can be used to define group classes, such as abelian groups, metabelian groups, and solvable groups. On the other hand, there was considerable recent research on short laws for almost simple groups (such as symmetric groups) and general finite groups [60, 82, 25], and these works serve as a guidance for several considerations in this paper.

With the commutative law in mind, we reformulate Diffie–Hellman key exchange for abelian group actions as follows. Suppose an abelian group $G$ acts on a set $S$ from the right. For $g\in G$ and $s\in S$, we use $s\ast g$ to denote the result of $g\in G$ acting on $s\in S$. Following Diffie–Hellman, Alice randomly samples $a\in G$ and Bob samples $b\in G$. Alice then computes $s\ast a$ and sends it to Bob, while Bob computes $s\ast b$ and sends it to Alice. Alice and Bob computes $(s\ast b)\ast a$ and $(s\ast a)\ast b$ respectively and they reach a common key $(s\ast b)\ast a=s\ast (ba)=s\ast (ab)=(s\ast a)\ast b$, by group action axioms and the commutativity law. This formulation was observed independently by Couveignes [35] and Rostovtsev–Stolbunov [76, 80] in the context of isogeny-based cryptography.

The Diffie–Hellman key exchange protocol can be readily generalized to actions of groups with laws. Indeed, let $G$ be a group satisfying a law, that is an equation, of the form $u(a,b,c,\mathrm{\dots })=v(a,b,c,\mathrm{\dots })$, where $u$ and $v$ are words in variables $a,b,c,\mathrm{\dots }$ and their inverses. Then by assigning these variables to Alice and Bob appropriately, they can sample group elements from $G$, communicate according to $u$ to get Alice’s key, and communicate according to $v$ to get Bob’s key. The agreement of their keys is then ensured by the group law.

In Section 3, we formally present the above key exchange protocol for actions of groups with laws, and prove its security [10, 49], based on a pseudorandom group action assumption. One simplification we make there is to focus on laws involving just two variables, as a law in $k$ variables can be transformed into another law in $2$ variables of length polynomially bounded by the original law [25].

A natural question is then whether general groups admit some laws. That is, whether certain groups are “outlaws.” To start with, note that finite groups always admit some laws. For example, for a finite group $G$ of order $N$, a naive law is $x^N=\mathrm{id}$. Shorter laws with two variables exist, as Bradford and Thom showed the existence of laws in two variables of length $\tilde{O}(N^{2/3})$ for groups of order $N$ [25]. Still, these laws would not be useful for our purpose, as the group order $N$ is not polynomially bounded.

We now present the key exchange protocol for actions by metabelian groups. We believe that it is a nice example to illustrate the above ideas concretely. However, to the best of our knowledge, we do not have candidate cryptographic actions by metabelian groups; therefore, we will move to an instantiation based on symmetric group actions in the next subsection. We leave the search for cryptographic metabelian group actions as an intriguing open problem.

Denoting by $[a,b]$ the commutator of $a,b$. Recall that a group $G$ is metabelian, if for any $a,b,c,d\in G$, $[a,b][c,d]=[c,d][a,b]$, i.e., $ab{a}^{-1}{b}^{-1}cd{c}^{-1}{d}^{-1}=cd{c}^{-1}{d}^{-1}ab{a}^{-1}{b}^{-1}$. In other words, the metabelian law is $xy{x}^{-1}{y}^{-1}uv{u}^{-1}{v}^{-1}=uv{u}^{-1}{v}^{-1}xy{x}^{-1}{y}^{-1}$ in variables $x,y,u,v$.

Note that $[a,b][c,d]=[c,d][a,b]$ is also equivalent to $[[a,b],[c,d]]=\mathrm{id}$, which means metabelian groups are solvable groups of derived length $\le 2$.¹¹1Briefly speaking, the derived length of a group refers to the number of steps needed to reach the trivial group $\{\mathrm{id}\}$ when repeatedly taking commutator subgroups. For example, dihedral groups and affine maps $x\to ax+b$ over a field are metabelian.

Suppose a metabelian group $G$ acts on a set $S$, with $g\in G$ sending $s\in S$ to $s\ast g\in S$. While the metabelian law can be used for Alice and Bob to reach a key agreement (see below), we need to be cautious about assigning $a,b,c,d$ to Alice and Bob appropriately. Indeed, some assignments of $a,b,c,d\in G$ to Alice and Bob would get us back to the commutative setting, such as $a$ and $b$ to Alice, and $c$ and $d$ to Bob. Furthermore, we need to make sure that one sequence of communications ends with Alice holding the last group element, and the other sequence of communications ends with Bob holding the last group element, so they can apply these last elements to get their share of the key.

With these considerations in mind, we arrive at the following protocol.

1. 1.

   Fix $s\in S$ as the public key.

2. 2.

   Alice randomly samples $a,d\in G$, and Bob randomly samples $b,c\in G$, as their private keys.

3. 3.

   Alice initiates $s\ast a$, and communicates with Bob in the following three rounds:

   1. (a)

      Alice$\stackrel{s\ast a}{\to }$Bob$\stackrel{\left(s\ast a\right)\ast b}{\to }$Alice. Let $t_1=s\ast (ab)$.

   2. (b)

      Alice$\stackrel{t_1\ast a^{-1}}{\to }$Bob$\stackrel{\left(t_1\ast a^{-1}\right)\ast \left(b^{-1}c\right)}{\to }$Alice. Let $t_2=t_1\ast (a^{-1}{b}^{-1}c)$.

   3. (c)

      Alice$\stackrel{t_2\ast d}{\to }$Bob$\stackrel{\left(t_2\ast d\right)\ast c^{-1}}{\to }$Alice. Let $t_3=t_2\ast (d{c}^{-1})$.

   Alice then computes $t_4=t_3\ast d^{-1}$ as her secret key.

4. 4.

   Bob initiates $s\ast c$, and communicates with Alice in the following three rounds.

   1. (a)

      Bob$\stackrel{s\ast c}{\to }$Alice$\stackrel{\left(s\ast c\right)\ast d}{\to }$Bob. Let $r_1=s\ast (cd)$.

   2. (b)

      Bob$\stackrel{r_1\ast c^{-1}}{\to }$Alice$\stackrel{\left(r_1\ast c^{-1}\right)\ast d^{-1}a}{\to }$Bob. Let $r_2=r_1\ast (c^{-1}{d}^{-1}a)$.

   3. (c)

      Bob$\stackrel{r_2\ast b}{\to }$Alice$\stackrel{\left(r_2\ast b\right)\ast a^{-1}}{\to }$Bob. Let $r_3=r_2\ast (b{a}^{-1})$.

   Bob then computes $r_4=r_3\ast b^{-1}$ as his secret key.

Note that by assigning $a,d$ to Alice and $b,c$ to Bob, elements of the form $s\ast ([a,b])$ or $s\ast ([c,d])$ are never revealed during the execution of the protocol. This ensures that we do not get back to the commutative setting.

It is clear that Alice and Bob reach a key agreement: in Step 3, Alice and Bob follow the sequence on the left-hand side of the metabelian law, while in Step 4, Alice and Bob follow the sequence on the right-hand side of the metabelian law. Therefore, $t_4$ and $r_4$, namely the secret keys of Alice and Bob, are the same.

The downside is that Alice and Bob need $6$ rounds of communications. Alice performs $7$ group actions, and so does Bob. In general, the group action is usually assumed to be efficiently computable. Recall that in the original Diffie–Hellman protocol, Alice and Bob only need $1$ round of communication, and each of them performs $2$ group actions. Still, when our interest is more on exploring the theoretical possibility of making use of non-commutative group actions, we could even accommodate polynomially many rounds of communications.

A more serious problem is that we don’t know of concrete cryptographic metabelian group actions. That is, a group action suitable for cryptographic uses needs to demonstrate evidence for satisfying one-way [26] or pseudorandom [58] assumptions. At present, candidate cryptographic group actions are either abelian from isogeny based cryptography [31, 17], or highly non-abelian (almost simple) groups such as symmetric or general linear groups [58, 81, 34, 18]. Indeed, it would be of great interest to identify candidate cryptographic actions by non-abelian solvable groups.

When we turn to symmetric groups ${\mathrm{S}}_n$, the group of permutations of $[n]=\{1,2,\mathrm{\dots },n\}$, some recent nice progress in group theory comes to our aid. In [60], Kozma and Thom demonstrated laws for ${\mathrm{S}}_n$ in two variables of length $\exp (\tilde{O}(\log {(n)}^4))$. This result builds on several important works, including [64, 54]. Actually, if a well-known conjecture of Babai [6] holds, the law length can be brought further down to $n^{O(\log \log (n))}$.

While the laws in [60] are close to polynomial in length, they may still be a bit too complicated to use in cryptographic protocols. Looking into the proofs in [60], an elementary fact about ${\mathrm{S}}_n$ turns out to be crucial: $1/n$ fraction of permutations are full-cycles. This means that ${(xy)}^n=\mathrm{id}$, or equivalently ${(xy)}^{\lceil n/2\rceil }={(y^{-1}{x}^{-1})}^{\lfloor n/2\rfloor }$, is a law that holds with probability (at least) $1/n$ when $x$ and $y$ are randomly sampled from ${\mathrm{S}}_n$.²²2Note that when $x$ and $y$ are assigned with uniformly sampled random permutations, their product $xy$ is also a uniformly random permutation.

Such probabilistic laws have been studied in the literature under the name of “almost laws”, and almost laws in two variables for ${\mathrm{S}}_n$ of length $\tilde{O}(n^8)$ were presented in [83] (see [25]). Here, we shall keep using ${(xy)}^{\lceil n/2\rceil }={(y^{-1}{x}^{-1})}^{\lfloor n/2\rfloor }$ due to its simplicity and efficiency (length $n$ compared to length $\tilde{O}(n^8)$ as in [83]).

This leads to the following protocol for key exchange based on symmetric group actions. Let ${\mathrm{S}}_n$ act on a set $S$, with $g\in {\mathrm{S}}_n$ sending $s\in S$ to $s\ast g$. Alice randomly samples $g\in {\mathrm{S}}_n$ and Bob randomly samples $h\in {\mathrm{S}}_n$. They agree on $s\in S$ which can be made public. For Bob’s key, Alice and Bob compute and communicate $s\ast g$, $s\ast gh$, …, $s\ast {(gh)}^{\lceil n/2\rceil -1}$ in turn. In the last round, Alice sends $s\ast ({(gh)}^{\lceil n/2\rceil -1}g)$ to Bob, and Bob computes $s\ast ({(gh)}^{\lceil n/2\rceil })$ as his key. For Alice’s key, Bob and Alice compute and communicate $s\ast h^{-1}$, $s\ast (h^{-1}{g}^{-1})$, …, $s\ast {(h^{-1}{g}^{-1})}^{\lfloor n/2\rfloor -1}$ in turn. In the last round, Bob sends $s\ast {(h^{-1}{g}^{-1})}^{\lfloor n/2\rfloor -1}{h}^{-1}$ to Alice, and Alice computes $s\ast {(h^{-1}{g}^{-1})}^{\lfloor n/2\rfloor }$ as her key.

In the case of ${(gh)}^n=\mathrm{id}$, such as $gh$ being a full-cycle permutation, $s\ast ({(gh)}^{\lceil n/2\rceil })=s\ast {(h^{-1}{g}^{-1})}^{\lfloor n/2\rfloor }$, that is, the keys of Alice and Bob agree. While the probability for it to hold is $1/n$, it suffices for a theoretical demonstration. We then apply a blackbox transformation from [49] to obtain key confirmation between Alice and Bob, and if it does not satisfy the key confirmation check, we will repeat the key exchange protocol by choosing a new pair of $g$ and $h$, until ${(gh)}^n=\mathrm{id}$ (cf. Section 5).

There has been a long history in designing and analyzing the security of key exchange protocols. There are basically three approaches for defining the security of key exchange protocols [38]: indistinguishability approach [10], simulation-based security paradigm [79, 9], and universal composability [30] or reactive simulatability [74].

For our protocol, we follow Fischlin et al.’s approach [49], which follows the previous work by Bellare and Rogaway [10] via the indistinguishability approach. The reason is that in our protocol, especially in the instantiation, we need to make sure that the shared keys obtained from two parties after the execution of the session are the same, and hence we need our key exchange protocol to have key confirmation property. Basically, following [49], one needs a key exchange protocol $\mathrm{\Pi }$ that provides key secrecy and match security properties, then Fischlin et al. [49] provide a generic transformation to obtain a key exchange preserving those two properties with an additional key confirmation property.

Due to non-commutativity, our key exchange protocol requires more rounds, and hence the transcript will consist of many elements of the form $s,s\ast a,s\ast ab,\mathrm{\dots }$, etc. Therefore, a new hardness assumption is needed for the key secrecy proof to go through following [49]. Using the protocol based on metabelian groups in Section 1.2 as an example, we require that it is hard to distinguish between two distributions $\{(s$, $s\ast a$, $s\ast ab$, $s\ast ab{a}^{-1}$, $\mathrm{\dots }$, $s\ast ab{a}^{-1}{b}^{-1}cd{c}^{-1}$, $s\ast ab{a}^{-1}{b}^{-1}cd{c}^{-1}{d}^{-1})\}$ and $\{(s$, $s\ast a$, $s\ast ab$, $s\ast ab{a}^{-1}$, $\mathrm{\dots }$, $s\ast ab{a}^{-1}{b}^{-1}cd{c}^{-1}$, $s\ast e)\}$ for random $a$, $b$, $c$, $d$, $e$. Note that here the shared key is $K=s\ast ab{a}^{-1}{b}^{-1}cd{c}^{-1}{d}^{-1}$ and a random value is $s\ast e$. Besides that, we also need to consider DLP-like (Assumption 1) and CDH-like (Assumption 2) assumptions to ensure that the shared key cannot be obtained by the adversary from the transcript of the protocol.

To instantiate the above key exchange protocol, we need a concrete group action suitable for cryptographic uses.

Symmetric group actions are an important topic in combinatorics and theoretical computer science. For example, the celebrated graph isomorphism problem can be formulated as the orbit problem of ${\mathrm{S}}_n$ acting on sets of size-$2$ subsets of $[n]$ [65]. Unfortunately (for cryptographers), graph isomorphism turns out to be (almost) easy both in practice [66] and in theory [3]. By contrast, the linear code equivalence problem is generally regarded as a candidate for cryptographic group actions, which asks whether two linear spaces are the same up to permutation of, and scalar multiplications on, the coordinates. In the literature, this version of the problem is usually referred to as monomial code equivalence, to distinguish from permutation code equivalence, in which scalar multiplications are not considered.

Several works show that permutation code equivalence is easy in some cases [77, 8]. Therefore, monomial code equivalence is preferred for cryptographic uses, as the current best practical algorithms for monomial code equivalence are the ones exploiting small-weight vectors by Leon and Beullens [62, 13]. For algorithms with worst-case asymptotic analyses, some recent works on monomial code equivalence design faster but still exponential-time algorithms [12], by exploiting some ideas from Babai’s algorithm on permutation code equivalence [5]. Based on monomial code equivalence, the digital signature scheme LESS [18] was developed and submitted to the call for post-quantum digital signatures of NIST [7].

Directly using monomial code equivalence has two issues. First, it is a monomial group action instead of a symmetric group action. This could be fixed relatively easily by utilizing group laws for the monomial group. The second and more serious issue is the following. During our protocol, a secret key needs to be used several times. Recall that it is straightforward to cast monomial code equivalence as the monomial group $\mathrm{Mon}(n,q)$ acting on the set of $m$-dimensional codes in ${𝔽}_q^n$. With this modeling, in cryptographic protocols, the secret key is the monomial matrix $M$, which is a product of a diagonal matrix $D$ and a permutation matrix $P$ (as in e.g. [18]). A recent surprising discovery is that the secret monomial matrix cannot be used several times, not even twice [36, 28, 29]. The secret key reusing is the main bottleneck for using monomial code equivalence in our key exchange protocols.

In [43], it was shown that a symmetric group action can be extracted from the monomial code equivalence problem. Furthermore, it was suggested there that the techniques in [36, 28, 29] for breaking multiple uses of the secret keys in the monomial group action setting do not carry over to this symmetric group setting, at least not directly. This makes such group action suitable for instantiating the key exchange protocol as above.

We define words and laws in two variables. This is partly for convenience and also due to the fact that $k$-variable laws can be turned to $2$-variable laws by a polynomial blow-up in length [25]. We note that $k$-variable laws could be more efficient in practice.

Let $G$ be a group and $S$ be a set. Suppose $G$ satisfies a useful law $u=v$, where $u=y^{b_1}{x}^{a_1}\mathrm{\dots }{y}^{b_k}{x}^{a_k}$ and $v=x^{c_1}{y}^{d_1}\mathrm{\dots }{x}^{c_{\mathrm{\ell }}}{y}^{d_{\mathrm{\ell }}}$ in variables $x$ and $y$. Let $\alpha :G\times S\to S$ be a group action. Recall that from Section 2, we assume that the following can be computed in polynomial time: group operations (multiplication and inverse), uniform sampling of $G$ and $S$, and the group action function.

Consider the following key exchange protocol between Alice and Bob. To start with, they fix some $s_0\in S$ as the public key. Then Alice randomly samples $g\leftarrow \text{\$}G$, and Bob randomly samples $h\leftarrow \text{\$}G$. Now Alice does the following to obtain her secret key. Recall that by our assumption, we have a word $u=y^{b_1}{x}^{a_1}\mathrm{\dots }{y}^{b_k}{x}^{a_k}$, where $a_i,b_i\in \mathbb{Z}$, and all but possibly $b_1$ are non-zero. If $b_1\ne 0$, then $k\ge 1$. If $b_1=0$, then $k\ge 2$.

1. 1.

   Bob computes $t_1:=\alpha (h^{b_1},s_0)$ and sends it to Alice.

2. 2.

   For $i\in [k-1]$, do the following:

   1. (a)

      Alice computes $s_i:=\alpha (g^{a_i},t_i)$ and sends it to Bob.

   2. (b)

      Bob computes $t_{i+1}:=\alpha (h^{b_{i+1}},s_i)$ and sends it to Alice.

3. 3.

   Alice computes $s_k=\alpha (g^{a_k},t_k)$ as her secret key.

Bob can then obtain his secret key in the same way using $v$. This is just to note that $v$ is of the form $x^{c_1}{y}^{d_1}\mathrm{\dots }{x}^{c_{\mathrm{\ell }}}{y}^{d_{\mathrm{\ell }}}$, where $c_i,d_i\in \mathbb{Z}$, and all but possibly $c_1$ are non-zero. Specifically, Bob does the following.

1. 1.

   Alice computes $s_1^{\prime }:=\alpha (g^{c_1},s_0)$ and sends it to Bob.

2. 2.

   For $i\in [l-1]$, do the following:

   1. (a)

      Bob computes $t_i^{\prime }:=\alpha (h^{d_i},s_i^{\prime })$ and sends it to Alice.

   2. (b)

      Alice computes $s_{i+1}^{\prime }:=\alpha (g^{c_{i+1}},t_i^{\prime })$ and sends it to Bob.

3. 3.

   Bob computes $t_l^{\prime }:=\alpha (h^{d_l},s_l^{\prime })$ as his secret key.

Upon the generic transformation in [49, Figure 4], Alice’s key agrees with Bob’s. This is because Alice holds $\alpha (h^{b_1}{g}^{a_1}\mathrm{\dots }{h}^{b_k}{g}^{a_k},s_0)$ and Bob holds $\alpha (g^{c_1}{h}^{d_1}\mathrm{\dots }{g}^{c_{\mathrm{\ell }}}{h}^{d_{\mathrm{\ell }}},s_0)$. As $u=v$ is a law in $G$, we have that $h^{b_1}{g}^{a_1}\mathrm{\dots }{h}^{b_k}{g}^{a_k}=g^{c_1}{h}^{d_1}\mathrm{\dots }{g}^{c_{\mathrm{\ell }}}{h}^{d_{\mathrm{\ell }}}$, which ensures the key agreement. The number of communications between Alice and Bob depends on the lengths of $u$ and $v$. In the above illustration, it is $2(k+\mathrm{\ell })-2$.

A linear code over ${𝔽}_q$ is a subspace of ${𝔽}_q^n$. An $m$-dimensional code in ${𝔽}_q^n$ can be represented by a generator matrix $C\in {\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)$ with rows spanning the code. The monomial code equivalence problem is formally stated as follows.

Since a monomial matrix is a product of an invertible diagonal matrix and a permutation matrix, it is equivalent to formulate monomial code equivalence as asking if there exist $A\in \mathrm{GL}(m,q)$, $D\in \mathrm{D}(n,q)$, and an $n\times n$ permutation matrix $P$, such that $ACDP=C^{\prime }$.

Following [43], we take a different perspective from above by formulating it as the symmetric group ${\mathrm{S}}_n$ acting on a set $S$ consisting of equivalence classes. Specifically, for $C_1,C_2\in {\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)$, we define an equivalence relation $\sim$ as $C_1\sim C_2$ if and only if there exists some $A\in \mathrm{GL}(m,q)$ and $D\in \mathrm{D}(n,q)$ such that $C_1=A{C}_{2}D$. This equivalence relation naturally partitions ${\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)$ into equivalence classes of ${\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)$ under the action of $\mathrm{GL}(m,q)\times \mathrm{D}(n,q)$. Note that this approach actually aligns with the natural viewpoint in that the monomial group $\mathrm{Mon}(n,q)$ acts on the set of $m$-dimensional codes in ${𝔽}_q^n$, as the codes can be treated as the equivalence classes of ${\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)$ under the action of $\mathrm{GL}(m,q)$.

Denote by ${[C]}_{\sim }:=\{ACD:A\in \mathrm{GL}(m,q),D\in \mathrm{D}(n,q)\}$ the equivalence class determined by $\sim$ and corresponding to $C\in {\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)$. Let ${\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)/\sim =\{{[C]}_{\sim }:C\in {\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)\}$ be the set of equivalence classes under $\sim$. Now we wish to define an action of ${\mathrm{S}}_n$ on ${\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)/\sim$. For $P\in {\mathrm{S}}_n$, since ${[C]}_{\sim }:=\{ACD:A\in \mathrm{GL}(m,q),D\in \mathrm{D}(n,q)\}$ is a set of matrices, a natural map is to send ${[C]}_{\sim }$ to ${[C]}_{\sim }P:=\{ACDP:A\in \mathrm{GL}(m,q),D\in \mathrm{D}(n,q)\}$. For ${\mathrm{S}}_n$ to act on ${\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)/\sim$, we need to show that ${[C]}_{\sim }P$ is an element in ${\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)/\sim$. This is ensured by the following proposition in [43].

Proposition 8 demonstrates that the map $\alpha :{\mathrm{S}}_n\times {\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)/\sim \to {\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)/\sim$ by $P\in {\mathrm{S}}_n$ sending ${[C]}_{\sim }$ to ${[C]}_{\sim }P={[CP]}_{\sim }$ is a well-defined group action.

At the end of our key exchange protocol, Alice and Bob each get $C_1$ and $C_2$ in the same equivalence class ${[C]}_{\sim }\in {\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)/\sim$. That is, there exist $A\in \mathrm{GL}(m,q)$ and $D\in \mathrm{D}(n,q)$ such that $C_1=A{C}_{2}D$. To obtain a common key, Alice and Bob need to perform a canonical form algorithm to reach the same $C^{\ast }\in {\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)/\sim$. Canonical forms have been extensively explored for graphs and matrix tuples [4, 75]. Let $G$ be a group acting on a set $S$. A canonical form algorithm takes an input $s\in S$ and returns a canonical representative $s^{\ast }\in \mathrm{𝖮𝗋𝖻}(s):=\{g\ast s:\forall g\in G\}$. The term “canonical” means that for any input $s^{\prime }\in \mathrm{𝖮𝗋𝖻}(s)$, the output of the canonical form algorithm must be the same element $s^{\ast }\in \mathrm{𝖮𝗋𝖻}(s)$. In our setting, we take $G=\mathrm{GL}(m,q)\times \mathrm{D}(n,q)$ and $S={\mathrm{Mat}}_{\mathrm{f}}(m\times n,q)$. This particular problem has been well studied in [37, 43]. We refer readers to the following result in [43], which gives an algorithmic proof and strengthens [37, Proposition 4] by eliminating the probability of failure.