IET Information Security · 2018 · 20 citations · 8 references
ComputingComputer ScienceAlgorithmsOptimizationTheory Of ComputationAlgorithm AnalysisApproximation AlgorithmsComputational ComplexityMulticollision AttacksPolynomial Time ComplexityRearrangement Techniques
In this study, the authors present some new algorithms for the unbalanced generalised birthday problem (UGBP), which was proposed by Nikolić and Sasaki in their attacks on the generalised birthday problem (GBP). The authors’ first idea is simple, which uses some precomputing to convert UGBP into GBP. After the precomputing, they just adopt Wagner's k ‐tree algorithm or the algorithms of Bernstein et al . to solve UGBP. Their second idea combines the technique for the unbalanced meet‐in‐the‐middle problem with the improved time–memory trade‐off algorithm for GBP to solve UGBP. Besides, they will utilise the inactive technique and the rearrangement technique to improve the time complexities of their algorithms. The inactive technique is used to neglect the effect of some costly functions, and the rearrangement technique is adopted to balance the time costs between different functions. When k is not a power of 2, the time complexity of their algorithms for UGBP can also be improved by using the multicollision technique.
8
A cryptanalytic time-memory trade-off
Martin E. Hellman · IEEE Transactions on Information Theory · 1980 · 696 citations
A sieve algorithm for the shortest lattice vector problem
Miklós Ajtai, Ravi Kumar, D. Sivakumar · 2001 · 553 citations