You are looking at a specific version 20120422:224703 of this paper. See the latest version.

Paper 2012/217

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

Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir

Abstract

In this paper 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 {\it dissection}, which has much 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 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 dissection technique, we show how to use it in a generic way in order to attack hash functions with a rebound attack, to solve hard knapsack problems, and to find the shortest solution to a generalized version of Rubik's cube with better time complexities (for small memory complexities) than the best previously known algorithms.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
CryptanalysisTM-tradeoffmulti-encryptionknapsacksbicompositedissectionrebound
Contact author(s)
itaid @ weizmann ac il
History
2019-06-20: revised
2012-04-22: received
See all versions
Short URL
https://ia.cr/2012/217
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.