security - 用于检查大多数签名元素是否未更改的组合数字签名

Question

我不熟悉这个领域，所以如果这个问题看起来微不足道或无聊，请原谅。

我有 N 个字符串，我需要以这样的方式签名，如果最多 M 个字符串被更改、删除或添加，签名仍然有效。N > M，N 可能会有所不同。签名不应允许从签名本身推导出 N。

到目前为止，我所能想象的只是一种简单的方法，分别为每个字符串构建哈希，并将它们全部存储为签名，但它不符合最新要求。

如果存在一些特定于语言的示例，请同时提及它们，-Java、C++、PHP 等都可以。

Answer 1

经过对此事的一些调查，我发现以下信息可能会有所帮助。

有一个所谓的“滚动哈希”。另一项密切相关的技术名为“上下文触发分段哈希”（CTPH）。关于 CTPH 有一篇易于理解的文章： 使用上下文触发分段散列识别几乎相同的文件。

我假设它可以用于签署 N 个元素，并连接在单个输入文件中。

该算法假设块大小（用于定期拼接从传统哈希构建的签名）是众所周知的，因为它嵌入到最终签名中。这可能允许推断签名内容的近似大小，但显然将 N 保密。

对于给定的未知内容，该算法根据 CTPH 提供相似性或同源性的度量，作为已知签名内容和使用其签名的未知内容之间的 0（差异）和 100（同一性）之间的值。