Why is double encryption that's equivalent to single encryption no better than single encryption?

Question

In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:

"if a cryptosystem is such that double encryption is equivalent to a single encryption, then there is no additional security obtained by double encryption"

Why is this?

Answer 1

This is simply saying that if a cryptosystem has a functional composition that is

$$ h_{k}(x) = f_{k_1}(g_{k_2}(x)) $$

then you can find a key for single encryption that works as the double encryption.

For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.

To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:

$$P = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\2 & 4 & 1 & 3 & 5 \end{pmatrix} \text{ and } Q = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1 \end{pmatrix}$$ The compositon of the two keys is

$$R =QP = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\4 & 2 & 5 & 3 & 1 \end{pmatrix}$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.

Now turn back to DES:

Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the subgroup generated by the set of DES permutations is greater than $10^{2499}$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.

If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^{28}$ steps showed by Judy H. Moore and Simmons (paywalled).

Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.

---

The academical works on DES closure

• 1982 - D. Coppersmith, “In Defense of DES”, personal communication^‡ Don Coppersmith was first to ask this. And he developed a method to show that lower bound on the size of the subgroup generated by the DES permutation is to be greater than the number of DES permutations, providing conclusive proof that set of DES permutations is not closed.
• 1988 - Burton S. KaliskiJr.Ronald L. RivestAlan T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES) ^(pay-walled), and pay-wall free. They introduce a novel cycling closure tests which gave evidence that the set of DES permutations is not closed. However, they assumed that DES pseudo-random function on their experiments. Therefore the claims are difficult to prove.
• 1989 - Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search. New results and applications to DES ^(pay-walled)
• 1989 Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search? Application to DES ^(pay-walled)
• 1992 - Campbell and Wiener DES is not a group (paywalled) (and paywall-free). In their conclusive work, they used a similar technique of Quisquater and Delescaille's work.

^{‡ This work claimed to be described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!}