International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Dissection of Bicomposite Problems with Cryptanalytic Applications

Authors:
Itai Dinur
Orr Dunkelman
Nathan Keller
Adi Shamir
Download:
DOI: 10.1007/s00145-018-9303-2
Search ePrint
Search Google
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 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=2rn TM = 2 rn , and even if “false negatives” are allowed, no attack could achieve TM<23rn/4 TM < 2 3 r n / 4 . Our new technique yields the first algorithm which never errs and finds all the possible keys with a smaller product of TM TM , such as T=24n T = 2 4 n time and M=2n M = 2 n memory for breaking the sequential execution of r=7 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.
BibTeX
@article{jofc-2019-30122,
  title={Efficient Dissection of Bicomposite Problems with Cryptanalytic Applications},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={32},
  pages={1448-1490},
  doi={10.1007/s00145-018-9303-2},
  author={Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir},
  year=2019
}