Security

Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems

Download Now Date Added: Apr 2012
Format: PDF

A composite problem is a problem that can be split into several simpler subproblems which can be solved independently of each other. To prevent attacks based on such decompositions, designers of cryptographic schemes usually try to entangle the various parts of the scheme by using a complex key schedule in block ciphers, or a strong message expansion in hash functions. In this paper, the authors 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 much better time/memory tradeoffs than previously known algorithms.