多重宇宙下具有隐私和责任的阈值签名方案

Threshold Signature Schemes with Privacy and Accountability in the Multiverse

摘要

多重宇宙架构是一种面向区块链系统设计的抽象结构，适用于去中心化金融应用场景。尽管该架构具有良好的扩展性和适配性，但现有阈值签名方案在此架构下难以同时满足隐私和责任的需求。为此，提出了一种多重宇宙下具有隐私和责任的阈值签名方案。该方案根据多重宇宙的应用场景，构造了一种通用的阈值签名系统模型，设计了将非交互式零知识证明嵌入签名生成过程的隐私增强机制，确保签名的正确性与身份隐私解耦，避免在签名收集过程中泄露签名方身份，并通过 “组合者-跟踪者”双层角色权限机制，在争议或审计场景下能通过追踪密钥识别真实签名方，从而实现恶意行为的可控溯源。通过基于BLS（Boneh-Lynn-Shacham）签名算法的实例化与实验评估，验证了该方案在隐私性、责任性、抗伪造性和运行效率方面的优势，具备较好的实用性与推广潜力。

Abstract

The multiverse architecture is an abstract structure designed for blockchain systems for decentralized financial application scenarios. Although the architecture has good scalability and adaptability, the existing threshold signature schemes are difficult to meet both privacy and accountability requirements under this architecture. For this reason, a threshold signature scheme with privacy and liability in the multiverse is proposed. Based on the application scenario of multiverse, this scheme proposes a set of generalized threshold signature system models, designs a privacy-enhancing mechanism that embeds non-interactive zero-knowledge proofs into the signature generation process, ensures that the correctness of the signature is decoupled from the privacy of the identity, is able to avoid disclosing the identity of the signing party during the signature collection process. Moreover, through the “combiner-tracker” two-layer role authority mechanism, in dispute or audit scenarios can identify the real signing party through the tracking key, so as to realize the controllable traceability of malicious behaviors. The the instantiation and experimental evaluation based on the BLS (Boneh-Lynn-Shacham) signature algorithm validates the advantages of the scheme in terms of privacy, accountability, forgery resistance, and operational efficiency, good practicality and promotion potential.

Graphical abstract

关键词

阈值签名 / 多重宇宙 / 区块链 / 隐私和责任

Key words

threshold signature / multiverse / blockchain / privacy and accountability

0　 引 言

阈值签名方案^[1]是一种特殊类型的数字签名，它允许在多个参与方之间分发秘密签名密钥，使每一方能够使用其私钥非交互式地为任意消息生成部分签名。当获得足够数量的部分签名后，组合者能够将其合并为一个完整的签名，从而验证参与签名的人数是否达到设定的阈值。近年来，阈值签名得到了广泛的应用，尤其是在区块链场景中^[2-3]。

去中心化金融^[4]（Decentralized Finance，DeFi）的兴起，极大推动了加密货币通过去中心化网络将传统金融产品转化为无需中介、信任和透明协议的潜力。区块链预言机是连接链上链下生态的协议层基础设施，其核心功能在于构建可信数据通道，通过安全验证机制将链外数据转化为可编程的链上输入，金融协议通常依赖特殊的预言机节点提供外部关键数据。Chainlink^[5]是全球最大的预言机网络之一，拥有超过300个参与节点。每当数据源值的波动超过设定的限制时，预言机节点会集体确认新的数据值，并在区块链上提交一个由智能合约验证的阈值签名。

然而，针对主流DeFi平台中预言机数据依赖的研究表明，这些设计将预言机视为可信任的一方，预言机很少或根本没有对其行为承担责任。此外，对部署预言机的大规模测量显示^[4]，预言机报告的价格经常偏离当前汇率，表明其操作存在问题。目前，实施阈值签名主要面临两个挑战：一是如何激励预言机改善其行为；二是如何减少低声望预言机对高声望预言机的攻击。因此，在预言机的应用场景中，完成阈值签名需要同时具备隐私性和责任性。隐私性指的是参与阈值签名的预言机要保持匿名性，保护签名者的身份隐私；责任性则是指参与签名的预言机能够被追责。

2022年，Boneh等^[6]提出的隐私性和责任性的阈值签名（Threshold Signatures with Private Accountability，TAPS）首次实现了两者的结合。2023年，Baird等^[7]引入了多重宇宙阈值签名（Multiverse Threshold Signatures，MTS）的新概念，在这一框架下，验证者可以随时定义一个包含系统中各方的任意子集的新宇宙，多重宇宙是所有此类（可能重叠的）宇宙的集合，它们可能具有不同的安全阈值。尽管多重宇宙的场景设计与DeFi系统的需求相对契合，但在隐私性和责任性兼备方面仍显不足^[4，7]。

因此，本文在多重宇宙背景下设计了一种基于BLS（Boneh⁃Lynn⁃Shacham）签名的阈值签名方案，即多重宇宙中具有隐私和责任的阈值签名（Threshold Signatures with Privacy and Accountability in the Multiverse，MTAPS）方案，该方案实现了隐私性与责任性的统一，完全适用于DeFi系统。本文主要贡献包括：

1） 针对多重宇宙架构下的动态阈值与异构节点管理需求，提出一套通用的阈值签名系统模型。该模型支持不同宇宙之间密钥共享、阈值灵活设置与签名互操作，为区块链应用中多角色、多策略的组织结构提供可配置支持；

2） 针对参与方隐私泄露风险，设计了一种将零知识证明（Zero-Knowledge Proof, ZKP）嵌入签名生成过程的隐私增强机制，实现签名正确性与身份隐私的解耦，确保组合者在收集部分签名的过程中无法反推出具体签名方身份；

3） 针对参与方行为可追责的监管诉求，引入“组合者-跟踪者”双层角色权限机制，其中组合者负责签名组合，跟踪者在争议或审计场景下调用追踪密钥识别真实签名方集合，从而实现对恶意行为的可控溯源。

1　 基础知识

定义1 困难问题假设

1） DDH（Decisional Diffie-Hellman）假设。设G是一个阶为素数q的循环群，g群G的一个生成元。对于随机选取的a,b,c\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_q，考虑两个分布：随机四元组：(g,g^a,g^b,g^c)和DDH 四元组：(g,g^a,g^b,g^{ab})。

DDH假设指出，上述两个分布在计算上是不可区分的。即对于任意多项式时间的敌手\mathrm{𝒜}，其区分这两个分布的优势\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{𝒜}}^{\mathrm{d}\mathrm{d}\mathrm{h}}(\lambda )=|\mathrm{P}\mathrm{r}[\mathrm{𝒜}(g,g^a,g^b,g^c)=\mathrm{1}]-\mathrm{P}\mathrm{r}[\mathrm{𝒜}(g,g^a,g^b,g^{ab})=\mathrm{1}]|在\lambda上是可忽略的。

2） CDH（Computational Diffie-Hellman）假设。设G是一个阶为素数q的循环群，g群G的一个生成元。给定(g,g^a,g^b)，其中a,b\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_q。

CDH假设指出，计算g^{ab}是不可行的。即对于任意多项式时间的敌手\mathrm{𝒜}，其成功计算g^{ab}的优势\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{𝒜}}^{\mathrm{c}\mathrm{d}\mathrm{h}}(\lambda )=\mathrm{P}\mathrm{r}[\mathrm{𝒜}(G,g,g^a,g^b)=g^{ab}]在\lambda上是可忽略的。

定义2 公钥加密方案^[8]

\mathrm{P}\mathrm{K}\mathrm{E}=(\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t},\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t})由以下三个算法组成。

1) (\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda })：安全参数\lambda为输入，公私钥对(\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})为输出，其中\mathrm{p}\mathrm{k}为公钥，\mathrm{s}\mathrm{k}为私钥。

2) \mathrm{c}\mathrm{t}\leftarrow \mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{p}\mathrm{k},m)：公钥\mathrm{p}\mathrm{k}，明文消息m为输入，密文\mathrm{c}\mathrm{t}为输出。

3) m\leftarrow \mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{s}\mathrm{k},\mathrm{c}\mathrm{t})：私钥\mathrm{s}\mathrm{k}，密文\mathrm{c}\mathrm{t}为输入，明文消息m为输出。

正确性 \forall \lambda \in {\mathbb{Z}}^{\mathrm{*}},\forall (\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda }),\forall m\in{\{\mathrm{0,1}\}}^{\mathrm{*}},可得到\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{s}\mathrm{k},\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{p}\mathrm{k},m))=m。

定义3 数字签名方案^[9]

\mathrm{S}\mathrm{I}\mathrm{G}=(\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n},\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}) 由以下三个算法组成。

