XMSS^MT私钥大小

Question

我在比较基于散列的签名方案。我正在阅读最新的方案之一XMSS^MT，并试图为具体参数找出它的实际公钥和私钥大小。

我找到了这个纸，它对各种参数都有一些数字，但是它没有说明私钥的大小(即使是XMSS参数)。有人想清楚了吗？

Answer 1

讨论XMSS私钥大小的问题是，存在相当多的大小/性能权衡，因此没有一个答案。

至少，私钥需要有用于生成WOTS+私钥(n位)、n比特公共种子和当前叶索引(20、40或60位，取决于参数集)的值。此外，如果您遵循RFC的建议，您也有一个n位SK_PRF值(用于随机散列)，以及n位根(如果有必要，您可以动态地重新计算这个值)。

如果您这样做(包括建议)，这将转换为136个字节的私钥(对于n=32) (假设参数设置为60级的超级树)。

另一方面，如果您只是这样做，这将意味着，对于您生成的每个签名，您将需要重建每一个涉及的XMSS树；这是不便宜的。

现在，显然要做的事情还包括每个XMSS树的内部内容；这使事情变得更快，但大大增加了私钥的大小。

作为折衷，您可以保存少量内部Merkle树元素，并使用树遍历算法(例如BDS )逐步生成下一个身份验证路径(如果您正在执行XMSS^MT，请不要忘记，在遍历这个树时，要开始构建下一个Merkle树，如果您想避免在耗尽这个树时构建整个下一个XMSS树)。有许多已知的树走算法，具有不同的权衡(和可调整的参数)。

此外，您还可能希望在私钥中包含其他内容。例如，如果您对检测错误攻击感兴趣(对于较低级别的XMSS公钥的错误计算会导致下一个较高的WOTS+签名在两个不同的签名操作中签名)，您可能希望存储当前较低级别树的签名(或公钥)(或者是签名的散列)；这样，您就不会实际使用相同的WOTS+私钥签名两次(或者，如果计算错误导致生成两个不同的签名)。

所有这些都导致了这样一个事实:你可以做很多不同的权衡，因此，对于私钥有多大，没有简单的答案。

您要求提供一个使用BDS的示例；让我们列出一些假设：

• 我们将假设私钥包含我上面列出的各种中心信息、层次结构中每个Merkle树的BDS树、构建下一个Merkle树的位置(对于除顶部以外的所有Merkle树级别)，而没有其他任何内容。
• 我们将使用带内变量k=2的BDS算法(注意: BDS文件指出，只有当H-B为偶数时，该算法才能工作；对该算法的简单修改使其在所有情况下都能工作)。

然后，中心信息采用4n+h位。

而且，如果我们将H=h/d表示为每棵梅克尔树的高度，那么每个BSDS树(包括当前和下一个正在构造的BSDS树；总计2d-1)只占用n(\lfloor 3.5H \rfloor - 4)内存(实际上，它所用的内存稍微少一些，但是它描述了有多少是不平凡的)。

此外，每个活动的BDS结构(它们的d总数)都需要一些辅助信息来跟踪存储在它们的堆栈中的信息(我们不需要为我们正在构建的默克尔树存储辅助信息)。我不想精确地检查占用的内存；我只是将其估计为8H位。

这给出了总共的n(4+(2d+1)(\lfloor 3.5h/d \rfloor - 4)) + 9h位。

不同的假设给出不同的数字(而且可能更高，可能更低.)