非平衡r-碰撞问题的高效解决算法
目前,在非平衡环境下的 r-碰撞问题还没有得到有效的解决.本文提出了一种新的高效算法来对 r 个不同的非平衡函数寻找对应的 r-碰撞.新算法是将现有的 r-碰撞算法、并行碰撞搜索算法与非平衡中间相遇攻击技术进行有机结合.具体攻击过程如下所示:首先,攻击者把 r 个函数分成左右两个集合,当 r 为偶数时,其对应的左右集合分别为{fl1,fl2,…,flr/2}和{ft1,ft2,…,ftr/2},并需要在左右集合中对应位置的两个非平衡函数 fli 和 fti(1≤i≤「r/2」)之间寻找碰撞.以第 i 对为例,攻击者在碰撞-收集阶段可以采用 PCS 算法收集两个非平衡函数 fli 和 fti 的 2mi 个碰撞.注意到,攻击者需要对左右集合中「r/2」个位置对重复上述寻找碰撞的操作.如果 r 是奇数,攻击者还需要对剩下的函数 f 收集 2m0 个函数值.在碰撞-收集阶段之后,攻击者采用中间相遇攻击在 r-「r/2」个列表中寻找 r-碰撞.新算法的主要结果是:(1)与现有的 r-碰撞算法不同,新算法的时间复杂度是由所需存储量和所选择的分组方法决定的.(2)在存储足够的情况下,新的 r-碰撞算法的时间复杂度公式为:当 r = 2k 时,时间复杂度为 O(2(r-1)n+∑r/2 x=1 log2 Rtx/r+log2 Rlj/2);当 r = 2k+1 时,时间复杂度为O(2(r-1)(n+log2Rlj/2)+log2Rc+∑(r-1)/2x=1 log2Rtx/r),其中 Rlj 表示左集合中实现代价最大的函数的实现代价,Rc 表示未配对函数的实现代价,Rtx(1≤x≤(r-1)/2)表示右集合中各函数实现代价.对于 r = 2k(或 r = 2k+1),攻击者首先需要找到 min(∑r/2x=1 log2 Rtx/r+log2 Rlj/2)(或 min(log2 Rc+∑(r-1)/2x=1 log2 Rtx/r+(r-1)log2 Rlj/2r)),从而求出该情况下的最佳分组方法和最佳时间复杂度.(3)在存储有限的情况下,如果不知道所有分组方法所需的时间复杂度,攻击者就无法得到最佳的时间复杂度.
r-碰撞算法、并行碰撞搜索算法、非平衡中间相遇攻击
10
TP309.7(计算技术、计算机技术)
国家自然科学基金;福建省自然科学基金项目
2023-07-13（万方平台首次上网日期，不代表论文的发表时间）
共14页
574-587