1) (\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda })：安全参数\lambda为输入，公私钥对(\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})为输出，其中\mathrm{p}\mathrm{k}为公钥，\mathrm{s}\mathrm{k}为私钥。

2) \sigma \leftarrow \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{s}\mathrm{k},m)：私钥\mathrm{s}\mathrm{k}，消息m为输入，签名\sigma为输出。

3) \mathrm{1}/\mathrm{0}\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{k},m,\sigma )：公钥\mathrm{p}\mathrm{k}，消息m和签名\sigma为输入。输出\mathrm{1}/\mathrm{0}表示签名有效或无效。

正确性 \forall \lambda \in {\mathbb{Z}}^{\mathrm{*}},\forall (\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda }),\forall m\in{\{\mathrm{0,1}\}}^{\mathrm{*}}，可得到\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{k},m,\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{s}\mathrm{k},m))=\mathrm{1}。

定义4 聚合签名方案^[10]

\mathrm{A}\mathrm{S}=(\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n},\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y},\mathrm{A}\mathrm{g}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e},\mathrm{A}\mathrm{g}\mathrm{g}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y})由以下五个算法组成。

1) (\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda })：安全参数\lambda为输入，公私钥对(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)为输出，其中\mathrm{p}{\mathrm{k}}_i为公钥，\mathrm{s}{\mathrm{k}}_i为私钥。

2) {\sigma }_i\leftarrow \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{s}{\mathrm{k}}_i,m)：私钥\mathrm{s}{\mathrm{k}}_i，消息m为输入，签名{\sigma }_i为输出。

3) \mathrm{1}/\mathrm{0}\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}{\mathrm{k}}_i,m,{\sigma }_i)：公钥\mathrm{p}{\mathrm{k}}_i，消息m和签名{\sigma }_i为输入。输出\mathrm{1}/\mathrm{0}表示签名有效或无效。

4) \sigma \leftarrow \mathrm{A}\mathrm{g}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}(m,\{\mathrm{p}{\mathrm{k}}_i,{\sigma }_i{\}}_{i=\mathrm{1}}^t)：消息m和t个公钥以及其对应的签名\{\mathrm{p}{\mathrm{k}}_i,{\sigma }_i{\}}_{i=\mathrm{1}}^t为输入，聚合签名\sigma为输出。

5) \mathrm{1}/\mathrm{0}\leftarrow \mathrm{A}\mathrm{g}\mathrm{g}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\{\mathrm{p}{\mathrm{k}}_i,{\sigma }_i{\}}_{i=\mathrm{1}}^t,m,\sigma )：t个公钥以及其对应的签名\{\mathrm{p}{\mathrm{k}}_i,{\sigma }_i{\}}_{i=\mathrm{1}}^t，消息m和聚合签名\sigma为输入，输出\mathrm{1}/\mathrm{0}表示聚合签名有效或无效。

正确性 \forall \lambda \in {\mathbb{Z}}^{\mathrm{*}},\forall i,\forall (\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda }),\forall m\in {\{\mathrm{0,1}\}}^{\mathrm{*}}可得到\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}{\mathrm{k}}_i,m,\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{s}{\mathrm{k}}_i,m))=\mathrm{1}。

\forall m\in {\{\mathrm{0,1}\}}^{\mathrm{*}},\forall t\le n,\forall (\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda }),

\forall \{{\sigma }_i\leftarrow \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{s}{\mathrm{k}}_i{,m)\}}_{i=\mathrm{1}}^t,\sigma \leftarrow \mathrm{A}\mathrm{g}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}(m,\{\mathrm{p}{\mathrm{k}}_i,{\sigma }_i{\}}_{i=\mathrm{1}}^t)可得到\mathrm{A}\mathrm{g}\mathrm{g}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\{\mathrm{p}{\mathrm{k}}_i,{\sigma }_i{\}}_{i=\mathrm{1}}^t,m,\sigma )=\mathrm{1}。

定义5 非交互式零知识证明^[11]

\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}=(\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p},\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{v}\mathrm{e},\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y})由以下三个算法组成。

1) \mathrm{p}\mathrm{p}\leftarrow \mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },\mathrm{ℛ})：以安全参数\lambda和关系\mathrm{ℛ}为输入，公共参数\mathrm{p}\mathrm{p}为输出。

2) \pi /\perp \leftarrow \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{v}\mathrm{e}(\mathrm{p}\mathrm{p},x,w)：以公共参数\mathrm{p}\mathrm{p}，实例x和见证者w为输入，如果\mathrm{ℛ}(x,w)=\mathrm{1}，则输出一个证明\pi；否则输出\perp。

3) \mathrm{1}/\mathrm{0}\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{p},x,\pi )：以公共参数\mathrm{p}\mathrm{p}，实例x和证明\pi为输入，输出\mathrm{1}/\mathrm{0}表示\pi是x的有效/无效证明。

\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}满足以下性质。

完整性 如果\mathrm{ℛ}(x,w)=\mathrm{1}，那么诚实的证明者\mathrm{𝒫}说服验证者V的概率可以忽略不计。如果\mathrm{ℛ}(x,w)=\mathrm{0}，证明输出是⊥。

零知识性 三元组(\mathrm{p}\mathrm{p},x,w)没有揭示关于见证者w的任何信息。

知识健全性 对于每一个{\mathrm{𝒫}}^{\mathrm{*}}，存在一个有效的算法，称为提取器，使得每当{\mathrm{𝒫}}^{\mathrm{*}}说服V输出1时，提取器可以使用{\mathrm{𝒫}}^{\mathrm{*}}输出w，使得\mathrm{ℛ}(x,w)=\mathrm{1}。

2　 方案设计

2.1　方案模型

多重宇宙^[7]是一个可能重叠的宇宙集合，每个宇宙都包含系统中各方的任意子集和特定的阈值。如图1所示，MTAPS方案包含五种角色：系统管理员、参与方、组合者、验证者和跟踪者。

方案模型框架如图1所示。主要流程如下：

1） 初始化阶段。系统管理员在多重宇宙中输入安全参数\lambda和包含零知识证明所需的所有关系，生成公共参数并初始化系统（①）。随后进行各方密钥生成和宇宙设置；宇宙中的参与方\{P_{\mathrm{1}},\dots ,P_n\}随机选择自己的私钥\mathrm{s}{\mathrm{k}}_i并发布相应的公钥\mathrm{p}{\mathrm{k}}_i（②），组合者生成自己的组合密钥对(\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})（③），跟踪者生成自己的跟踪密钥对(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}})（④），然后设置需要进行签名操作的单个宇宙（⑤）。

2） 签名生成阶段（⑥）。宇宙信息设置完成后，签名者可以在该宇宙进行签名。签名生成算法包括原始签名生成阶段，加密签名阶段以及零知识证明生成阶段。

3） 签名组合阶段（⑦）。组合者接收从签名者处得到的签名集合，并验证签名的有效性，验证通过后生成相应的证明，并对其进行签名。

4） 签名验证阶段（⑧）。验证者接收组合后的签名和相关证明，并对其进行验证。

5） 签名跟踪阶段（⑨）。在系统中，当签名信息与实际数据产生偏差时，通过生成的签名对签名者集合进行跟踪。

2.2　方案设计

