1
$\begingroup$

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'

$\endgroup$
1

1 Answer 1

2
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.