Meet in the middle

The forty largest cities of the world according to GeoNames, from Shanghai to Taipei, have 494,439,236 inhabitants between them. Can they be split into two teams so that the populations are equal to the person? There are 2⁴⁰ ways to split them, more than a trillion: even at a nanosecond per split, trying them all would take about twenty minutes. Below, the answer is found in a fraction of a second right in your browser, and under the map is an estimate of the brute force at the speed at which your browser adds up sums. Move the number of cities and switch to the cities around Almaty.

The answer is yes, and in more than one way: forty cities split exactly in half, 247,219,618 people each, in 5294 ways. The scene shows the first of them in the order of the search: eighteen cities in one team, twenty-two in the other. On the right are all pairs “the sum of some part of the first twenty cities + the sum of some part of the second twenty”. There are 2²⁰ × 2²⁰ such pairs, the same 2⁴⁰ splits, since every split is made of a choice in the first half and a choice in the second. Blue pairs fall short of half of all the people, orange ones overshoot, and the answers lie exactly on the border between the colours. The algorithm need not look at the whole square. It goes row by row and in each finds by binary search where the colour changes.

The idea

If a problem can be cut into two independent halves so that the answer is made of an answer for the left and an answer for the right, try each half separately, 2^n/2 options each, and store the results of one of them in a sorted table or a hash table. Then for each option of the second half a suitable partner is found by search, not by trying. Instead of 2ⁿ steps, about 2 · 2^n/2, the square root of the former number.

The square root of a trillion is a million. That is the whole strength of the trick and its whole limit: it turns the impossible into the possible, but not into the easy. Meeting in the middle turns a search of 2⁸⁰ into 2⁴¹, and that already needs terabytes of memory. So the trick lives where n is from 30 to 50 and the numbers are too large for dynamic programming.

How it works

Take the problem of two teams. Let s be the total population; we look for a subset of cities with a sum as close as possible to s/2.

1. Cut. Divide the cities into two halves, the first n/2 and the rest.
2. Try the halves. For each half write out the sums of all its subsets. It is convenient to do this by doubling: start with the list [0] and for each city append to the list a copy of itself increased by the city’s population. Then the index of a sum in the list is a mask: bit i of the index means the i-th city of the half is taken.
3. Sort one half. Sort the sums of the left half, 2^n/2 numbers.
4. Meet. For each sum b of the right half, the left sum closest to s/2 − b is needed. Binary search finds the place where that number would go in the sorted list, and the closest sum is either at that place or right before it.

To see the steps on a small example, move the slider in the first scene down to six cities: the square becomes an 8 × 8 table where each cell is one of 64 splits, and the colour border runs between cells. Instead of binary search you can sort both halves and walk with two pointers: up through the left sums, down through the right ones. It is the same colour border, traversed as a staircase, in linear time after sorting. And if what is needed is not the closest sum but an exact one, the left half can be put into a hash table and sorting avoided.

Why the answer is correct

The proof rests on one thing: the answer is made of the answers of the halves, and the halves are independent: a choice in the left does not change what can be chosen in the right. If this is not so, say the teams must be of the same size, the condition stops being independent, but independence can be restored by splitting the sums of the halves by the number of cities taken and letting only matching groups meet. The first problem at the end of the article works this way.

Code

The program splits the 40 largest cities. In Python the sums are conveniently kept in numpy arrays: doubling the list is np.concatenate, sorting is np.argsort, and binary search for all million right sums at once is one call to np.searchsorted. In Go everything is done with ordinary slices, sort and slices.BinarySearch. With equal sums both programs choose the same split: the smallest mask on the right, and with it the smallest on the left.

the 40 largest towns of GeoNames, 494439236 people in all
two halves of 20: 1048576 sums each instead of 1099511627776 subsets
the smallest difference between the teams: 0 people
exact splits: 5294 (each split is counted once, not as A|B and B|A)

Populations in GeoNames are often round, Chongqing has exactly 22 million, Kinshasa 16, and this helps exact splits turn up. But there would be many exact splits anyway: there are more than a trillion subsets and fewer than half a billion possible sums, so each sum has thousands of subsets on average.

A double lock

The best-known application of the trick is in cryptography. Suppose a cipher has a key of k bits, and searching all keys seems too fast. The obvious idea is to encrypt the message twice, with two independent keys: C = E_k2(E_k1(P)). Now there are 2k unknown bits, and searching pairs of keys costs 2^2k. But an attacker who knows at least a piece of plaintext P and its ciphertext C has a shorter way. The intermediate text M = E_k1(P) can be obtained from both sides: by encrypting P with all keys k1 and by decrypting C with all keys k2. Where the two lists coincide, there is a candidate pair of keys. The work is 2 · 2^k cipher calls instead of 2^2k: the second key added one bit of strength, not k.

Below is the real cipher Speck32/64 with a 32-bit block, with keys shortened so that the attack takes seconds. It has encrypted twice the first sentence of War and Peace in the translation by Louise and Aylmer Maude. The attacker knows only its beginning, Well, Pr, eight bytes, two blocks.

The scene opens with keys of 14 bits each, as in the listing below, and finds a single pair. Move the slider to 20 bits and press “Attack” again. Now almost three hundred pairs of keys meet in the middle, 287 with the default keys, and all but one are chance coincidences. The reason is in the sizes. There are 2⁴⁰ pairs of keys and 2³² possible block values, so each middle value has on average 2⁴⁰/2³² = 256 pairs that produce it by pure chance. The second known block weeds them out: the probability that a false pair also guesses it is 2⁻³². When keys are twice as long as the block, more known blocks are needed, and attackers obtain them.

