Break double encryption Let $E_k$ : {0,1}$^l$ be a block cipher encryption function with block-size $l$ and key-length $n$. 

In class, we saw that a double encryption with two independent keys $E{}'_{k_1k_2}(x)$ = $E_{k_1}(E_{k_2}(x))$, 

can be brute-forced in $O(2^n)$ time and $O((l + n)2^n)$ space using the meet-in-the-middle attack: 

create a table with $2^n$ entries mapping
keys of length $l$ to entries of length n by encrypting the known plain text $x$ with all possible keys $k_2$,
then search the table by decrypting the corresponding cipher text $c$ using all possible keys $k_1$.

Suppose you only have $O((l + m)2^m)$ space (where $m &lt; n$),
Give an algorithm to break the double
encryption in time $O(2^{2n-m})$.

I am stuck for days, can't figure out the trick that will allow such an efficient algorithm.

Any ideas? Tips? Hints?

This is homework of course.

ADDED:

Is it sufficient to show that if we choose smaller $n$ the encryption will be broken with non neglect-able probability? Or I must show an algorithm that ALWAYS brake the encryption?
Hint: suppose someone told you $n-m$ bits of $k_2$; how much time/space would a meet-in-the-middle attack take then?