威胁模型：在每个宇宙中，签名数量阈值t通常设定为参与者n^{\text{'}}的一半。攻击者可以针对多个参与者发起攻击，但其数量不得超过阈值。在DeFi系统中，尤其是当系统依赖预言机进行数据交互时，主要的问题往往出现在签名数据的错误性上，而恶意预言机的行为并不常见。攻击者虽然可以控制多个系统维护者，但无法破坏他们之间的共识，诚实的系统维护者仍能够有效地利用区块链作为公告板来进行维护。此外，攻击者不能破坏系统设计中所定义的安全属性，必须满足在选定消息攻击（EUF-CMA）下存在不可伪造性的标准概念。在该系统中，跟踪者被假设为诚实的。如果组合者收到来自可疑方的签名，可以将其传递给跟踪者以进行进一步监控。

MTAPS方案需满足以下目标：

1） 正确性。如果底层公钥加密方案\mathrm{P}\mathrm{K}\mathrm{E}、数字签名方案\mathrm{S}\mathrm{I}\mathrm{G}、聚合签名方案\mathrm{A}\mathrm{S}和非交互式零知识证明\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}正确，并满足DDH和CDH假设，则通用方案正确。

2） 不可伪造性。控制少于t个参与者的对手无法构建有效的消息签名对。

3） 责任性。控制t个或更多参与者的对手无法构造出一个有效的消息签名对，而有效的消息签名对至少能追踪到一个诚实的参与者。

4） 对公众的隐私性。只看到消息签名对序列的一方，无法得知对阈值t或创建这些签名的签名者。

5） 对签名者的隐私性。共同工作的所有签名者，可看到消息签名对的序列，但无法确定哪些签名者参与了这些签名的创建。

2.3　系统组件

假设共有n个参与者\{P_{\mathrm{1}},\dots ,P_n\}。每个参与者P_i\in \{P_{\mathrm{1}},\dots ,P_n\}通过密钥生成算法生成公钥和私钥(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)，P_i的身份由公钥\mathrm{p}{\mathrm{k}}_i标识。正式地，一个宇宙实例U被参数化为(n^{\text{'}},t,\mathbb{P}\mathbb{K})，在宇宙U内的n^{\text{'}}个参与方P^{\text{'}}=\{P_{\mathrm{1}}^{\mathrm{\text{'}}},\dots ,P_{n^{\text{'}}}^{\mathrm{\text{'}}}\}\subseteq \{P_{\mathrm{1}},\dots ,P_n\}，并且超过n^{\text{'}})个参与方可以代表宇宙生成有效的阈值签名。

MTAPS方案的通用构造包含9个算法，具体描述如下：

1） \mathrm{c}\mathrm{r}\mathrm{s}\leftarrow \mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },\mathrm{ℛ})：参数设置算法。输入安全参数\lambda和零知识证明的关系\mathrm{ℛ}后，经过处理后输出公共参数\mathrm{c}\mathrm{r}\mathrm{s}。在以下算法中，我们省略了\mathrm{c}\mathrm{r}\mathrm{s}作为输入。

2） (\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda })：参与方密钥生成算法。输入安全参数\lambda和宇宙中的n个参与方\{P_{\mathrm{1}},P_{\mathrm{2}},\dots ,P_n\}输出(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)。

3） (\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})\leftarrow \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda })：组合密钥生成算法。输入安全参数\lambda，组合者生成组合密钥对(\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})。

4） (\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}})\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda })：跟踪密钥生成算法。输入安全参数\lambda，跟踪者生成跟踪密钥对(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}})。

5） (\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}})\leftarrow \mathrm{U}\mathrm{S}\mathrm{e}\mathrm{t}\left({\mathrm{1}}^{\lambda },\mathbb{P}\mathbb{K},\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},n^{\text{'}},t\right)：宇宙设置算法。输入安全参数\lambda，全宇宙内所有参与者的公钥\mathbb{P}\mathbb{K}=\{\mathrm{p}{\mathrm{k}}_{\mathrm{1}}^{\mathrm{\text{'}}},\mathrm{p}{\mathrm{k}}_{\mathrm{2}}^{\mathrm{\text{'}}},\dots ,\mathrm{p}{\mathrm{k}}_{n^{\mathrm{\text{'}}}}^{\mathrm{\text{'}}}\}，跟踪公钥\mathrm{p}{\mathrm{k}}_{\mathrm{T}}，组合公钥\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}}和私钥\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}}，宇宙内参与者的数量n^{\text{'}}和阈值t，输出宇宙验证公钥\mathrm{V}\mathrm{p}\mathrm{k}和组合密钥\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}。

6） {\sigma }_i\leftarrow \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_i^{\mathrm{\text{'}}},m)：签名生成算法。输入跟踪者公钥\mathrm{p}{\mathrm{k}}_{\mathrm{T}}，该宇宙内签名者的公钥\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}}和私钥\mathrm{s}{\mathrm{k}}_i^{\mathrm{\text{'}}}以及消息m，输出每个签名者的部分签名{\sigma }_i。

7） \sigma \leftarrow \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}},m,\{{\sigma }_i{\}}_{i=\mathrm{1}}^t)：签名组合算法。输入宇宙验证公钥\mathrm{V}\mathrm{p}\mathrm{k}，组合密钥\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}，消息m和签名者的部分签名集\{{\sigma }_i{\}}_{i=\mathrm{1}}^t，输出一个MTAPS签名\sigma。

8） \mathrm{1}/\mathrm{0}\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{V}\mathrm{p}\mathrm{k},m,\sigma )：签名验证算法。输入宇宙验证公钥\mathrm{V}\mathrm{p}\mathrm{k}，消息m和MTAPS签名\sigma。输出\mathrm{1}/\mathrm{0}表示签名有效或无效。

9） S\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{T}},m,\sigma )：签名跟踪算法。输入宇宙验证公钥\mathrm{V}\mathrm{p}\mathrm{k}，跟踪私钥\mathrm{s}{\mathrm{k}}_{\mathrm{T}}，消息m和MTAPS签名\sigma。输出签名方的公钥集合S，该公钥集合可以揭示签名方的身份。

2.4　安全模型

2.4.1　不可伪造性和责任性

与其他签名方案一样，MTAPS方案必须满足不可伪造性的标准概念。此外，方案应该是负责任的。不可伪造性定义具有跟踪私钥\mathrm{s}{\mathrm{k}}_{\mathrm{T}}的跟踪者应该为给定的消息签名对输出正确的仲裁集\{\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}}{\}}_{i=\mathrm{1}}^t\subseteq \mathbb{P}\mathbb{K}以跟踪到对应的签名者。

游戏设置：设\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}^{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}(\lambda )为对手\mathrm{𝒜}=({\mathrm{𝒜}}_{\mathrm{0}},{\mathrm{𝒜}}_{\mathrm{1}})在不可伪造性和责任性攻击游戏中战胜MTAPS方案的概率。首先对手{\mathrm{𝒜}}_{\mathrm{0}}输出(n^{\text{'}},t,S,\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e})\stackrel{\mathrm{\$}}{\leftarrow }{\mathrm{𝒜}}_{\mathrm{0}}({\mathrm{1}}^{\lambda }),t\in [n^{\text{'}}]并且S\subseteq [n^{\text{'}}]，然后分别生成密钥(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda }),(\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})\leftarrow \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda }),(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}})\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda })，{\mathrm{𝒜}}_{\mathrm{1}}获得参与方、组合者和跟踪者的密钥，进入宇宙生成阶段获得\mathrm{V}\mathrm{p}\mathrm{k}和\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}，请求m_j的部分签名(m^{\text{'}},{\sigma }^{\text{'}})\stackrel{\mathrm{\$}}{\leftarrow }{\mathrm{𝒜}}_{\mathrm{1}}^{\mathrm{𝒪}(\cdot ,\cdot )}(\{\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i{\}}_{i\in S},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e})，查询签名预言机\mathrm{𝒪}(S_j,m_j)返回部分签名。

获胜条件：令(S_{\mathrm{1}},m_{\mathrm{1}}),(S_{\mathrm{2}},m_{\mathrm{2}}),\dots是{\mathrm{𝒜}}_{\mathrm{1}}对\mathrm{𝒪}的查询，令S^{\text{'}}\leftarrow \bigcup S_j，联合所有查询\mathrm{𝒪}(S_j,m^{\mathrm{\text{'}}})。如果没有这样的查询，则设置S^{\text{'}}\leftarrow \mathrm{\varnothing }。令S_t\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{T}},m^{\text{'}},{\sigma }^{\text{'}})，如果满足条件\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{V}\mathrm{p}\mathrm{k},m^{\text{'}},{\sigma }^{\text{'}})=\mathrm{1}且S_t⊈(S\bigcup S^{\text{'}})或者S_t=\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{l}，则输出1。

定义6（不可伪造性和责任性） 如果对于所有概率多项式时间对手\mathrm{𝒜}=({\mathrm{𝒜}}_{\mathrm{0}},{\mathrm{𝒜}}_{\mathrm{1}})，函数\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}^{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}(\lambda )是\lambda的可忽略函数，则MTAPS方案具有不可伪造性和责任性。

