Cryptology ePrint Archive: Report 2012/217
Efficient Dissection of Bicomposite Problems with Cryptanalytic Applications
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 improve rebound attacks on hash
functions and to solve with better time complexities (for small memory complexities)
hard combinatorial search problems, such as the well known knapsack problem.
Category / Keywords: secret-key cryptography / Bicomposite problems, dissection algorithm, time-memory tradeoff, cryptanalysis, multiple encryption, knapsack problems
Original Publication (with major differences): IACR-CRYPTO-2012
Date: received 20 Apr 2012, last revised 20 Jun 2019
Contact author: dinuri at cs bgu ac il
Available format(s): PDF | BibTeX Citation
Version: 20190620:111043 (All versions of this report)
Short URL: ia.cr/2012/217
[ Cryptology ePrint archive ]