IACR News item: 22 April 2012
Itai Dinur, Orr Dunkelman, Nathan Keller, Adi Shamir
ePrint Report
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
Additional news items may be found on the IACR news page.