上述游戏说明了阈值签名方案的不可伪造性和责任性。在博弈过程中，对手获得S中各方的私钥，并从S中各方获得m^{\text{'}}的部分签名。攻击者应该无法生成导致跟踪算法失败的有效签名{\sigma }^{\text{'}}，或者导致跟踪算法将责任归咎于S\bigcup S^{\text{'}}之外的签名方。这说明了责任性。

在不可伪造性上，假设对手\mathrm{𝒜}获得的m^{\text{'}}的部分签名少于阈值t，这意味着。在其他情况下，攻击者能够产生一个有效的签名{\sigma }^{\text{'}}，导致跟踪算法归咎于某个群体S_t。由跟踪的定义可知|S^{\text{'}}|\ge t，因此S_t不能包含在S\bigcup S^{\text{'}}中。因此，对手成功地指责了诚实的一方，结果对手\mathrm{𝒜}赢得了比赛。因此，如果\mathrm{𝒜}无法赢得游戏，那么该方案必须是不可伪造的。

2.4.2　隐私性

MTAPS方案的隐私性通常通过要求消息m上的阈值签名与某些标准签名方案生成的m上的签名无法区分来定义。此属性确保阈值签名不会显示有关产生该签名的阈值和签名者的任何信息。隐私性定义为MTAPS方案的内在属性。在设计目标中，定义了MTAPS方案的两个隐私要求。

公众的隐私游戏：b\stackrel{\mathrm{\$}}{\leftarrow }\{\mathrm{0,1}\}，首先{\mathrm{𝒜}}_{\mathrm{0}}输出(n^{\text{'}},t_{\mathrm{0}},t_{\mathrm{1}},\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e})\stackrel{\mathrm{\$}}{\leftarrow }{\mathrm{𝒜}}_{\mathrm{0}}\left({\mathrm{1}}^{\lambda }\right),t_{\mathrm{0}},t_{\mathrm{1}}\in [n^{\text{'}}]，然后分别生成密钥(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda }),(\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})\leftarrow \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda }),(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}})\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda })，进入宇宙生成阶段获得\mathrm{V}\mathrm{p}\mathrm{k}和\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}，b^{\text{'}}\leftarrow {\mathrm{𝒜}}_{\mathrm{1}}^{{\mathrm{𝒪}}_{\mathrm{1}}(\cdot ,\cdot ),{\mathrm{𝒪}}_{\mathrm{2}}(\cdot ,\cdot )}(\mathbb{P}\mathbb{K}=\{\mathrm{p}{\mathrm{k}}_{\mathrm{1}}^{\mathrm{\text{'}}},\dots ,\mathrm{p}{\mathrm{k}}_{n^{\text{'}}}^{\mathrm{\text{'}}}\},\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e})，输出b=b^{\text{'}}，查询签名预言机{\mathrm{𝒪}}_{\mathrm{1}}(S_{\mathrm{0}},S_{\mathrm{1}},m)返回\sigma \stackrel{\mathrm{\$}}{\leftarrow }\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}},m,\{\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_i^{\mathrm{\text{'}}}{,m)\}}_{i\in S_b})对于S_{\mathrm{0}},S_{\mathrm{1}}\subseteq [n^{\text{'}}]且|S_{\mathrm{0}}|=t_{\mathrm{0}}与|S_{\mathrm{1}}|=t_{\mathrm{1}}，{\mathrm{𝒪}}_{\mathrm{2}}(m,\sigma )返回\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{T}},m,\sigma )。限制条件为如果\sigma是从查询{\mathrm{𝒪}}_{\mathrm{1}}(\cdot ,\cdot ,m)中获得的，那么{\mathrm{𝒪}}_{\mathrm{2}}永远不会在(m,\sigma )处查询。

签名者的隐私游戏：\stackrel{\mathrm{\$}}{b\leftarrow \{\mathrm{0,1}\}}，首先{\mathrm{𝒜}}_{\mathrm{0}}输出(n^{\text{'}},t,\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e})\stackrel{\mathrm{\$}}{\leftarrow }{\mathrm{𝒜}}_{\mathrm{0}}({\mathrm{1}}^{\lambda })，然后分别生成密钥(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda }),(\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})\leftarrow \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda }),(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}})\leftarrow\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda })，进入宇宙生成阶段获得\mathrm{V}\mathrm{p}\mathrm{k}和\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}，{\mathrm{𝒜}}_{\mathrm{1}}发出签名和跟踪查询b^{\text{'}}\leftarrow {\mathrm{𝒜}}_{\mathrm{1}}^{{\mathrm{𝒪}}_{\mathrm{1}}(\cdot ,\cdot ),{\mathrm{𝒪}}_{\mathrm{2}}(\cdot ,\cdot )}(\mathbb{P}\mathbb{K},\{\mathrm{s}{\mathrm{k}}_{\mathrm{1}}^{\mathrm{\text{'}}},\dots ,\mathrm{s}{\mathrm{k}}_{n^{\text{'}}}^{\mathrm{\text{'}}}\},\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e})，输出b=b^{\text{'}}，其中{\mathrm{𝒪}}_{\mathrm{1}}(S_{\mathrm{0}},S_{\mathrm{1}},m)，返回\sigma \stackrel{\mathrm{\$}}{\leftarrow }\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}},m,\{\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_i^{\mathrm{\text{'}}}{,m)\}}_{i\in S_b})，对于S_{\mathrm{0}},S_{\mathrm{1}}\subseteq [n^{\text{'}}]且|S_{\mathrm{0}}|=|S_{\mathrm{1}}|=t，查询跟踪预言机{\mathrm{𝒪}}_{\mathrm{2}}(m,\sigma )返回\mathrm{T}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{T}},m,\sigma )。限制条件为如果\sigma是从查询{\mathrm{𝒪}}_{\mathrm{1}}(\cdot ,\cdot ,m)中获得的，那么{\mathrm{𝒪}}_{\mathrm{2}}永远不会在(m,\sigma )处查询。

设W对公众的隐私游戏输出1的事件。类似地，设W^{\text{'}}对签名者的游戏隐私输出1的事件。定义了MTAPS方案的对手\mathrm{𝒜}的两个优势函数，作为安全参数\lambda的函数。

\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}^{\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{1}}(\lambda )=|\mathrm{2}\mathrm{P}\mathrm{r}[W]-\mathrm{1}|;

\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}^{\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{2}}(\lambda )=|\mathrm{2}\mathrm{P}\mathrm{r}[W^{\text{'}}]-\mathrm{1}|

定义7（隐私性） 如果对于所有概率多项式时间公共对手\mathrm{𝒜}=({\mathrm{𝒜}}_{\mathrm{0}},{\mathrm{𝒜}}_{\mathrm{1}})，函数\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathbf{M}\mathbf{T}\mathbf{A}\mathbf{P}\mathbf{S}}^{\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{1}}(\lambda )和\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathbf{M}\mathbf{T}\mathbf{A}\mathbf{P}\mathbf{S}}^{\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{2}}(\lambda )是\lambda的可忽略函数，则MTAPS方案是隐私性的。

上述游戏说明了阈值签名方案的隐私性。攻击者在宇宙中选择两个阈值t_{\mathrm{0}}和t_{\mathrm{1}}，然后向签名预言机发出一系列签名查询，其中每个签名查询包括一条消息m和两个序列S_{\mathrm{0}}和S_{\mathrm{1}}。攻击者获得使用左序列或右序列生成的签名。我们还允许攻击者访问受限制的跟踪预言机{\mathrm{𝒪}}_{\mathrm{2}}，它将跟踪有效的消息签名对。对手应该无法确定它所看到的签名序列是相对于法定人数的左序列还是相对于法定人数的右序列。对隐私的定义确保阈值t是隐藏的。签名者的隐私是使用游戏定义的。然而，在这里，攻击者选择阈值t，并获得所有签名密钥。同样，攻击者应该无法确定采用两个签名者集合S_{\mathrm{0}}和S_{\mathrm{1}}的签名预言机{\mathrm{𝒪}}_{\mathrm{1}}是否使用左序列或右序列进行响应。和前面一样，攻击者可以访问受限制的跟踪预言机{\mathrm{𝒪}}_{\mathrm{2}}。

2.5　方案流程

MTAPS方案主要包括以下5个阶段。

1） 初始化阶段：初始化阶段具体可以分为系统初始化阶段和宇宙信息初始化阶段。设{\mathbb{G}}_{\mathrm{1}},{\mathbb{G}}_{\mathrm{2}}为q阶群，{\mathbb{G}}_{\mathrm{T}}为目标群。我们用g_{\mathrm{1}}和h，g_{\mathrm{2}}，g_{\mathrm{T}}分别表示{\mathbb{G}}_{\mathrm{1}},{\mathbb{G}}_{\mathrm{2}}和{\mathbb{G}}_{\mathrm{T}}的生成元。存在一个有效可计算且不退化的双线性映射e:{\mathbb{G}}_{\mathrm{1}}\mathrm{*}{\mathbb{G}}_{\mathrm{2}}\to {\mathbb{G}}_{\mathrm{T}}。假设为系统中所有参与方的集合。在DeFi系统中，预言机相当于系统模型中的参与方，以下用预言机进行表述；设H:{\{\mathrm{0,1}\}}^{\mathrm{*}}\to {\mathbb{G}}_{\mathrm{1}}是一个随机预言机；设{\mathbb{Z}}_q是环\mathbb{Z}/q\mathbb{Z}，q\leftarrow {\{\mathrm{0,1}\}}^{\lambda }。

（a） 系统初始化：在系统初始化阶段，系统维护者为区块链系统生成公共参数，并将其记录在公告板（如区块链）中。在不损失安全性的情况下，假设系统维护者专门将区块链作为公告板维护。

\mathrm{c}\mathrm{r}\mathrm{s}\leftarrow \mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },\mathrm{ℛ})：参数设置算法。系统管理员协商安全参数\lambda，然后调用算法\mathrm{c}\mathrm{r}\mathrm{s}\leftarrow \mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}.\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },\mathrm{ℛ})，生成公共参数\mathrm{c}\mathrm{r}\mathrm{s}。

