LMS有多安全？

Question

LMS是一种基于散列的数字签名方案.它是XMSS的一个标准，XMSS具有本文所述的位安全性(标准参数的大约200位安全性)。LMS的安全性假设是基于ROM的哈希函数。这是否意味着LMS的位安全性等于QROM中哈希函数的位安全性？

Answer 1

这是否意味着LMS的位安全性等于QROM中哈希函数的位安全性？

那么，爱德华·伊顿在一个多目标设置中研究了这个问题(也就是说，已经给了对手一些公钥(以及这些密钥的有效签名)，目的是为其中的任何一个提供伪造)；他的结论(定理2，第4.2节)是：

定理2.在多用户设置下，设A是攻击全LMS方案安全性的对手。如果A最多进行Q查询，则它们破坏任何LMS实例的存在不可忘记性的概率最多为580q/2^{n/2}。

考虑到Grover的算法需要\pi /2 \cdot 2^{n/2}查询(将计算操作和未计算操作计算为两个单独的查询)，这意味着安全性不会比log_2(580 / (\pi/2)) \approx 8.5位差于底层哈希函数对Grover算法的安全性。