In this talk we show that a large class of diverse problems have a
bicomposite structure which makes it possible to solve them with a new
type of algorithm called dissection, which has better time/memory
tradeoffs than previously known algorithms. A typical example is the
problem of finding the key of multiple encryption schemes with r
independent n-bit keys. All the previous error-free attacks required time
T and memory M satisfying TM = 2^{rn}, and even if "false negatives" are
allowed, no previous attack could achieve TM<2^{3rn/4}. Our new
technique yields the first algorithm which never errs and finds all the
possible keys with a smaller product of TM, such as T=2^{4n} time and
M=2^{n} memory for breaking the sequential execution of r=7 block
ciphers. The improvement ratio we obtain increases in an unbounded way as
r increases, and if we allow algorithms which can sometimes miss
solutions, we can get even better tradeoffs by combining our dissection
technique with parallel collision search.

To demonstrate the generality of the new algorithmic technique, we show
how to use it in a generic way in order to solve with better time
complexities (for small memory complexities) hard combinatorial search
problems, such as solving knapsack problems, or finding the shortest
sequence of face rotations which can unscramble a given state of Rubik's
cube.

This is joint work with Itai Dinur, Nathan Keller, and Adi Shamir.