（b） 宇宙信息初始化：多重宇宙被定义为一个可能重叠的宇宙集合，每个宇宙包含所有各方的任意子集\{P_{\mathrm{1}}^{\mathrm{\text{'}}},P_{\mathrm{2}}^{\mathrm{\text{'}}},\dots ,P_{n^{\text{'}}}^{\mathrm{\text{'}}}\}和一个特定的阈值t。宇宙信息初始化阶段包括各方密钥生成以及宇宙设置。

(\mathrm{p}{\mathrm{k}}_i,\mathrm{s}{\mathrm{k}}_i)\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda })：参与方密钥生成算法。每当新的预言机P_i进入系统时，它选择私钥\mathrm{s}{\mathrm{k}}_i\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_q，计算并发布相应的公钥\mathrm{p}{\mathrm{k}}_i=g_{\mathrm{2}}^{\mathrm{s}{\mathrm{k}}_i}。

(\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})\leftarrow \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda })：组合密钥生成算法。根据(\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})\leftarrow \mathrm{S}\mathrm{I}\mathrm{G}.\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}({\mathrm{1}}^{\lambda })生成自己的签名密钥对(\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}})。

(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}})\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{K}\mathrm{e}\mathrm{y}({\mathrm{1}}^{\lambda })：跟踪密钥生成算法。跟踪者选取私钥\mathrm{s}{\mathrm{k}}_{\mathrm{T}}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_q，并计算\mathrm{p}{\mathrm{k}}_{\mathrm{T}}\leftarrow g_{\mathrm{1}}^{\mathrm{s}{\mathrm{k}}_{\mathrm{T}}}生成自己的跟踪密钥对(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{s}{\mathrm{k}}_{\mathrm{T}})。

(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}})\leftarrow \mathrm{U}\mathrm{S}\mathrm{e}\mathrm{t}\left({\mathrm{1}}^{\lambda },\mathrm{P}\mathrm{K},\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},n^{\text{'}},t\right)：宇宙设置算法。各方密钥生成完成后，在线各方共同进入宇宙设置阶段。宇宙设置将分为以下四个部分。首先设置特定的参与预言机和阈值。在某一个特定的宇宙中，为与整个系统中的n个预言机进行区分，将该宇宙中的参与阈值签名的预言机总数量设置为n^{\text{'}}并且将阈值设置为t。其次加密隐私信息。由于阈值t是对公众保密的隐私信息，所以需要使用ElGamal加密算法对其进行加密，该过程为首先选取随机盲化因子\psi \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_q，然后通过计算T_{\mathrm{0}}=g_{\mathrm{1}}^{\psi }，T_{\mathrm{1}}=g_{\mathrm{1}}^t{h}^{\psi }生成阈值t的密文(T_{\mathrm{0}},T_{\mathrm{1}})\leftarrow (g_{\mathrm{1}}^{\psi },g_{\mathrm{1}}^t{h}^{\psi })。接着生成宇宙验证公钥。宇宙验证公钥包含了宇宙内所有的公开信息，这将用于后续的签名组合阶段，签名验证阶段以及签名跟踪阶段。设置宇宙验证公钥为\mathrm{V}\mathrm{p}\mathrm{k}\leftarrow (\mathbb{P}\mathbb{K},\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},T_{\mathrm{0}},T_{\mathrm{1}})，其中\mathbb{P}\mathbb{K}=\{\mathrm{p}{\mathrm{k}}_{\mathrm{1}}^{\mathrm{\text{'}}},\mathrm{p}{\mathrm{k}}_{\mathrm{2}}^{\mathrm{\text{'}}},\dots ,\mathrm{p}{\mathrm{k}}_{n^{\mathrm{\text{'}}}}^{\mathrm{\text{'}}}\}是该宇宙内所有参与预言机的公钥集合，并且|\mathbb{P}\mathbb{K}|=n^{\text{'}}，\mathrm{p}{\mathrm{k}}_{\mathrm{T}}是跟踪者的跟踪公钥，\mathrm{p}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}}是组合者的签名公钥，(T_{\mathrm{0}},T_{\mathrm{1}})是阈值t加密后的密文。最后生成组合者的组合密钥。组合者的组合密钥将用于后续的签名组合阶段。设置组合者的组合密钥为\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}\leftarrow (\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},t,\psi )，其中\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}}是组合者的签名私钥，t是该宇宙的特定阈值，\psi是用于加密的随机盲化因子。

2） 签名生成阶段：宇宙信息设置完成后，签名者可以在该宇宙进行签名生成。

{\sigma }_i\leftarrow \mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_i^{\mathrm{\text{'}}},m)：签名生成算法。分为原始签名生成阶段和加密签名阶段。

步骤一：在不失一般性的情况下，假设t个预言机\{P_{\mathrm{1}}^{\mathrm{\text{'}}},P_{\mathrm{2}}^{\mathrm{\text{'}}},\dots ,P_t^{\mathrm{\text{'}}}\}作为签名者队列使用他们自己的私钥\{\mathrm{s}{\mathrm{k}}_{\mathrm{1}}^{\mathrm{\text{'}}},\mathrm{s}{\mathrm{k}}_{\mathrm{2}}^{\mathrm{\text{'}}},\dots ,\mathrm{s}{\mathrm{k}}_t^{\mathrm{\text{'}}}\}对消息m进行签名，每个签名者计算部分签名{\sigma }_i^{\mathrm{\text{'}}}=H{(m)}^{\mathrm{s}{\mathrm{k}}_i^{\mathrm{\text{'}}}}\in {\mathbb{G}}_{\mathrm{2}}，从而得到原始签名集\left\{{\sigma }_{\mathrm{1}}^{\text{'}},{\sigma }_{\mathrm{2}}^{\text{'}},\cdots ,{\sigma }_t^{\text{'}}\right\}。

步骤二：签名者使用跟踪公钥\mathrm{p}{\mathrm{k}}_{\mathrm{T}}对自己的部分签名{\sigma }_i^{\mathrm{\text{'}}}进行加密，选取\varphi \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_q，计算密文c_i:=(c_{\mathrm{0}},d_i)=(g_{\mathrm{1}}^{\varphi },{\sigma }_i^{\mathrm{\text{'}}}\mathrm{p}{\mathrm{k}}_{\mathrm{T}}^{\varphi })，然后生成满足关系{\mathrm{ℛ}}_{\mathrm{1}}(x_{\mathrm{1}},w_{\mathrm{1}})的{\pi }_i\leftarrow \mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}.\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{v}\mathrm{e}(\mathrm{c}\mathrm{r}\mathrm{s},x_{\mathrm{1}},w_{\mathrm{1}})相应的零知识证明，其中x_{\mathrm{1}}=(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},m,c_i),w_{\mathrm{1}}=(\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}},{\sigma }_i^{\mathrm{\text{'}}},\varphi )，如公式(1)所示，以证明{\sigma }_i^{\mathrm{\text{'}}}是在消息m上生成的有效签名，密文c_i的解密是在消息m上生成的有效签名。最后输出每个签名者的加密签名c_i及其相应的零知识证明{\pi }_i。

{\pi }_i\leftarrow \mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}\{(\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}},{\sigma }_i^{\mathrm{\text{'}}},\varphi ):e({\sigma }_i^{\mathrm{\text{'}}},g_{\mathrm{1}})=

e(H(m),\mathrm{p}{\mathrm{k}}_i^{\mathrm{\text{'}}})\wedge c_{\mathrm{0}}=g_{\mathrm{1}}^{\varphi }\wedge d_i={\sigma }_i^{\mathrm{\text{'}}}\mathrm{p}{\mathrm{k}}_{\mathrm{T}}^{\varphi })\}(1)

3） 签名组合阶段：组合者接收从签名者处得到的签名集合，由于签名被加密保护签名者的身份隐私，所以传统的秘密共享方案并不适用，因此通过组合者进行阈值判断，并验证签名有效性再组合。

\sigma \leftarrow \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}},m,\{{\sigma }_i{\}}_{i=\mathrm{1}}^t)：签名组合算法。

