在Grover算法的量子模拟中，什么是简单的8位密码散列函数？

Question

我正在上一个量子计算课程，在最后一个项目中，我们必须创建一个Grover搜索的概念实现的证明，以找到一个困难的哈希冲突(类似于块链)。

我需要一个(相对)简单的散列函数。由于这将运行在一个量子模拟器，我有限的量子位数，我可以模拟。理想情况下，哈希函数应该为任意大小的输入输出8位，不应该是可破解的(例如手工操作)，并且应该是相对快的，因为散列函数(虽然是经典的)将用量子逻辑门来实现。

我正在考虑一个8位版本的SHA-1，但我不确定在这种情况下SHA-1的适应性如何。

Answer 1

我建议使用皮尔逊哈希的导数。它可以用两种形式实现，使用独立和独立的随机排列表：-

1. h1 = T1[h1 ^ x[i]]，h2 = T2[h2 ^ x[i]]，最后是h = h1 ^ h2
2. h = T1[h ^ x[i]]紧接着是h = T2[h ^ x[i]]，所以您可以有效地将一个查找表运行到另一个查找表中，

其中h是最后的8位输出。后一种形式似乎更酷、更简单。以任何可以想到的方式构造表T1和T2。这两种方法都使输出分布与预期的1 \over e 碰撞速率一致。如果您可以为这两个表节省必要的512字节，这是很好的证明，并不是很容易破解，而且非常简单。

请注意。正如评论中所指出的那样，免费的量子位元可能很少。是否可以忽略哈希算法本身的存储需求？如果实验是为了“查找哈希冲突的Grover搜索”，那么您主要关注的是打破哈希而不是制造哈希的技术。因此，我打算将使散列从总模拟量子位数中排除的任何存储要求排除在外。只有你才能决定这是否是一个合适的折衷方案。