耐碰撞性是否暗示（或不）次原像阻力？

#1 楼

根据定义，函数$ F $是




具有抗冲突性，当[以计算为限的对手]不能[具有相当大的几率]展示任何$（a， b）$与$ a \ ne b $和$ F（a）= F（b）$;

当给定$ f $时确定为$ F（a）$对于一个未知的随机$ a $，[有计算限制的]对手不能[以相当大的几率]展示任何$ b $并且$ F（b）= f $;

在给定随机$ a $的情况下，[有算术限制]的对手不能[以相当大的几率]展示任何$ b $且$ a \ ne b $和$ F（a）= F（b）$

是的，抗碰撞性意味着第二原像抗性。通过对证进行证明：假设不具备抗二次原像的属性。重复选择一个随机的$ a $，进行攻击，使其表现出带有$ a \ ne b $和$ F（a）= F（b）$的$ b $，直到成功。根据我们的假设，这需要可行的工作量。一旦显示，那对$（a，b）$证明该抗碰撞属性不成立。


但是，正如CodesinChaos在其评论中指出的，答案是否定的。耐碰撞性和前图像抗性的定义将找到碰撞或（分别）原图像的难度量化为大约$ 2 ^ {n / 2} $或（分别）$ 2 ^ n $个评估，其中$ n $是输出中的位数。

通过反例进行证明：对于偶数$ n $，假设哈希函数$ H：\ {0,1 \} ^ * \ to \ {0,1 \} ^ n $表现为随机函数。现在，将$ F：\ {0,1 \} ^ * \ to \ {0,1 \} ^ n $构造为
$$ F（x）= \ begin {cases} x || x＆\ text {如果} x \ text {具有} n / 2 \ text {位} \\ H（x）＆\ text {否则} \ end {cases} $$
$ F $具有抗碰撞属性（当$ a $和$ b $均为$ n / 2 $位时，$ a \ ne b \表示F（a）\ ne F（b）$；而当$ a都不$或$ b $是$ n / 2 $位，抗碰撞性是$ H $；当$ a $或$ b $的单个是$ n / 2 $位时，另一个必须具有两个等于一半，则需要花费大约$ 2 ^ {n / 2} $的哈希值才能显示此类输入）。但是，以下算法以相当于$ 2 ^ {n / 2} $的哈希值的代价破坏了$ F $的第二原像抵抗特性，远低于要求：如果随机$ a $的大小不等于$ n / 2 $，计算$ H（a）$，如果它的两半相等（预期会在$ 2 ^ {n / 2} $哈希之后出现），则使$ b $为$ n / 2 $位的位串；它认为$ a \ ne b $和$ F（a）= F（b）$。


总而言之：函数的二次原像电阻始终至少与后者一样强作为其抗碰撞性；但是它不能强得多，而不能是二次强，这是理论上的理想。因此，根据定义，抗碰撞性意味着第二原像抗性。当我们保持相同的安全级别（对手的努力和成功几率）来评估这两个属性时，这是正确的。当我们期望与属性和函数的输出大小一致的安全级别时，这是错误的。


以下注释中的补充：问题链接到Elena Andreeva，Bart Mennink和Bart Preneel的论文加密哈希函数的域扩展器的安全属性。那篇技术性很强的论文考虑了各种提议的扩展方法，以在比核心模块接受的更大的输入上迭代哈希函数的核心模块。并且如果在扩展构造中保留了该核心的安全属性，则可以达到可比较的级别（攻击和成功几率）。

就像任何好的论文一样，该论文也给出了其特定的定义，对于一些已确立的定义，请参见其参考文献[15]：P. Rogaway＆T. Shrimpton密码散列函数基础：定义，含义和分离前图像阻力，第二-图像前抵抗力和碰撞抵抗力。所有这些定量定义都与经典结果完全一致，经典结果表明，在任何给定水平（攻击和成功几率）下，抗碰撞性都意味着具有第二原像抗性。

本文表明了一些扩展可以证明（大多数）方法保留了防碰撞级别，但没有证明（大部分）保留了第二原像抗级别。这完全符合上述规则。例如，从假定具有抗碰撞能力的核心块开始，到$ \ mathcal O（2 ^ {n / 2}）$努力和第二原像-抵抗$ \ mathcal O（2 ^ n）$的努力，某些扩展程序可能会构造一个哈希，该哈希抵抗$ \ mathcal O（2 ^ {n / 2}）$的努力，而第二个原像则抵抗$ \数学运算O（2 ^ {2 \ cdot n / 3}）$的努力。效果不佳的扩展器保留了防碰撞级别，但没有保留第二原像的级别。但是，对于使用该扩展器构建的哈希，达到某种努力水平的抗碰撞性仍然意味着达到该努力水平的第二原像抗性。