步骤一：如公式(2)所示，组合者确认\{{\pi }_i{\}}_{i=\mathrm{1}}^t是从签名者得到的有效证明，如果验证通过，则为验证的签名生成一个集合Y=Y\cup \{{\sigma }_i\}，最终得到Y=\{{\sigma }_i{\}}_{i=\mathrm{1}}^t，其中{\sigma }_i由c_i和{\pi }_i组成。

\forall i\in \{\mathrm{1},\cdots ,t\},\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}.\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{c}\mathrm{r}\mathrm{s},(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},m,c_i),{\pi }_i)=\mathrm{1}(2)

步骤二：如公式(3)所示，组合者生成一个满足关系{\mathrm{ℛ}}_{\mathrm{2}}(x_{\mathrm{2}},w_{\mathrm{2}})的零知识证明，证明它知道阈值t的隐私信息和签名集的大小不小于t，其中x_{\mathrm{2}}=(T_{\mathrm{0}},T_{\mathrm{1}},Y)w_{\mathrm{2}}=(\psi ,t)。

\pi \leftarrow \mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}\{(\psi ,t):(T_{\mathrm{0}}=g_{\mathrm{1}}^{\psi }\wedge T_{\mathrm{1}}=g_{\mathrm{1}}^t{h}^{\psi })\wedge |Y|\ge t\}(3)

步骤三：组合者用自己的签名密钥\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}}在三元组(m,Y,\pi )上签名，\mathrm{t}\mathrm{s}\leftarrow \mathrm{S}\mathrm{I}\mathrm{G}.\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{s}{\mathrm{k}}_{\mathrm{c}\mathrm{s}}^{\mathrm{\text{'}}},(m,Y,\pi ))，并输出一个MTAPS签名\sigma，它是\sigma \leftarrow (Y,\pi ,\mathrm{t}\mathrm{s})的三元组。

4） 签名验证阶段：验证者接收组合后的签名和相关证明，对其进行验证。

\mathrm{1}/\mathrm{0}\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{V}\mathrm{p}\mathrm{k},m,\sigma )：签名验证算法。验证者根据\mathrm{1}/\mathrm{0}\leftarrow \mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}.\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{c}\mathrm{r}\mathrm{s},(\mathrm{p}{\mathrm{k}}_{\mathrm{T}},m,c_i),{\pi }_i)检查集合Y中的签名是否有效。如果验证失败，则说明组合者行为存在问题，输出了无效签名，以此追究组合者的责任。如果验证通过，验证者再通过算法\mathrm{1}/\mathrm{0}\leftarrow \mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}.\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{c}\mathrm{r}\mathrm{s},(T_{\mathrm{0}},T_{\mathrm{1}},Y),\pi )确认\pi是满足关系{\mathrm{ℛ}}_{\mathrm{2}}(x_{\mathrm{2}},w_{\mathrm{2}})的有效证明，并对三元组(m,Y,\pi )上的组合者签名\mathrm{t}\mathrm{s}进行验证，如果签名有效则输出1，否则输出0。

通常，在此阶段签名过程已经完成。然而，由于DeFi系统中应用的特殊性，签名的消息有时与实际数据存在偏差，需要对签名者进行跟踪。

5） 签名跟踪阶段：在系统中，如果签名信息与实际数据有偏差，则对签名者集合进行跟踪。

S\leftarrow \mathrm{T}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}(\mathrm{V}\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{T}},m,\sigma )：签名跟踪算法。跟踪者应该通过调用验证算法\mathrm{1}/\mathrm{0}\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{V}\mathrm{p}\mathrm{k},m,\sigma )对组合者的行为进行验证。如果验证失败，则表明组合者行为无效，对组合者进行追责。否则，跟踪者使用跟踪密钥\mathrm{s}{\mathrm{k}}_{\mathrm{T}}对集合Y中签名的密文c_i:=(c_{\mathrm{0}},d_i)=(g_{\mathrm{1}}^{\varphi },{\sigma }_i^{\mathrm{\text{'}}}\mathrm{p}{\mathrm{k}}_{\mathrm{T}}^{\varphi })，通过计算{\sigma }_i^{\mathrm{\text{'}}}=d_i(c_{\mathrm{0}}^{\mathrm{s}{\mathrm{k}}_{\mathrm{T}}}{)}^{-\mathrm{1}}进行解密，得到原始的部分签名集合\{{\sigma }_i^{\mathrm{\text{'}}}{\}}_{i=\mathrm{1}}^t。

最后，跟踪者使用宇宙参与者的公钥\mathbb{P}\mathbb{K}，消息m，签名集合\{{\sigma }_i^{\mathrm{\text{'}}}{\}}_{i=\mathrm{1}}^t来跟踪签名者。对于集合\{{\sigma }_i^{\mathrm{\text{'}}}{\}}_{i=\mathrm{1}}^t中的每个签名，遍历公钥\mathbb{P}\mathbb{K}，找到满足e({\sigma }_i^{\mathrm{\text{'}}},g_{\mathrm{1}})=e(H(m),\mathrm{p}\mathrm{k})的\mathrm{p}\mathrm{k}，然后将\mathrm{p}\mathrm{k}添加到S中。输出S中签名参与者的公钥可以显示他们的身份，进而输出了签名者集合，完成跟踪。

3　 安全性分析

3.1　正确性

MTAPS方案的正确性是指在各方都正确执行自己算法的情况下，MTAPS签名能够被签名验证者有效验证，并且可以被签名追责者准确追责。各方调用执行的底层算法的正确性在基础知识部分给出了分析，根据此可以得出方案是正确的。

3.2　其他属性分析

定理1 如果MTAPS方案的底层BLS签名方案是安全的，签名方案\mathrm{S}\mathrm{I}\mathrm{G}具有强不可伪造性，DDH假设在群{\mathbb{G}}_{\mathrm{1}}中成立，并且非交互式零知识证明\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}对于关系{\mathrm{ℛ}}_{\mathrm{1}}和{\mathrm{ℛ}}_{\mathrm{2}}满足知识性论证和诚实验证者的零知识性，则MTAPS方案具有不可伪造性、可追责性和隐私性。

要使得定理1证明成功，等价于证明引理1，引理2和引理3。

引理1 如果MTAPS方案的底层BLS方案是安全的，并且非交互式零知识证明\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}对于关系{\mathrm{ℛ}}_{\mathrm{1}}和{\mathrm{ℛ}}_{\mathrm{2}}满足知识性论证，则MTAPS方案具有不可伪造性和可追责性。具体来说，即对于任何攻击MTAPS方案的敌手\mathrm{𝒜}，会存在一个和\mathrm{𝒜}运行相同时间的敌手\mathrm{ℬ}，有：\mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}^{\mathrm{𝒜},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}(\lambda )\le \mathrm{A}\mathrm{d}{\mathrm{v}}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}^{\mathrm{ℬ},\mathrm{B}\mathrm{L}\mathrm{S}}(\lambda )\cdot q(\lambda )+\kappa (\lambda )，其中q(\lambda )是敌手\mathrm{𝒜}查询零知识证明系统的次数；\kappa (\lambda )是非交互式零知识证明的知识误差。

证 \mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{0}}：此游戏是2.4节中定义的有关MTAPS签名的不可伪造性和责任性的安全游戏。在该安全游戏中，敌手\mathrm{𝒜}试图通过伪造签名或者破坏签名的责任性来获取游戏的胜利，为此定义敌手\mathrm{𝒜}在该游戏中取得胜利的优势为：\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}^{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}(\lambda )=\mathrm{P}\mathrm{r}[W_{\mathrm{0}}]，其中W_{\mathrm{0}}表示敌手\mathrm{𝒜}赢得游戏\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{0}}。

\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{1}}：\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{1}}和\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{0}}基本一致，唯一的修改就是要求敌手不仅要成功伪造一个有效的消息和签名对(m^{\text{'}},{\sigma }^{\text{'}})，还需要提供用于有效验证满足关系{\mathrm{ℛ}}_{\mathrm{1}}和{\mathrm{ℛ}}_{\mathrm{2}}的见证w_{\mathrm{1}}和w_{\mathrm{2}}，其操作过程主要是基于\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{0}}中的敌手\mathrm{𝒜}构建\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{1}}中的敌手{\mathrm{𝒜}}^{\text{'}}。{\mathrm{𝒜}}^{\text{'}}像\mathrm{𝒜}一样向挑战者\mathrm{𝒞}发起签名问询，直到能够伪造出一个消息和签名对(m^{\text{'}},{\sigma }^{\text{'}})，并构建有效的关于关系{\mathrm{ℛ}}_{\mathrm{1}}的公共实例x_{\mathrm{1}}和关系{\mathrm{ℛ}}_{\mathrm{2}}的公共实例x_{\mathrm{2}}。然后\mathrm{𝒜}运行非交互式零知识证明提取器算法^[11]以生成见证w_{\mathrm{1}}和w_{\mathrm{2}}，如果w_{\mathrm{1}}和w_{\mathrm{2}}均是有效见证，则由\mathrm{𝒜}通过组合者密钥\mathrm{s}{\mathrm{k}}_{cs}^{\mathrm{\text{'}}}生成{\mathrm{ℛ}}_{\mathrm{2}}关系的证明{\pi }^{\text{'}}和相应的签名\mathrm{t}{\mathrm{s}}^{\text{'}}。最后输出消息签名对(m^{\text{'}},{\sigma }^{\text{'}})。所以在该安全游戏中，敌手{\mathrm{𝒜}}^{\text{'}}在敌手\mathrm{𝒜}的基础上再提供一个有效的关于{\mathrm{ℛ}}_{\mathrm{2}}关系的见证来获取游戏的胜利，我们定义敌手{\mathrm{𝒜}}^{\text{'}}在该游戏中取得胜利的优势为\mathbf{A}\mathbf{d}{\mathbf{v}}_{{\mathrm{𝒜}}^{\text{'}},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}^{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}(\lambda )=\mathrm{P}\mathrm{r}[W_{\mathrm{1}}]，其中W_{\mathrm{1}}表示敌手{\mathrm{𝒜}}^{\text{'}}赢得\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{1}}。

根据提取器算法^[11]的定义，\mathrm{P}\mathrm{r}[W_{\mathrm{1}}]\ge (\mathrm{P}\mathrm{r}[W_{\mathrm{0}}]-\kappa (\lambda ))/q(\lambda )，这样就成功地将敌手{\mathrm{𝒜}}^{\text{'}}赢得\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{1}}的优势与敌手\mathrm{𝒜}赢得\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{0}}的优势相联系。此外，假设敌手{\mathrm{𝒜}}^{\text{'}}能赢得了游戏\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{1}}，那么相当于敌手{\mathrm{𝒜}}^{\text{'}}能成功伪造出基于BLS签名的有效消息和签名，这也表明我们同样可以以敌手{\mathrm{𝒜}}^{\text{'}}来构建一个以相同优势攻破BLS方案的敌手\mathrm{ℬ}，即\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{B},\mathrm{B}\mathrm{L}\mathrm{S}}^{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}(\lambda )\ge \mathrm{P}\mathrm{r}[W_{\mathrm{1}}]。至此，可以将MTAPS方案的安全性与BLS方案的安全性联系。如果BLS方案是安全的，那么敌手\mathrm{ℬ}攻破BLS方案的优势是可忽略的，即\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{B},\mathrm{B}\mathrm{L}\mathrm{S}}^{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}(\lambda )\le \mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}(\lambda )，因此推导出：

