In the meet-in-the-middle attack, if we built the tables first and then looked for matches, we would have another high complexity problem. For each of the table 1 entries, compare with all the table 2 entries; this algorithm has complexity of O(2^2k). How the matching could be done while building the tables, resulting in the total complexity remaining at O(2k+1)?
$\begingroup$
$\endgroup$
-
2$\begingroup$ Dictionary (aka hash tables) search complexity is about O(1). $\endgroup$ – kludg Sep 14 '16 at 4:40
$\begingroup$
$\endgroup$
Let $(K,K')$ be the key and let $C=E_{K'}(E_K(P))$.
Generate $$L=[(E_K(P),K):K \in \{0,1\}^k]$$ sorted in a hash table on first coordinate with time complexity $O(2^k).$ You can take a hash table of size a few times $2^k$ to avoid long chains by avoiding too many collisions in the table. Or sort the list at cost $O(k2^k)=\tilde{O}(2^k).$
Now try all $K'\in \{0,1\}^k$ and compute $D_{K'}(C)$ and lookup in the table at constant time, until you get a match. Check a few other plaintext ciphertext pairs to ensure the match is not spurious since the permutation $$u\rightarrow E_{K'}(E_K(u))$$ will typically have some fixed points, which may include $u=P.$ This gives overall time complexity $O(2^k)$ if you choose hash sorting.
