The following paper presents an elegant new algorithm for solving a broad class of combinatorial optimization problems. The idea of the dissection technique came up by studying strengthened versions of the DES algorithm. DES is a cryptographic algorithm proposed by the National Bureau of Standards (now known as the National Institute for Standards and Technology, or NIST) in 1977 for the protection of sensitive but unclassified U.S. government data. For almost three decades, DES has been a worldwide de facto standard for encryption. IBM may have designed DES, but the U.S. National Security Agency (NSA) decided the key length should be restricted to 56 bits. This was a controversial move, as it would allow the NSA (and no one else) to break the cipher by searching the key space.
A straightforward way to increase the key length seems to encrypt twice, known as double-DES or C = DESK1 (DESK2(P)), where P and C are the plaintext and ciphertext and K1 and K2 are two different k-bit keys. In 1977, Diffie and Hellman demonstrated this method does not help. Let us assume a few ciphertexts and corresponding plaintexts are known (this is a standard assumption in cryptography, one that is very often met in practice). The meet-in-the-middle attack works as follows: one tries all 2k values of the first key K1, computes the values in the middle A = DESK1(P) and stores the pairs (K1, A(K1)) in a table. In a second step, one computes for all keys K2 the value in the middle as
and searches for the value A in the table. If a match is found, the candidate pair (K1, K2) is checked with an additional plaintext and ciphertext. This algorithm requires about 2k encryptions and 2k memory. This is the reason why the financial sector has upgraded single DES to triple-DES, with three encryptions. A meet-in-the-middle attack on triple-DES requires about 22k encryptions and 2k memory.
The authors of this paper ask a natural question: Would one get even better security with quadruple-DES? At first sight one would conclude that breaking quadruple DES requires 22k encryptions and 22k memory. But the rather surprising answer is the cost can be reduced to that of triple-DES by applying recursion, that is, guessing first the value in the middle and subsequently performing two meet-in-the-middle attacks. This idea was proposed by Zhu and Gong for the block cipher KATAN and the authors were inspired by the work of Isobe on the block cipher GOST; however, the authors push these ideas much further in their Crypto 2012 paper by optimizing and generalizing this algorithm for the case of n-fold encryption for any value of n. Moreover, they show that the dissection technique has many applications.
The authors of the following paper ask a natural question: Would one get even better security with quadruple-DES?
This paper describes dissection for two examples. The first is the solution of Rubik’s cube. The dissection solution has the same complexity as an earlier algorithm, but without using group-theoretic properties. The second example is the combinatorial partition problem; a variant of this problem (the knapsack problem) has played a very important role in cryptography for the construction of public-key encryption and hash functions. For this example a more complex strategy is used that divides the problem into uneven parts.
The dissection technique is remarkable, as it starts from a very simple idea, the meet-in-the-middle attack. The authors show this idea can be generalized in an elegant way and that many clever optimizations can push the idea to its limits. A key contribution of this work is the realization that dissection is broadly applicable to combinatorial optimization problems. Finally, the proposed algorithms reduce memory requirements, which is essential to make the algorithms practical.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment