Algorithms for Solving the Unbalanced r-Collision Problem.

At present, the problem of r-collision in the unbalanced environment has not yet been effectively solved. In this paper, a new efficient algorithm is proposed to find an unbalanced r-collision of r different and unbalanced functions. The new algorithm adopts the techniques from the previous 3-collision algorithm, the parallel collision search (PCS) algorithm and the unbalanced meet-in-themiddle (UMitM) attack. The attack process of the new algorithm can be described as follows: First, the attacker divides r functions into left and right sets. When r is even, the corresponding left and right sets are {f_l1, f_l2, ???, f_lr/2} and {f_t1, f_t2, ???, f_tr/2} respectively, and it is necessary to find collisions between two unbalanced functions f_li and f_ti (for 1 ≤ ⌊r/2⌋) at corresponding positions in the left and right sets. Take the i-th function for example, the attacker adopts the PCS algorithm to collect 2^mi collisions of two unbalanced functions f_li and f_ti. Note that the attacker needs to repeat the collectioncollision operation for ⌊r/2⌋ pairs of positions in the left and right sets. If r is odd, the attacker also needs to collect 2^m0 images of the left function. After the collision-collection phase, the attacker adopts the MitM attack to find a r-collision between these r -- ⌊r/2⌋ lists. The main results of the new algorithm are: (1) The time complexity of the new algorithm is determined by the memory and the chosen grouping methods, which is different from the previous r-collision algorithm. (2) With sufficient storage, the time complexity formula of the new r-collision algorithm is as follows: when r = 2k, the time complexity is .... When r = 2k + 1, the time complexity is ..., where R_lj is the implementation cost of the function with the highest implementation cost in the left set, Rc is the implementation cost of the unpaired function, and R_tx(1 ≤ x ≤ (r -- 1)/2) is the implementation cost of each function in the right set. The attacker first needs to find min (&#931_x=1^r/2 log₂ R_tx/r + log₂r_lj/2) for r = 2k (or min (log₂ R_c + Σ_x=1^(r-1)/2 log ₂ R_tx/r + (r-1)log₂ R_ij/2r) for r = 2k + 1) so as to find the best grouping method and the best time complexity in this case. (3) With limited storage, the attacker cannot find the best time complexity without exhausting the time complexity of all grouping methods. [ABSTRACT FROM AUTHOR]