May 30, Wednesday 14:15, Room 303, Jacobs Building

Title: Improved Algorithms for Composite Problems

Lecturer: Itai Dinur

Affiliation : Weizmann Institute

A composite problem is a problem that can be split into several simpler subproblems which can be solved independently of each other. A wide variety of problems in Cryptography and in other areas of Computer Science can be treated as composite problems, including finding the key of multiple encryption schemes with independent subkeys, solving knapsack problems, and even finding the shortest solution to the Rubik's cube puzzle.

The meet-in-the-middle (MITM) approach (Merkle and Hellman, 1981) suggests that in such problems, one can obtain the time/memory tradeoff curve TM=N (where N is the number of possible solutions, and T, M are the time and memory complexities of the algorithm). In the last thirty years, several generic algorithms improved over the basic MITM approach and achieved the curve TM=N^{3/4} for specific values of M.

In this talk we show that surprisingly, the curve TM=N^{3/4} is not optimal. We achieve a better curve of TM < N^{3/4} for any M < N^{1/4}, and in particular, obtain TM=N^{5/7} with M=N^{1/7}. Our results are obtained by a new algorithm called dissection, in which the problem is divided into several sub-problems by guessing (parts of) intermediate values. An interesting feature of the technique is that the best results are obtained by division into "exotic" numbers of parts, such as 7 and 11, rather than to 2^k parts (as was common in previous works).

Joint work with Orr Dunkelman, Nathan Keller and Adi Shamir.