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

Question

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'

Answer 1

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$.