基于离散对数问题的散列

Question

首先，可以用椭圆曲线离散对数问题来证明$H(x)=x*G$ (其中$G$是循环子群的生成点)的一元性。

另外，$H(x)$是同态的，因为$H(x+y)=H(x)+H(y)$，这在某些应用中对哈希函数是有用的。

有哪些缺点或漏洞使得这样的散列方案在实践中不受欢迎？

Answer 1

基于离散日志问题的一个安全哈希函数是$H(x=y)=x\ not G+y\cdot P$，其中$P$是一个不知道离散日志的随机点，而"$|$“表示级联；Damg显示了这一点。在离散日志假设下，这可以被证明是抗碰撞的(如果您能够找到一个碰撞，那么这个可以用来查找$P$的离散日志)。请注意，为了使其感兴趣，输出必须小于输入。然而，这是很容易实现对大多数曲线使用点压缩。一旦你有了这个函数，你就可以得到一个一般的抗碰撞哈希函数，通过应用Merkle变换。

当然，这将是非常低效率的，但是它是一个来自离散日志问题的抗碰撞哈希函数。

本文介绍的是Ivan的无碰撞哈希函数与公钥签名方案。“Katz”教科书(第二版)第8.4.2节也对此作了说明。