algorithm - 数据汇总的哈希算法

Question

我正在寻找具有一组给定属性的非加密哈希算法，但我不知道如何用 Google 可用的术语来描述它。

问题空间:我有一个 64 位整数向量，大部分线性分布在整个空间中。此规则有两个异常(exception):(1) 数字 0 出现得相当频繁，以及 (2) 如果数字 x 出现，它再次出现的可能性大于 2 ^-64。目标是，给定两个向量 A 和 B，有一个方便的机制来快速检测 A 和 B> 不一样。并非所有向量的大小都是固定的，但我希望与另一个向量进行比较的任何向量都具有相同的大小(又名:大小检查是微不足道的)。

我唯一的特殊要求是我希望能够“撤销”一段数据。换句话说，给定 A[i] = x 和一个散列 (A)，计算散列 (A) 应该很便宜A[i] = y。换句话说，我想要一个非加密散列。

---

我想出的最合理的事情是这个(在 Python-ish 中):

# Imagine this uses a Mersenne Twister or some other seeded RNG...
NUMS = generate_numbers(seed)

def hash(a):
    out = 0
    for idx in range(len(a)):
        out ^= a[idx] ^ NUMS[idx]
    return out

def hash_replace(orig_hash, idx, orig_val, new_val):
    return orig_hash ^ (orig_val ^ NUMS[idx]) ^ (new_val ^ NUMS[idx])

这是一个极其简单的算法，它可能工作正常。然而，我编写哈希算法的所有经验告诉我，其他人已经以更好的方式解决了这个问题。

Answer 1

我想你要找的是同态哈希算法，它已经被讨论过了Paillier cryptosystem .

据我从那次讨论中可以看出，现在还没有实际的实现。

最有趣的功能，我想它符合您的需求，是:

H(x*y) = H(x)*H(y)

因此，您可以自由定义单位的下限并依赖该属性。

我用过 Paillier cryptosystem几年前(某处有一个 Java 实现，但我不再有链接)在我的研究期间，但就您正在寻找的内容而言，它要复杂得多。

它在某些约束下具有有趣的特征，例如以下:

n*C(x) = C(n*x)

同样，在我看来，它与您要查找的内容相似，因此也许您应该搜索这一系列的哈希算法。我将尝试使用 Google 搜索更具体的链接。

引用资料:

This one很有趣，但也许它不是一个可行的解决方案，因为你的空间是 [0-2^64[(除非你接受处理大数字)。