加密哈希函数的属性

Question

在比特币课程的第1周讲座中,讨论了加密哈希函数的3个属性:

碰撞阻力:如果找不到两个值x和y,使得x!= y,而H(x)= H(y),则认为散列函数H是抗碰撞的.

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

益智友善.如果对于每个可能的n比特输出值y,如果从具有高熵的分布中选择k,则哈希函数H被认为是难以使用的,那么找到x使得H(k‖x)= y是不可行的.在时间上明显少于2 ^ n.

拼图友好似乎是一个更详细的隐藏描述.2之间有什么显着差异吗？哈希函数有1个属性,但不是两个？

Answer 1

对结构进行重组使我对它更加清晰.

碰撞性:

给定:x和h(x)

很难找到:y与x不同,并且h(y)= h(x).

隐藏:

给定:h(r | x)

秘密:x和极不可能随意选择的r

很难找到:y使得h(y)= h(r | x).

这与抗碰撞性不同,因为y = r | x无关紧要.

益智友好性:

给定:z和非常不可能随机选择的r

很难找到:x使得h(r | x)= z(但它应该存在).

这与抗碰撞性不同,即使我们有一个算法来找到碰撞y,解决方案必须以r开始的约束可能使得y不是解决方案.

这与隐藏不同,类似地,因为r是解谜友好性的约束,但不是隐藏属性中的约束,因为在这种情况下y不需要等于r | x.此外,为了谜题友好,x事先并不为人所知(甚至不是拼图提议者).

Answer 2

我有同样的想法,差异确实很微妙.我不得不考虑这一段时间.

假设你有一个哈希哈希哈希.你选择x'和一个随机的nonce 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("比特币是通货紧缩")).因此,因为BadHash是非隐藏的(加号),你可以确定一个R(即00101 ... 0001)和x(即UTF8("比特币是通货紧缩")),这样BadHash(R | x)= Y '但这对你没有帮助,因为这个谜题指明你需要一个与不同的R一起工作的x,即"11110011 ... 100".所以你还没有解决这个难题.

那么,你看,这两个属性并不相同.至于是否确实存在一个属性而不是另一个属性 - 我不知道.

Answer 3

让我们有：y = H(x|r)。这里的输出是y，输入是r和x。

隐藏属性：

给定哈希函数的输出（y），找到输入（x）是不可行的。注意，没有给出r。

益智游戏属性：

给定哈希函数的输出（y）和部分输入（r），很难找到输入（x）。

Answer 4

这门课程非常混乱，写得不好。

在隐藏问题中，您试图找到x，知道值H（r | x）（当然也知道H）。但是你不认识r！例如，x的集合可能为{0,1}，但您无法在0或1之间进行选择，因为在x上添加秘密r会混合所有可能的哈希值。

在拼图难题中，给出k（或r）！这里的问题是尝试所有可能的x，直到找到给出正确哈希值y的x为止。因此，您最终会找到一个，但这需要时间。（定义中具有k（或r）的原因令人困惑，这仅意味着我们不能通过先反转H来作弊）。

在隐藏问题中，即使您之前尝试过所有可能的r和x对于H。这将不起作用，因为您可以找到r'，x'，r''，x''使得H（r'| x'）= H（r''| x''）。而且由于您不知道r的哪个值是正确的值，因此不可能找到x。