在Dili三国或其他任何后量子签名方案中，解决短整数解问题的效果是什么？

Question

我正在努力理解基于后量子的数字签名方案。我知道该方案中存在哪些困难问题，但我很难理解短整数解在该方案中的使用情况。具体来说，我不明白这个问题在计划中究竟是在哪里使用的。另外，如果有人找到了这个难题的解决方案，除了为哈希函数找到冲突之外，还会发生什么？

Answer 1

SIS的硬度(或更准确地说，SIS: MSIS模块版本的硬度)是用来证明晶体Dili立托在所选消息攻击(SUF)下的强不可伪造性的假设。换句话说，如果这个问题很难解决，那么即使允许对手请求其他消息的多个签名，也很难为先前签名的消息生成新的签名。这一点见文件第6.2.2节。

如果你能解决MSIS，那么强大的攻击是可能的:考虑一下规范第4页上的密钥生成算法：

Gen

01 A←R^{k×l} q

02 (\mathbf s_1,\mathbf s_2)\leftarrow S_\eta^l \times S_\eta^k

03 \mathbf t := A\mathbf s_1 +\mathbf s_2

04返回(pk=(A,\mathbf t)，sk=(A,\mathbf t,\mathbf s_1,\mathbf s_2))

给出了值A和\mathbf t，并希望恢复\mathbf s_1和\mathbf s_2以进行密钥恢复攻击(攻击结果层次结构的顶部)。

注意，矩阵\begin{matrix}(A|I|-T)\end{matrix}，其中I是k\times k恒等矩阵，T是从\mathbf t获取条目的k\times k对角线矩阵，有一个简短的解决方案(\mathbf s_1^T,\mathbf s_2^T,1,\cdots 1)^T。因此，该问题的解决方案允许恢复私钥并完全模拟所有者。