\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{ℬ},\mathrm{B}\mathrm{L}\mathrm{S}}^{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}(\lambda )\ge \mathrm{P}\mathrm{r}[W_{\mathrm{1}}]\ge (\mathrm{P}\mathrm{r}[W_{\mathrm{0}}]-\kappa (\lambda ))/q(\lambda )

\mathrm{P}\mathrm{r}[W_{\mathrm{0}}]\le \mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{ℬ},\mathrm{B}\mathrm{L}\mathrm{S}}^{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{g}}(\lambda )\cdot q(\lambda )+\kappa (\lambda )=\mathrm{n}\mathrm{e}\mathrm{g}\mathrm{l}(\lambda )

以上证明过程说明了MTAPS方案具有不可伪造性和可追责性。至此引理2证明完毕。

引理2 如果DDH假设在群{\mathbb{G}}_{\mathrm{1}}中成立，同时非交互式零知识证明\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}对于关系{\mathrm{ℛ}}_{\mathrm{1}}和{\mathrm{ℛ}}_{\mathrm{2}}满足诚实验证者的零知识性（HVZK），并且签名方案\mathrm{S}\mathrm{I}\mathrm{G}具有强不可伪造性，则MTAPS方案具有对公众的隐私性。具体而言，对于任何攻击MTAPS方案的敌手\mathrm{𝒜}，都存在和\mathrm{𝒜}运行时间相同的敌手{\mathrm{ℬ}}_{\mathrm{1}},{\mathrm{ℬ}}_{\mathrm{2}},{\mathrm{ℬ}}_{\mathrm{3}}，并有：\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}^{\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{1}}(\lambda )\le \mathrm{2}\left(\mathbf{A}\mathbf{d}{\mathbf{v}}_{{\mathrm{ℬ}}_{\mathrm{1}},SIG}^{\mathrm{e}\mathrm{u}\mathrm{f}\mathrm{c}\mathrm{m}\mathrm{a}}(\lambda )+Q\cdot \mathbf{A}\mathbf{d}{\mathbf{v}}_{{\mathrm{ℬ}}_{\mathrm{2}},\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}}^{\mathrm{h}\mathrm{v}\mathrm{z}\mathrm{k}}(\lambda )+(Q+\mathrm{1})\cdot \mathbf{A}\mathbf{d}{\mathbf{v}}_{{\mathrm{ℬ}}_{\mathrm{3}},{\mathbb{G}}_{\mathrm{1}}}^{\mathrm{d}\mathrm{d}\mathrm{h}}(\lambda )\right)。其中，Q是敌手\mathrm{𝒜}进行签名查询的总次数；Q+\mathrm{1}表示敌手\mathrm{𝒜}的查询次数加上一次最终的挑战查询。

引理3 如果DDH假设在群{\mathbb{G}}_{\mathrm{1}}中成立，同时非交互式零知识证明\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}对于关系{\mathrm{ℛ}}_{\mathrm{1}}和{\mathrm{ℛ}}_{\mathrm{2}}满足诚实验证者的零知识性（HVZK），并且签名方案\mathrm{S}\mathrm{I}\mathrm{G}具有强不可伪造性，则MTAPS方案具有对内部签名者的隐私性。具体而言，对于任何攻击方案的敌手\mathrm{𝒜}，都存在和\mathrm{𝒜}运行时间相同的敌手{\mathrm{ℬ}}_{\mathrm{1}},{\mathrm{ℬ}}_{\mathrm{2}},{\mathrm{ℬ}}_{\mathrm{3}}，并有：\mathbf{A}\mathbf{d}{\mathbf{v}}_{\mathrm{𝒜},\mathrm{M}\mathrm{T}\mathrm{A}\mathrm{P}\mathrm{S}}^{\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{2}}(\lambda )\le \mathrm{2}\left(\mathbf{A}\mathbf{d}{\mathbf{v}}_{{\mathrm{ℬ}}_{\mathrm{1}},\mathrm{S}\mathrm{I}\mathrm{G}}^{\mathrm{e}\mathrm{u}\mathrm{f}\mathrm{c}\mathrm{m}\mathrm{a}}(\lambda )+Q\cdot \mathbf{A}\mathbf{d}{\mathbf{v}}_{{\mathrm{ℬ}}_{\mathrm{2}},\mathrm{N}\mathrm{I}\mathrm{Z}\mathrm{K}\mathrm{P}}^{\mathrm{h}\mathrm{v}\mathrm{z}\mathrm{k}}(\lambda )+(Q+\mathrm{1})\cdot \mathbf{A}\mathbf{d}{\mathbf{v}}_{{\mathrm{ℬ}}_{\mathrm{3}},{\mathbb{G}}_{\mathrm{1}}}^{\mathrm{d}\mathrm{d}\mathrm{h}}(\lambda )\right)。

对引理2和3的证明可以参考引理1，碍于篇幅，不再赘述。

4　 实验评估

4.1　实验环境

实验采用Python语言编写，版本为3.8，操作系统为Ubuntu 20.04，内存16 GB RAM，CPU为Core(TM) i7-8700 CPU @3.20 GHz。

4.2　方案对比

为了全面展示MTAPS方案的功能特性，将其与阈值BLS^[1]、TAPS^[5]、MTS^[7]方案进行比较。如表1所示，传统BLS方案不能同时具备隐私性和责任性，本文列举的是仅具有隐私性的情况；TAPS方案首次提出具有隐私和责任的阈值签名概念，但没有考虑到多重宇宙的场景需求；而MTS方案关注到DeFi系统中不同场景对预言机需求的不同，抽象出多重宇宙的概念，却忽略了对预言机的隐私性保护，因此上述方案要么只能满足一个属性，要么只能满足两个属性，本文的方案可以同时满足三个属性，因此更加全面。

