假设我有一个一方创建的 64 字节签名（来自 ed25519）。该方必须进一步压缩签名，使其以 2048 为基数为 4-8 位。然后，第二方必须能够从数据中重新创建签名。
以下是十进制签名的示例：
5670805304946899675614751184947294808143702505785021095830828785725573127924144977212837580418240432902375737987653828318622222068237988634991262293689098
如何将此签名压缩到以 2048 为基数的 4 位左右？这可能使用数独压缩吗？
我认为这是不可能的。至少您说“第二方必须能够从数据中重新创建签名”的部分
这背后的简单原因是熵，或每个签名中包含的信息量。首先，让我们看一下您描述的每种“格式”最多可以存储多少信息。
因此，基于 2048 的数字中的信息已经少了很多（最大可能）。为了让你的函数存在，这意味着不知何故，在 2^512 种可能性中，有足够的冗余信息（即，如果你知道位 a 和 b，你很有可能知道位 c，或者可能是一些值的配置完全不可能，等等），您可以用 44（或 88）位来表征所有可能的输出。
让我们看一下香农的源编码定理：
N iid 每个具有熵 H(X) 的随机变量可以被压缩成 N H(X) 位以上，信息丢失的风险可以忽略不计，因为 N → ∞；但相反，如果将它们压缩成少于 N H(X) 位，则几乎可以肯定信息会丢失。
这里的随机变量是 ed25519 签名。你在问两件事
ed25519 签名中的熵肯定比 44 位或 88 位存储的更多。从网站介绍 Ed25519：
安全级别高。这个系统有一个 2^128 的安全目标；破解它与破解 NIST P-256、具有约 3000 位密钥的 RSA、强大的 128 位分组密码等具有相似的难度。已知的最佳攻击实际上平均花费超过 2^140 位操作，并且成功地以二次方降低随着位操作次数的减少，概率。
但是如果你的函数存在，它可能会容易得多，因为你足以有 2^44（或 2^88）次尝试，每次应用“反向”函数，以详尽地找到所有碰撞。当然，我们不知道假设的反向函数需要多少位操作，但至少它给了你一个想法。另外，如果您使用生日攻击进行这种蛮力攻击，您将只需要此尝试次数的平方根（因此为 2^22 或 2^44）。
相反，如果您阅读了使用平均 2^140 次操作进行此攻击的论文，每次 2^o 次操作的 2^i 次迭代（因此 i+o=140），您可能希望找到一种可以合理枚举的格式所有可能的 2*i 位的 64 字节签名。但是，这仅适用于您的第一个问题，因为攻击可以利用属性，例如某些签名值比其他更频繁地发生。然后，您的最佳存储长度 2*i 只会平均达到，而不是每个值，通过编码一些更频繁发生的值比更频繁发生的值更少位。
除此之外，我们读到：
小签名。签名适合 64 个字节。这些签名实际上是较长签名的压缩版本；压缩和解压缩的时间包含在上面报告的循环计数中。
这意味着即使较大的密钥中有一些冗余，它们已经进行了额外的压缩，我们可以合理地假设较小的密钥中应该有相同的信息密度，如果不是更高的信息密度的话。即，找到冗余的机会更小。
因此，这意味着如果您应用从签名到 44-88 位的转换，您将丢失信息，几乎会占用64 字节的哈希值。尽管无法重新创建从其校验和下载的文件，但这将使得无法根据您计算的哈希重新创建 ed25519 签名。
签名为 64 字节，因此有 256^64 或 2^512 个可能的签名。只有在 2^512 个可能的签名中最多使用 2048^8 = 2^88 个时，才能进行这种压缩量。Ed25519 似乎不太可能出现这种情况。
编辑：修改并澄清了问题，以询问这里是否可以进行数独压缩。有 6670903752021072936960 = 2^72.49... 填充数独网格的方法，远小于标记每个单元格的 9^81 = 2^256.7... 方法。但是签名算法不应该是这样的情况，因此从信息理论上讲，这种压缩是不可能的。