New algorithms for the unbalanced generalised birthday problem

New algorithms for the unbalanced generalised birthday problem

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

Related content

This is a required field
Please enter a valid email address