Speck32/64 test vector: a86842f2 (the paper says a86842f2)
keys of 14 bits, 20 blocks intercepted: 6129cdf4 a1e61005 80c3e04a 02fee7c1 ...
cipher calls: 32768 instead of 268435456 pairs of keys
candidates after the first block: 1
after the second block: 1
k1 = 2b7e, k2 = 1a5f: Well, Prince, so Genoa and Lucca are now just family estates of the Buonapartes.

The first line checks the cipher itself: the test vector from the paper by Speck’s authors, key 1918 1110 0908 0100 and block 6574 694c, must give a868 42f2. It matches, so the attack breaks real Speck, not a home-made lookalike.

What it costs

The time is 2 · 2^n/2 for trying the halves, sorting one half, O(2^n/2 · n), and 2^n/2 binary searches, as much again. For an attack on a cipher n is the number of bits in both keys together. Below is a measurement of the attack on double Speck with different key lengths. The time axis is logarithmic: an exponential looks like a straight line, and its slope is the base.

Each extra bit of key doubles the time of meeting in the middle and quadruples the time of the brute force. In Go, searching pairs of twelve-bit keys took about a quarter of a second, and extending the line to twenty bits gives about five hours. Meeting in the middle for twenty bits took less than a second: a difference of twenty-five thousand times.

Memory is the real price

The time went under a square root, but the memory grew: the table of one half is 2^n/2 entries. For 40 cities that is a million numbers, eight megabytes. For 60 it is a billion, and the table no longer fits in an ordinary computer’s memory, although a billion steps is affordable in time. For double DES with 56-bit keys the table is 2⁵⁶ blocks: the attack costs 2⁵⁷ encryptions, which is not that much, but there is nowhere to keep the table, and so in practice time–memory trade-offs are devised for attacks.

One such trade-off for subset sum was found by Richard Schroeppel and Adi Shamir in 1981. The items are divided not into two but into four quarters. The sums of each quarter are 2^n/4 numbers. The sums of the left half are all sums “first quarter + second”, and they need not all be written out at once: it is enough to be able to produce them in increasing order, and a heap of 2^n/4 elements does that. The right half is likewise produced in decreasing order, and the walk is with two pointers, as before. The time is the same, about 2^n/2, and the memory 2^n/4: for n = 60 that is thirty thousand numbers instead of a billion.

When the trick does not help

Small numbers. If population is counted in thousands, there will be few sums, hundreds of thousands, and dynamic programming over sums answers in n · s steps, where s is the sum itself. This is pseudo-polynomial time: for small numbers it beats any exponential, and meeting in the middle is needed when the numbers are large: population to the person, sums in tiyn, 64-bit keys.

The halves are not independent. If a choice in one half arbitrarily limits the choice in the other, “these two cities cannot be put into different teams”, the simple gluing breaks. Sometimes the constraint can be put into the key of the meeting, like the team size in the first problem. If there are many tangled constraints, backtracking with pruning fits better.

Three keys instead of two. Triple encryption E_k3(E_k2(E_k1(P))) is attacked in the middle too: on one side k1 is searched, on the other pairs (k2, k3). That is 2^2k, not 2^3k. So triple DES with three 56-bit keys is considered to have 112 bits of strength, not 168. But 112 bits cannot be taken by brute force, and it was triple DES, not double, that replaced the plain one.

Where it works

• Cryptanalysis. Besides the attack on multiple encryption, the trick appears in the analysis of reduced versions of ciphers and hash functions: if the first rounds depend on one part of the key and the last ones on another, the middle is computed from both sides.
• The discrete logarithm. Find x with g^x ≡ h modulo p. Write x = i · m + j, where m ≈ √p. The table of “baby steps” is the values g^j for all j < m; the “giant steps” are h · g^−im for i = 0, 1, …, and the first match with the table gives the answer. About 2√p multiplications instead of p. The method was published by Daniel Shanks in 1971 under the name “baby-step giant-step”.
• Pathfinding and puzzles. Two waves, from the start and from the end, meet in the middle, and each needs half the depth. This is bidirectional search: the same trick on a graph, where the halves are the first and last moves.
• Programming contests. A limit of n ≤ 40 with numbers up to 10¹⁸ almost always hints at meeting in the middle, and n ≤ 20 at trying masks or dynamic programming over masks.

History

The first to bring a general problem under this trick were Ellis Horowitz and Sartaj Sahni. In 1974 they described an algorithm for number partitioning and knapsack: divide the items into two halves, list the sums of each, sort and merge. The time is 2^n/2 up to a factor, and for subset sum in the worst case nothing noticeably faster has been found since. Three years earlier Daniel Shanks had published the baby-step giant-step method for number theory: the same meeting, only in the exponent.

In 1977 Whitfield Diffie and Martin Hellman, analysing what a key search of the newly adopted DES cipher would cost, noticed that double encryption with two keys takes twice as long to break as single encryption, not 2⁵⁶ times as long. Hence the name of the attack, which later passed to the whole trick. The consequence is well known: when a 56-bit key stopped being enough, DES began to be applied three times. In 1981 Richard Schroeppel and Adi Shamir showed how to make do with 2^n/4 memory instead of 2^n/2.

Problems

In the first problem the teams must be of the same size, and only sums with a matching number of cities may meet. In the second, a lock with two keys and two intercepted blocks; the tests are chosen so that the first meeting in the middle is not always the real one.