4.3　性能分析

本文主要考虑阈值对MTAPS方案效率的影响，性能测试包含两部分实验，一部分是使用不同的阈值测试本方案各个阶段的算法运行效率，另一部分是将MTAPS方案与其他方案签名主要阶段的算法运行效率进行对比。

4.3.1　各个阶段的算法运行效率分析

为了还原DeFi系统的实际情况，本文设置的签名数量阈值以5个节点起步。图2给出了本文方案各个阶段算法运行时间。可以看出，密钥生成阶段、签名生成阶段、签名组合阶段、签名验证阶段以及签名跟踪阶段的算法运行时间均随着阈值的增加而增加，而宇宙的设置阶段时间相对恒定。

在密钥生成阶段，组合者、跟踪者以及参与者都需要进行密钥生成，由于一个宇宙中只有一个组合者和一个跟踪者，因此影响密钥生成时间的主要因素是参与者的数量n^{\text{'}}，密钥生成时间随参与者数量增加而增加。签名各个阶段中涉及了零知识证明的生成与验证，零知识证明的操作时间随阈值增加而增加，因此签名各个阶段表现出的执行时间相应更长。在宇宙设置阶段，所需的时间主要包括加密私有信息所需的时间和设置多个密钥所需的时间，由于加密操作的高效性，时间相对恒定。

此外，对签名跟踪阶段进行实验分析，如图3所示，MTAPS方案中签名跟踪阶段所需的时间包括调用算法、解密算法和跟踪算法的时间。实验结果表明，解密算法和跟踪算法时间几乎是恒定的。影响跟踪阶段总时间的因素是验证算法的调用，单从跟踪算法效率而言，随着宇宙阈值的增加，签名跟踪阶段的跟踪时间几乎没有明显的变化，表明它是有效的跟踪。

4.3.2　签名主要阶段效率对比分析

Chainlink是一个主流的预言机系统，DeFi系统的数据广泛依赖于预言机。目前Chainlink^[5]中的阈值签名主要利用BLS签名和Schnorr签名实现。由于多重宇宙背景采用BLS签名作为基础，因此基于Schnorr签名的TAPS方案不在比较范围内。本文主要将阈值BLS ^[1]方案和MTS^[7]方案在签名组合阶段和签名验证阶段进行比较，结果如图4所示。实验中，阈值仍从5个开始设置，以符合DeFi系统的实际情况。

MTS^[7]方案适用于多重宇宙，具有责任性而不具有隐私性，而阈值BLS^[1]方案为传统的BLS阈值方案，具备隐私性而不具备责任性；由于本文方案需要通过零知识证明实现隐私性和责任性的兼容，所以在时间开销上稍大。

在签名组合阶段，MTAPS方案所需的时间包括验证签名者生成的零知识证明，以及生成新的零知识证明并对有效信息进行签名的时间。其中最重要的时间开销是验证零知识证明所花费的时间，它随着宇宙阈值的增加而增加，图4中MTAPS方案在签名组合阶段的时间变化趋势与验证零知识证明的时间基本一致。相比之下，阈值BLS和MTS方案所需的时间只包括签名聚合的时间，与MTAPS方案相比，上升趋势较平缓。但是在DeFi系统的实际应用中，一个宇宙中的节点数量是有限的，阈值通常很小（≤10），因此MTAPS方案在组合阶段的性能不会受到很大的影响。

在签名验证阶段，MTAPS方案所需的时间包括验证组合者输出的签名集、验证组合者自己的签名和验证零知识证明。其中验证组合者输出的签名集耗时最多。如图5所示，在签名验证阶段，由于最初签名数量较少，MTAPS方案的时间开销也较小。然而，随着宇宙阈值的增加，MTAPS方案的时间开销会显著增加，这主要是受验证零知识证明的影响，其他两个方案相对稳定。阈值BLS和MTS方案的验证时间基本保持不变。在DeFi系统的实际应用中，一个宇宙中的节点数量是有限的，阈值通常很小（不大于10），因此MTAPS方案在实际的应用过程中验证阶段是更高效的。

综上，MTAPS方案在组合阶段的效率略低于阈值BLS和MTS方案，但它引入了Chainlink预言机系统多重宇宙应用背景下所缺乏的隐私和责任兼具的阈值签名，且在验证阶段的效率更为高效。此外，本研究实验使用的服务器性能不是最优的，但在实际应用中受益于服务器的优化，签名所需的时间将减少，从而表现出更好的性能。

5　 结 语

本文提出了一种支持非交互设置的多重宇宙阈值签名方案。该方案可以在多重宇宙背景下实现兼具隐私性和责任性的阈值签名，从而提升了系统的安全性。方案采用去中心化方式管理密钥，无需依赖密钥分发中心。当签名内容存在异常时，系统中的跟踪者能有效识别问题并向签名者进行追责。实验结果和安全性分析结果表明，本文方案在分布式预言机网络中的应用是可行的，且各阶段算法均展现出较高的执行效率，这对DeFi应用场景具有重要意义。鉴于当前零知识证明方案的时间效率仍有提升空间，后续研究将重点优化其计算性能。

参考文献

[1] BONEH D， LYNN B， SHACHAM H. Short signatures from the Weil pairing［M］//Advances in Cryptology — ASIACRYPT 2001. Berlin： Springer， 2001： 514-532. DOI：10.1007/3-540-45682-1_30 .

[2] 徐淑奖， 张朝阳， 王连海， 等. 基于区块链的跨数据中心匿名可监管身份认证方案［J］. 网络与信息安全学报， 2024， 10（2）： 47-58. DOI： 10.11959/j.issn.2096-109x.2024031 .

[3] XU S J， ZHANG C Y， WANG L H， et al. Blockchain-based cross-data center anonymous and verifiable identity authentication scheme［J］. Chinese Journal of Network and Information Security， 2024， 10（2）： 47-58. DOI： 10.11959/j.issn.2096-109x.2024031（Ch ）.

[4] 胡荣磊， 丁安邦， 于秉琪. 一种基于门限签名的区块链共识算法［J］. 计算机应用研究， 2022， 39（12）： 3555-3561. DOI： 10.19734/j.issn.1001-3695.2022.04.0219 .

[5] HU R L， DING A B， YU B Q. Blockchain consensus algorithm based on threshold signature［J］. Application Research of Computers， 2022， 39（12）： 3555-3561. DOI： 10.19734/j.issn.1001-3695.2022.04.0219（Ch ）.

[6] LIU B W， SZALACHOWSKI P， ZHOU J Y. A first look into DeFi oracles［C］//2021 IEEE International Conference on Decentralized Applications and Infrastructures （DAPPS）. New York： IEEE Press， 2021： 39-48. DOI：10.1109/DAPPS52256.2021.00010 .

[7] ELLIS S， JUELS A， NAZAROV S. Chainlink： A decentralized oracle network［EB/OL］. ［2017-03-11］.

[8] BONEH D， KOMLO C. Threshold signatures with private accountability［M］//Advances in Cryptology — CRYPTO 2022. Cham： Springer Nature， 2022： 551-581. DOI：10.1007/978-3-031-15985-5_19 .

[9] BAIRD L， GARG S， JAIN A， et al. Threshold signatures in the multiverse［C］//2023 IEEE Symposium on Security and Privacy （SP）. New York： IEEE Press， 2023： 1454-1470. DOI：10.1109/SP46215.2023.10179436 .

[10] BELLARE M， ROGAWAY P. Introduction to modern cryptography［EB/OL］. ［2024-03-20］. DOI: 10.1007/11535218_32 .

[11] GJØSTEEN K， JAGER T. Practical and tightly-secure digital signatures and authenticated key exchange［M］//Advances in Cryptology — CRYPTO 2018. Cham： Springer International Publishing， 2018： 95-125. DOI：10.1007/978-3-319-96881-0_4 .

[12] BONEH D， GENTRY C， LYNN B， et al. Aggregate and verifiably encrypted signatures from bilinear maps［M］//Advances in Cryptology — EUROCRYPT 2003. Berlin： Springer， 2003： 416-432. DOI：10.1007/3-540-39200-9_26 .

[13] OZDEMIR A， BONEH D. Experimenting with collaborative zk-SNARKs： Zero-knowledge proofs for distributed secrets［C］// 31st USENIX Security Symposium （USENIX Security 22）. Berkeley： USENIX Assoiation， 2022：4291-4308.

基金资助

国家重点研发计划(2021YFB2700200)

国家自然科学基金(61772383)

国家自然科学基金(U1836202)

国家自然科学基金(62076187)

国家自然科学基金(62172303)

湖北省自然科学基金(2020CFB628)