hash - 加密散列函数的特性

Question

在比特币类(class)的第 1 周讲座中，讨论了加密哈希函数的 3 个属性:

抗碰撞:如果找到两个值 x 和 y 不可行，使得 x != y ，但 H(x)= H(y)，则称散列函数 H 是抗碰撞的。

隐藏:哈希函数 H 隐藏如果:当从具有高熵的概率分布中选择 secret 值 r 时，给定 H(r ‖ x) 找到 x 是不可行的。 ‖ 表示两个字符串的连接。

益智友好。如果对于每个可能的 n 位输出值 y ，如果从具有高熵的分布中选择 k，那么找到 x 使得 H(k ‖ x) = y 是不可行的，则称散列函数 H 是拼图友好的在时间上明显小于 2^n。

益智友好似乎是对隐藏的更详细描述。 2之间有什么显着差异吗？是否有具有 1 个属性但不是两个属性的哈希函数？

Answer 1

我也有同样的想法，区别确实很微妙。我不得不考虑一段时间。

假设你有一个哈希，BadHash。你选择 x' 和一个随机随机数 r'，计算 y' = BadHash(r'|x')，然后给我 y'。事实证明，如果 x' 是 UTF8 编码的英文文本，我可以告诉你 x' 是什么，而且(虽然不是绝对必要的)，我什至可以告诉你 r'。如果 x' 碰巧只是一个随机位串，那我就不走运了。但没关系，这显然不是隐藏的哈希。

现在的难题是:我给你一个值 Y' 和一个随机选择的值 R'(比如“11110011...100”)，然后让你找到一个 x，使得 BadHash(R'|x) = Y'。好消息:事实证明 Y'= BadHash(00101...0001 | UTF8("Bitcoin is deflationary"))。所以因为 BadHash 是非隐藏的(加号)，你可以确定一个 R(即 00101...0001)和 x(即 UTF8(“比特币是通货紧缩的”))，这样 BadHash(R|x) = Y ' 但这对您没有帮助，因为拼图指定您需要一个与不同 R 一起使用的 x，即“11110011...100”。所以你还没有解决这个难题。

您会看到，这两个属性并不等效。至于是否确实有一个属性而不是另一个属性的哈希值——我不知道。