基于散列的签名的优缺点

Question

我们知道基于散列的签名(Winternitz签名，HORS(T)签名)是量子安全和高效的.它们可以是有状态的或无状态的，一次或多次.但是，为什么它们在实践中没有得到广泛的应用呢？或者他们可能是，请告诉我一些应用，优点和缺点。

Answer 1

在类似的后量子安全级别上，使用Ed25519与基于点阵的后量子候选体迪利托相对于SPHINCS+的表，并在签名大小和签名时间之间进行权衡，可能有助于解释：

\begin{equation*} \begin{array}{r|rr|rr|rr} \text{sig scheme} && \text{sig bytes} && \text{cycles to sign} \\ \hline \text{ed25519} & \times1= & 64 & \times1= & 45\,400 \\ \text{dilithium3} & \times42= & 2\,701 & \times101= & 4\,600\,060 \\ \text{sphincss192sha256simple} & \times266= & 17\,064 & \times46\,000= & 2\,105\,269\,820 \\ \text{sphincsf192sha256simple} & \times557= & 35\,664 & \times1\,850= & 84\,025\,740 \end{array} \end{equation*}

从2019年AMD 7702和64×2000 the内核上的超for测量中获得的中间周期计数；有关更多细节、不同机器的比较和附加签名方案，请参见完整结果https://bench.cr.yp.to/results-sign.html。

虽然基于散列的签名是合理理解的，并且基于保守的设计原则，但它们比针对经典对手的现代签名标准(椭圆曲线签名方案Ed25519 )昂贵数千倍，而且比传统的签名标准(椭圆曲线签名方案)要大数百倍。(也就是说，SPHINCS+的验证成本并不太高。)

有状态签名方案XMSS已经部署在OpenSSH中，这有点愚蠢，因为(a)有状态签名是操作者用严肃的脚枪，(b)没有必要在很长一段时间内部署后量子在线身份验证机制，只有在量子计算机成为严重威胁时才部署它们，这样以后的会话就不能由量子对手伪造。

(相比之下，后量子加密和后量子密钥协议对于尽快部署( OpenSSH也在试验)非常重要，以防止未来的量子计算机对过去的会话进行追溯解密。)

Answer 2

至于有状态哈希签名的“脚枪”问题，可以归结为重复状态。

基于状态哈希签名(XMSS，LMS)是相当有趣的(可以用竞争的签名生成时间来实现，并且有一个公钥和签名大小之和，这与其他量子后签名算法相比相当好，它基于的硬问题比格子或多元签名方法1要少)，但是它们确实有一个氪石，即状态。

基于状态散列的签名是基于一次签名的集合；对于每一条签名消息，我们在对实际消息进行签名时使用一次签名。如果我们(无论出于什么原因)使用相同的一次签名来签署两条不同的消息，那么对手就有可能使用这两个签名来签署第三条消息(这显然违背了签名方法应该给出的保证)。

最典型的情况是，我们保留要使用的下一次签名的索引，并将该索引保存在某种永久存储中(这样，如果我们重新运行程序，我们就会继续我们离开的地方)。

可能出现的问题：

• 如果我们将永久存储保存在磁盘文件中，那么如果备份，然后再还原磁盘文件，会发生什么情况?还原过程会将当前索引重置为以前使用的索引吗？
• 如果我们在虚拟机上，如果它被克隆了，会发生什么？如果是的话，永久存储是否也会被克隆(因此两个虚拟机可能使用相同的索引来签名两条不同的消息)？
• 如果我们生成一个签名，输出它，但是在更新的状态实际上写到磁盘之前重新启动呢？
• 如果我们需要快速生成签名(例如，使用多个并发签名者)，那么如何确保两个不同的签名者不会意外地使用相同的状态(实际上，这个状态并不难解决)

另一方面，也有可能的解决办法。一种可能是将状态保留在硬件安全模块(不能恢复或克隆)上。

至于为什么有人会经历这种麻烦，一个基于散列签名的场景看起来很有吸引力，那就是图像签名。也就是说，我们生成一个公钥，我们可以将它嵌入到一个难以更新的设备(例如IOT设备)中；当我们试图下载设备的更新时，该设备将验证图像上的签名。这样的设备可能存在很长时间(因此我们对后量子技术感兴趣)，而且我们(或者，至少，我)相信基于哈希签名的签名所依赖的困难问题(我们不知道如何找到特定哈希函数的第二个前置图像)比其他签名方法的相应难题更难解决。

顺便说一句:这些“脚枪”问题不适用于无状态散列签名(如Sphincs+)，这避免了这些状态管理问题。

1：每个执行消息初始哈希(然后对哈希签名)的签名方法都需要假设它们使用的哈希是强的。重点是基于散列的签名使得这是唯一的假设；而基于格的签名方法也需要假设它们所基于的格问题也是很困难的。