签名聚合/多重签名

Question

我想要节省比特币交易中占用的空间签名。为了简化它，下面是块中的一般事务结构：

• 消息
• 公用钥匙
• 电文的签字

在一个块中有许多事务，我希望通过使用签名聚合来节省签名所占用的空间。一个块中的签名使用许多不同的公钥和不同的消息。

我发现这些有趣的文章，但我不确定它们是否解决了我的确切问题。请告诉我，我的问题的解决方案是否可以在其中一篇文章中找到，或者向我指出一个新的方向，或者向我解释为什么这是不可能的。

• 签名聚合
• 普通公钥模型中的多签名与一般分叉引理
• 提高可伸缩性的签名聚合

Answer 1

多重签名方案将是一种签名方案，其中多个当事方都签署了同一条消息。所以这不是我们要找的。

我们正在寻找的是所谓的聚合签名方案。在这种方案中，我们有不同的$\ell$用户，每个用户都有自己的公钥$\mathsf{pk}_i$。每个用户都有一个他们想要签名的不同的消息$m_i$。聚合签名方案的目标是创建一个短签名，以使每个用户$i$确实对各自的消息$m_i$签名的验证者信服。

要做到这一点，通常有五种算法：

• $\mathsf{KGen}(1^n)$：输出键盘$(\mathsf{sk_i}，\mathsf{pk_i})$。
• $\mathsf{符号}(\mathsf{sk_i}，m_i)$：输出签名$\sigma_i$。
• $\mathsf{Vfy}(\mathsf{pk_i}、m_i、\sigma_i)$：如果签名有效，输出$1$，否则输出$0$。
• $\mathsf{Agg}((mathsf{pk_1}，\dots，\mathsf{pk_\ell})，(m_1，\dots，m_\ell)，(\sigma_1，\dots，\sigma_\ell)$：输出聚合签名$\sigma$。
• $\mathsf{AggVfy}((\mathsf{pk_1}、\pk_1、\mathsf{pk_\ell})、(m_1、\dots、m_\ell)、\sigma)$：如果聚合签名对所有邮件有效，则输出$1$；否则，输出$0$。

标准正确性适用于所有消息$m_i$和所有密钥对$(mathsf{sk}_i，\mathsf{pk}_i) \get \mathsf{KGen}(1^n)$，它认为$$\mathsf{Vfy}(mathsf{pk_i}，m_i，\mathsf{符号}(mathsf{sk_i}，m_i)=1美元，$$\mathsf{AggVfy}左((mathsf{pk_1}，\dots，\mathsf{pk_\ell})，(m_1，\dots，m_\ell)，m_1 \dots，\mathsf{pk_\ell}，(m_1，\dots，m_\ell)，\(mathsf{sk_1}，m_1)，\dots，\mathsf{符号}(\mathsf{sk_\ell}，( m_\ell)\end{array}\right)\right) =$1$

除了标准的不可伪造性外，我们还要求聚合签名的不可伪造性。也就是说，对于所有多项式时间的对手，$\mathcal{A}$都存在一个可忽略的函数$\epsilon(n)$，使得$$\Pr_{(mathsf{sk}_1，\mathsf{pk}_1) \得到\mathsf{KGen}(1^n)} \leq \epsilon(n)$$。

这种签名方案的第一次实例化是由于Boneh、Gentry、Lynn和Shacham在他们的论文来自双线性映射的聚合和可验证加密签名中。(具体见第3.1节)在他们的方案中，可以将任意数目的签名聚合到仅由单个组元素组成的聚合签名中。

这个原语还有许多其他的实例化，它们来自不同的假设，具有特殊的属性，比如执行顺序聚合的能力。

虽然其中一些方案可能已经实现了至少基准，但我不知道有任何密码库实现聚合签名。