# Is it possible to use Diffie-Hellman protocol for symmetric group?

I was asked this question during one of my first cryptography classes, and I'm not sure if I understand it correctly. To begin, I know that after using the Diffie-Hellman protocol (which itself is asymmetric), we establish symmetric communication. So, what would be the point of using this protocol for a symmetric group, and how would it work if it did?

Maybe I'm not understanding the question correctly, and 'symmetric group' is not the same as 'symmetric encryption'

In the question, a symmetric group is the set $$S_n$$ of permutations of $$n$$ things. $$S_n$$ has $$n!$$ elements. It's internal law noted  $$\circ$$  is function composition: $$w=u\circ v$$ is defined by $$w(i)=u(v(i))$$ where $$i$$ is any of the $$n$$ things. The identity element $$e$$ is the identity function.

We can conveniently represent an element $$u\in S_n$$ as a vector of $$n$$ integers $$u_i\in[0,n)$$, with $$u_i=u(i)$$. Notice that these $$n$$ integers are distinct, thus this representation is not optimally compact. For the composition $$w=u\circ v$$, we get $$w_i=u_{(v_i)}$$, and computing the representation of $$w$$ has cost like $$\mathcal O(n\log n)$$. For the identity function we have $$e_i=i$$.

If we used that group for Diffie-Hellman, we'd somehow select $$n$$ and a public permutation $$g\in S_n$$. We'd need to decide a range $$[0,k_\max)$$ for secret exponents.

We can define and compute $$g^k$$ using $$g^0=e$$, $$g^1=g$$, $$g^k=g^{\lfloor k/2\rfloor}\circ g^{\lceil k/2\rceil }$$ for $$k\ge2$$. This is enough to compute the representation of $$g^k$$ for $$k\ge 0$$, with $$\mathcal O(n\log n\log k)$$ work. We would extend that to negative $$k$$, but do not need to for our purposes.

Then Diffie-Hellman with these parameters $$(n,g,k_\max)$$ in the group $$S_n$$ works just as usual:

• Alice chooses random secret $$k_A\in[0,k_\max)$$, sends $$a=g^{k_A}$$ (as a vector of $$n$$ integers).
• Bob chooses random secret $$k_B\in[0,k_\max)$$, sends $$b=g^{k_B}$$ (as a vector of $$n$$ integers).
• Alice receives $$b$$, computes $$c=b^{k_A}$$ (as a vector of $$n$$ integers) and hashes $$c$$ do get a shared hopefully secret value.
• Bob receives $$a$$, computes $$c=a^{k_B}$$ (as a vector of $$n$$ integers) and hashes $$c$$ do get a shared hopefully secret value.

That works in the sense of generating a shared value. But the system would only be secure if from $$g$$ and $$g^k$$ it was hard to find the value of $$k\bmod\ell$$ where $$\ell$$ is the order of $$g$$. Notice that having such capability would be enough to break the system since $$c=b^{k_A\bmod\ell}$$ and adversaries know $$g$$, $$a=g^{k_A}$$, and $$b$$.

$$\ell$$ is the Least Common Multiple of the cycle lengths $$\ell_j$$ of $$g$$, with $$n=\sum\ell_j$$. We can choose practicable $$n$$ and $$g$$ that yield $$\ell$$ large (e.g. $$384$$-bit with $$n=7699$$, with $$g$$ having $$l_j$$ the first $$60$$ primes).

But it turn out that's not enough for security! Whatever our choice of $$n$$ and $$g$$, the idea is doomed to allows attack with effort polynomial in $$n$$. Sketch of attack finding $$k\bmod\ell$$ from $$g$$ and $$g^k$$:

• Write $$g$$ in cycle notation and find the $$\ell_j$$.
• Find $$k\bmod l_j$$ for each $$j$$.
• Find $$k\bmod\ell$$ by the Chinese Remainder Theorem.

Another way to look at it is that the Pohlig-Hellman algorithm breaks the Discrete Logarithm Problem in $$S_n$$ because the largest prime factor of $$\ell$$ is at most $$n$$.