区分加密属性：隐藏和碰撞阻力

Question

我从Another question看到了以下定义，这些定义有所澄清：

碰撞性：

给定：x和h（x）

很难找到：y与x不同，并且h（y）= h（x）。

隐藏：

给定：h（r | x），其中r | x是r和x的串联

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

很难找到：y使得h（y）= h（r | x）。其中r | x是r和x的串联

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

我的问题：

这是否意味着如果没有秘密r，任何散列函数h（x）都是非隐藏的，也就是说，散列是h(x)，而不是h(r|x)？其中r | x是r和x的串联

例：

假设我做了一个简单的哈希函数h(x) = g^x mod(n)，其中g是该组的生成器。哈希应该是与p(x_1 != x_2, h(x_1) = h(x_2)) = 1/(2^(n/2))碰撞抵抗，但我认为它也隐藏了？

Answer 1

Hashfunctions可以提供抗冲击性

承诺必须隐藏。

与流行观点相反，这些原语并不相同！

非常严格地说，你认为哈希函数不能提供碰撞阻力：总是存在碰撞。理论上输入空间是无限的，但该函数总是产生固定长度的输出。术语实际应该是“H是从一系列抗碰撞函数中随机抽取的”。在实践中，我们只是将该功能称为防碰撞，并忽略它在技术上不是。

承诺必须提供两个属性：隐藏和绑定。绑定意味着您只能将其打开到一个值（这是与碰撞阻力的关系所在的位置）。隐藏意味着无法了解其中包含的元素。这就是为什么一个安全的承诺必须使用随机性（或nounces，但毕竟说完了，然后归结为相同）。想象一下任何哈希函数，无论你想要多么完美：如果你愿意，你可以使用随机预言。如果我给你一个值为H(m)的散列m，你可以计算H(0)，比较结果并了解m = 0，意思是它没有隐藏。

这也是g^x不是隐藏承诺计划的原因。是否绑定取决于你允许的消息空间：如果你允许所有整数，那么一个简单的攻击y = x*phi(n)produces H(y)=H(x)。作品。如果你把它定义为ℤ_p，其中p是组顺序，那么它是完全绑定的，因为它是一个信息理论上的抗冲突单向函数。 （由于消息空间和目标空间大小相同，这次单个功能实际上可以真正防碰撞！）