摘要
门限签名方案允许分布式签名，在n个参与者的群体里面，任何大于t+1个群体都能够完成签名，然而任何小于等于t的群体不能完成签名。
虽然之前已经有了基于ECDSA的门限签名方案，但是我们设计了第一个支持任意t<=n的高效的多签协议，并且key generation无需任何中间环节。
我们的协议比之前的门限签名方案更加快速高效，并且显著降低了通信复杂度。我们证明了该方案在不诚实节点占多数情况下，在对抗恶意对手时的安全性。
我们实现了该协议，证明了其在实际使用场景中的高效性和兼容性。
1. 介绍
门限签名方案能够使n方在相同公钥前提下共享数字签名权利。门限值t被指定，任意>=t+1个子集参与者可以联合签名，然而小于该数量的子集无法完成签名。
通常，目标是为了得到与现存的中心化签名方案一致的签名结果。在门限签名方案中，私钥生成与签名算法被参与方的通信协议所取代，但是验证方法被完整的保留下来，这部分一般由某个中心化参与方完成（执行）。
近年来，签名方案越来越多被关注，特别是ECDSA的门限生成技术，重要的原因是因为ECDSA在bitcoin和其他加密货币的广泛应用。事实上，基于ECDSA的安全门限签名方案将成为一种有效的对策，以应对由于签名授权交易过程的私钥丢失而导致的bitcoin被盗。bitcoin安全等同于私钥安全。私钥应该被分开保存，同时签名行为也应该被授权给门限计算参与者，而不是简单的将私钥存储在一个地方。任何一个计算方或者少于门限值数量的计算方违反行为，都将不允许攻击者盗窃任何资产或者收集到任何key信息。
在bitcoin之前，最好的ECDSA门限签名方案是Gennaro完成的工作，有相当大的挫折。为了实现t个参与者的安全门限（少于t无法签名），必须要实现在至少2t+1个参与者之间的私钥分发，并且至少2t+1个参与者要参与签名过程。这个限制从规则上排除了要求所有各方签名的n-of-n私钥共享。此外，要求设置多台服务持有私钥共享，这样带来的问题是成本增加，当然在某种程度上攻击者的工作会更容易（因为许多台服务都肯能成为目标，并且诚实参与者需要至少有2t+1个参与签名，攻击者只需要t+1台服务就可以偷到私钥）。
为了解决这些问题，Mackenzie 和 Reiter 为 2-out-of-2 签名场景设计了专门的方案，Gennaro的方案并为涵盖这种场景。近期许多增强的2-out-of-2方案被提出。然而2-out-of-2共享有非常多的限制，可能无法实现某些特定应用程序需要的更加灵活的共享策略。
Gennaro和其他人共同解决了在更加通用的(t, n)情况下门限值的优化设置，这意味着 n>=t+1情况下只有 t+1 个参与者被要求参加签名。然而这个方案有个巨大的问题，就是分布式的私钥生成协议成本非常之高。
结论：我们提出的这种新的ECDSA门限优化协议在许多重要方面实现了增强。这种新的协议速度更快，同时比[4, 17]需要更少的通信次数；概念上更加简单，也不需要复杂的分布式私钥生成协议。
在同一进程的并行工作过程中，Lindell 提出了一种多方门限ECDSA签名的近似方案，具有高效的私钥生成。
1.1. 方案总体
回想一下一般的DSA签名算法步骤
- 由元素g生成的的任意素数q的cyclic group G(这意味着 g \in G 都是以q为幂的数值).
- 使用hash函数 H 将任意字符串映射到 $Z_q$ 的定长有限域
- 使用hash函数 H’将循环群组G映射到 $Z_q$ 的定长有限域
- 在 $Z_q$ 有限域中均匀随机的选择x，x即为私钥
- 同时求解 $y=g^x$ 得到公钥
- 待签名消息M，签名者首先计算 $m = H(M) \in Z_q$
- 在Z_q有限域内选择随机数k，计算 $R=g^{k^{-1}} \in G$，同时计算 $r = H’(R) \in Z_q$
- 计算 $s = k * (m + xr) mod q$。得到待签名消息的签名结果为 $(r, s)$
- 签名结果的验证计算公式为
$$R’ = g^{ms^{-1} mod q} * y^{rs^{-1} mod q} \in G$$
当 $H’(R’) == r$ 时验证通过
共享DSA签名的技术难点在于需要联合计算R和S，其中R是g的k倒数次幂，s是k与x的乘积。参考文件[18]充分展示了如何在多个参与者之间使用隐私信息完成两次计算。在[18]文献中，隐私值通过Shamir密钥共享实现分发，举例，从具有自由t次多项式上选择相应的点，其中参数是隐私值。乘法计算的影响是多项式的两倍，这就解释了为什么在[18]中提到的解决方案需要至少2t+1个参与者进行计算。为了解决这个问题，使用一个乘积结果作为共享密钥x，其中 $x = x1*x2$ (这个方法在[12, 28]中也被采用)，然后，x的计算难以在t>2的情况实现。
[17]中提到了一个不同的方法：密钥x通过公钥加密方案E通过加密计算生成，同时隐私值E既能在不通参与者之间共享，也能有效提供私钥x。如果E是一个加法条件下的同态加密方案（比如 Pailliers’s [33]），他们表明可以构建一个合理有效的协议，不过这个协议存在一些问题。主要的问题之一是这个协议需要基于公私钥对的联合计算用以得到加法条件下的同态加密E。当E使用Paillier方法实例化后，这需要RSA模数的分布式生成。虽然这个方案的问题众所周知，但是实际上这个计算过程没有有效和规模化的方法而被忽略。在已知的情况下，该协议从未被恶意多方计算案例中实现。我们所知的对于这个协议的基准检测结果是，在两方半诚实案例中，需要15分钟才能完成，同理我们可以推测出在更多方的恶意节点设置下，需要花费相当长的时间。而且这个签名生成协议需要更长的消息体和复杂的零知识证明。
本文，我们使用了受到SPDZ方法启发的多方计算的不同路径。给定两个秘密值a, b，在多个参与者直接共享，共享方法如下
- 设 $a = a_1 + … + a_n ， b = b_1 + … + b_n$
- 定义ab的乘法规则为 $ab = \sum_{i, j} a_i b_j$
- 因此如果需要得到ab的加法共享隐私值，通过每个多方计算参与者自身持有的 $a_i b_j$汇总就够了
- 在这种情况下，我们设计一个两方协议，该协议允许两方将秘密的乘法结果转换为同一秘密的加法结果
- 参与者以成对的方式参与该协议，以获得 ab 的附加秘密结果共享
基于这个方法，我们为一般的多方计算场景构建了一个简单的优雅的ECDSA门限协议。
- 多个参与者开始于一个(t, n)Shamir共享私钥x
- 当t+1个参与者参与签名，生成两个加法共享随机数k和γ，其中 $k=\sum_i k_i$， $γ=\sum_i γ_i$
- 使用上节的算法计算结果 δ = kγ[可以简单快速被重建]，$σ = kx = \sum_i w_i$ [保持共享]
- 通过将自己持有的$γ_i$与公共值$δ^{-1}$进行乘法计算，参与者共同得到一个加法共享值$k^{-1}$
- 接下来计算R，计算公式为 $R = \prod_i{g^{ {γ_i}δ^{-1} } }$
- 接下来计算s，s是一个参与者间的加法共享值，每个参与者持有的 $s_i = k_im + w_ir$，则$s=\sum_is_i$
1.2. 在恶意对手情况下避免昂贵的零知识证明
根据[28]，我们在多方参与者间检测恶意行为的过程中，最小化使用了零知识证明。
取而代之的是，我们采用了优化方法来假定参与协议运行的各方都是诚实节点。通过检测签名结果的合法性来判断是否有参与者背离了协议而运行（加入签名不能被验证，显然至少有一个参与者没有合规运行）。
在这点上，因为我们可能处在不诚实节点占多数的情况，因而无法保证能够输出正确的签名结果而导致协议停机。这产生了一个技术上很复杂的问题，就是需要证明诚实节点呈现的结果并没有泄漏任何有价值的信息，而且这种证明需要支持包括正确的计算场景和失败的计算场景两种情况。显然，这需要我们在呈现计算结果之前，分布式的验证每个节点的共享值$s_i$，同时重建合法签名。这个检查有点让人联想到 Canetti 和 Goldwasser 在 [7] 中解决类似问题以构建基于 Cramer-Shoup 方案的阈值 CCA 安全加密的方式。
范围证明。当使用签名验证方法来检测欺诈，我们不得不在共享交换协议期间，运行两步相对昂贵的零知识证明：
- 一个包含了一定通过Pailliers’s加密方法加密的结果的“范围证明”在一定程度上是小范围的
- 证明一方知道 x 使得 $c = E(x)$ 和 y = gx 其中 E 是 Paillier 的加密方案
1.3. 前面提到的方法的问题
之前版本的协议并未检查基于Paillier’s加密方法的秘密值的范围。这会产生一个对抗性策略，可能导致诚实节点共享的信息泄漏。之前版本的协议证明环节并未考虑这种泄漏，并且错误的设定了某些子协议是符合零知识和可模拟的。这个问题在[37, 32]中被提出。
在[37]中，文献作者呈现了如何利用这种信息泄漏来实际重建诚实节点的全部共享，并且让对手了解该组的完整私钥。然而关键上，这种攻击依赖于选择一个非常小的Paillier模数N（非常接近用于DSA方法模素数q）。在之前的版本中，我们清晰的指出，$N>q^7$，因而这种攻击并不适用于我们之前的方法（虽然在忽略了模数大小检查的情况下可以起作用）。
我们现在已经修改了方案，以取保所有基于Paillier’s方法构建的所有加密值都非常小。区别于之前方案的全部修改都会在提出时进行讨论，并且标注为关于先前版本的批注头。
最终，在之前的版本我们讨论了一种完全移除零知识范围证明的协议。我们讨论了移除零知识证明后会导致如何产生在不同服务器之间泄漏某些关于DSA密钥（即在每次签名方案中使用的随机数k）信息的攻击行为。我们推测这些信息（被泄漏的）仍然不会允许对手仿造签名。我们不认为这些轻量协议足够安全，并且永远不会推荐在商业系统中使用。我们作出这些推测是为了促进对泄漏这些信息的危险性的研究。我们的这些推测已经在[37, 32]中被推翻了，这篇文章同时呈现了移除零知识范围证明的确导致了协议的不安全。我们将在本文中预留第5节作为历史记录，但会以这些新的信息作为开头。
1.4. 实验结果
我们实现了本文提及的方法，并且发现该方法在私钥生成和签名协议都非常高效。
这个私钥生成协议很容易实现并且足够快速（在任何合理参数的选择下都低于1秒）。这与从未实现的[4, 17]密钥生成协议形成了鲜明对比，并且这个协议很难估算它的实际运行时间。
我们的签名协议同样非常高效，同时相比之前的工作无论在数据传输和运行时间都是非常重要的提升。
借助这种高效的密钥生成和签名协议的联合，我们的方法非常适合部署于实际生产环境。我们在第7节提供了完整的基测和评估。
2. 预备
通信模型。我们假定有一个广播信道，以及每个参与者存在点对点的信道连接。
对手。我们假定恶意对手出现符合一个时间上的概率多项式，恶意对手可能会偏离协议运行规则。恶意对手数量达到t，它了解所有受影响参与者的私有状态。与之前门限ECDSA方案相同，我们限定自己为静态腐蚀状态，这意味着对手必须在协议开始阶段选定被腐蚀的参与者，即系统开始运行后，腐蚀节点数量就被固定下来。已经有了标准的技术方法来将协议转换为静态腐蚀状态，以防止自适应的参与者腐化，不过这当然会产生额外的开销。
我们假定一个快速对手，这意味着它能够在给定的轮次中最后做决策，特别是它能够在看到诚实参与者的消息后再选择性给出自己的消息。
在[4, 17]的方法下，我们假定不诚实参与者为多数，设为t，即被对手腐化的参与者数量可能达到t-1.在这种情况下，无法保证协议运行能够完成，并且因而我们也不再尝试达到稳健以及协议完成的能力。
2.1. 签名方案
一个数字签名方案 S 包含三种高效算法：
- $(sk, pk) \leftarrow Key-Gen(1^λ)$，随机密钥生成算法，选择安全的参数作为输入，返回私有签名密钥sk和公有验证密钥pk。
- $σ \leftarrow Sig(sk, m)$，随机签名算法，选择私有密钥sk和待签名消息m作为输入，输出一个签名σ。由于签名很可能随机，因此可能存在多个有效签名。我们将这个这个有效签名集合表示为 {$Sig(sk,m)$}，并且满足 $\sigma\in { Sig(sk,m) }$
- $b \leftarrow Ver(pk, m, \sigma)$，确定性验证算法，使用公有密钥pk，消息m和签名 $\sigma$ 作为输入，输出一个bit长度值b，并且当对消息m的签名 $\sigma$ 符合公钥pk时候，b的值为1，否则为0.
为了证明签名方案的安全性，我们回顾了针对指定消息攻击的存在不可伪造的标准概念，这个曾在[23]被提及。
定义1（存在不可伪造性）。设想一个PPT对手A，拥有Key-Gen算法给出的公钥pk，以及能够访问签名算法Sig(sk, …)的预言机，预言机能够根据它选择的自适应消息接收签名。设M为A能够查询到的消息集合。如果没有PPT这样的对手，A可以在消息 $m \notin M$ 上生成签名，则数字签名方法 $S = (Key-Gen, Sig, Ver) $ 被认为是存在不可伪造的，除非 $\lambda$ 具有可忽略的概率。
2.2. 门限签名
门限密钥共享。由n个共享 {$x_1, …, x_n$} 组成的密钥x的 (t, n) 门限密钥共享存在一个高效算法，使得t+1个共享可以共同输出密钥，但t或者更少的共享无法显示任何密钥信息。
门限签名方案。考虑一种签名方法，$S = (Key-Gen, Sig, Ver) $。一个(t, n)门限签名方法TS，使得S能够在n个参与者进行密钥分布，参与者为 {$P_1, …, P_n$}，至少需要t+1个参与者才能联合生成签名，t或者少于t个参与者则不能。正式的说，TS由两个协议组成：
- 门限密钥生成。分散密钥生成协议，使用安全参数$1^{\lambda}$作为输入参数。每一个参与者 $P_i$ 收到公钥 pk 和 一份私钥 $sk_i$ 作为输出，其中$sk_i$是归属 {P_i} 的私钥分片。
- 门限签名。这种分布式签名协议使用待签名消息m和每个参与者持有的私钥分片 $sk_i$作为公共输入。它输出签名结果 $\sigma \in Sig(sk, m)$。
注意到门限签名方案输出的签名是在密钥Sig下的有效签名，但是Sig是一种中心化的签名协议。因此我们不需要指定验证算法的门限变体，因为我们会使用中心化的验证算法，Ver。
在某些应用中，需要接受由可信交易商为每个参加者生成私钥共享。在这种情况下，门限密钥生成将不被运行使用。
在[18, 19]之后，我们提出了一个类似于EU-CMA的基于游戏的安全定义。
定义2（不可伪造的门限签名方法）。我们提到这种(t, n)的门限签名方案 TS包括(Thresh-Key-Gen, Thresh-Sig)是不可伪造的，如果没有腐化了最多t个参与者的恶意对手能够产生对任意新的消息m的签名的概率不可忽略，在Thresh-Key-Gen和Thresh-Sig协议视角来看，输入消息 $m_1, …, m_k$ 是可以被对手自适应选择的。
这是一个基于游戏的安全定义，类似于Goldwasser，Micali和Rivest定义的在给定消息攻击下的存在不可伪造的概念。与中心化的EU-CMA定义不同，对手还能够获取被腐化的参与者的密钥生成协议，还能够获得指定消息的签名协议。一种更健壮的基于仿真的定义也是可能的。在6.3节中，我们呈现了如何证明我们使用的更加健壮的基于仿真的定义的协议安全.
2.3. 加法同态加密
我们的协议依赖加密方案 $\xi$，即加法同态对一个大整数N取模。
设$E_{pk}(.)$表示加密算法，$\xi$使用公钥pk。给定密文 $c_1 = E_{pk}(a)$ 和 $c_1 = E_{pk}(b)$，
设一个高效的计算方法，用 $+_E$ 表示，
计算方法如下 $ c_1 + c_2 = E_{ pk } (a + b) mod N$，其中加法为$+_E$。
一个密文加法运算的存在意味着对应一个标量的乘法运算，标为为 $\times_E$。对于一个给定的整数 $a \in N$，以及一个密文 $c=E_{pk}(m)$，则
$a \times_E c = E_{pk}(am \ mod \ N)$。
非正式的讲，如果任意两个消息的加密概率分布在计算上是难以区分的，那么我们认为 $\xi$ 是语义安全的。
我们使用Paillier的加法同态加密来实例化我们的协议应用，回顾一下细节：
- Key-Gen：生成两个等长大素数 P,Q，计算 N = P*Q。设 $\lambda(N) = lcm(P-1, Q-1)$为N的Carmichael函数，设$\gamma = N + 1$。公钥是 $Z_N$，密钥是$\lambda(N)$。
- Encryption：加密一个消息m，其中 $m \in Z_N$，先选择一个 $x \in_RZ_N*$，计算 $c = \gamma^mx^N\ mod\ N^2$。
- Decryption：解密一个密文c，其中 $c \in Z_{N^2}$，设L是一个定义在集合 {$u \in Z_{N^2} : u = 1 \ mod \ N$}的函数，形式为 $L(u) = (u - 1)/N$。则密文c的解密计算形式为$L(c^{\lambda(N)})/L(\gamma^{\lambda(N)})$
- 同态属性：给出两个密文 $c_1, c_2 \in Z_{N^2}$，定义 $c_1 +_E c_2 = c_1c_2\ mod \ N^2$。
如果 $c_i = E(m_i)$，则 $c_1 +_E c_2 = E(m_1 + m_2 \ mod \ N)$。
近似的，给定一个密文 $c = E(m) \in Z_{ N^2 } $ 以及一个数 $a \in Z_n$，得出 $a \times_E c = c^a\ mod\ N_2 = E(am\ mod\ N)$。
Paillier’s加密系统的安全性，依赖于N残差的决策性假设，解释为非正式来说，随机N残差和 $Z_{N^2}*$的随机群元素是无法区分的。
2.4. 不可扩展的模糊承诺
一个陷阱式承诺方案允许一个发送者提供一个使用信息论隐私的保证消息，举例说明，发送者给接收者一个承诺消息的副本，即使耗尽算力，也无法猜测出承诺的消息，而且也仅可能使用随机方法猜测。另一方面，当打开消息的时候，发送者计算上被绑定在承诺消息。事实上这个方法存在一个陷阱，他们的知识允许以任何可能方式开启一个保证承诺（我们也将其称为模糊承诺）。这个陷阱很难高效计算。
正式上，一个（非交互式的）陷阱承诺方案由四个算法组成，包括KG，Com，Ver，Equiv，分别描述如下：
- KG是密钥生成算法，在输入安全参数的情况下，会输出一个密钥对 { pk, tk}，其中pk与承诺方案相关的公钥，tk则称为陷阱。
- Com是承诺算法。在输入公钥pk和消息M的情况下，输出 $[C(M), D(M)] = Comp(pk, M, R)$，其中r是一个抛硬币随机数。C(M)是一个承诺字符串，D(M)是一个解除成怒哦字符串，需要在打开承诺结果之前保持私密。
- Ver是验证算法，在输入C, D和pk的情况下，它能够输出消息M或者⊥。
- Equiv是一个算法，用于在给定陷阱信息的情况下，以任意可能的方式开启承诺。它接受 公钥pk，字符串 M，以及[C(M),D(M)] = Comp(pk, M, R)条件下的R，一个不同于消息M的新消息M’，以及一个字符串T作为输入，输出D’，满足 Ver(pk, C(M), D’) = M’。
我们注意到如果发送者拒绝开启承诺，我们令 D = ⊥ 并且Ver(pk, C, ⊥) = ⊥，陷阱承诺需满足如下属性
- 正确性. 如果 [C(M), D(M)]=Comp(pk, M, R)，则 Ver(pk, C(M), D(M)) = M.
- 信息论安全性.对于任意消息对M和M’，C(M)和C(M’)的分布在统计学上是接近的.
- 安全绑定. 当对手能够输出C, D, D’ 并满足 Ver(pk, C, D) = M, Ver(pk, C, D’) = M’，并且 $M \neq M’$，则该对手A取得胜利。我们要求对于所有的有效算法A，A取得胜利的可能性在输入参数安全的前提下可以忽略不计。
Such a commitment is non-malleable [13] if no adversary A, given a commitment C to a messages m, is able to produce another commitment C0
such that after seeing the opening of C to m, A can successfully decommit to a related message m0 (this is actually the notion of non-malleability with respect to opening introduced in [10]).
The non-malleable commitment schemes in [10, 11] are not suitable for our purpose because they are not “concurrently” secure, in the sense that the security definition holds only for t = 1
(i.e. the adversary sees only 1 commitment).
The stronger concurrent security notion of non-malleability for t > 1 is achieved by the schemes presented in [8, 15, 31]), and any of them can be used in our threshold DSA scheme.
However in practice one can use any secure hash function H and define the commitment to x as h = H(x, r), for a uniformly chosen r of length λ and assume that H behaves as a random
oracle. We use this efficient random oracle version in our implementation.
2.5. 数字签名标准
数字签名算法（DSA）于1991年被Kravitz提出，并被NIST在1994年纳入数字签名标准(DSS)。ECDSA，是DSA基于椭圆曲线的变体，近些年变得相当流行，特别是在数字货币领域。
本文的所有结论都同时适用于DSA和ECDSA。我们使用出自[17]文件的更一般的G-DSA提出结果，我们来回顾一下：
前提设定
- 公共参数由素数q组成的循环群G给定
- 在循环群中生成随机数g
- 一个哈希函数 $H: [0,1] ^* \rightarrow Z_q$
- 另一个哈嘻函数 $H’ : G \rightarrow Z_q$，即将循环群租G的任意素数q映射到 $Z_q$ 有限域
算法
- 密钥生成。在输入参数安全的前提下，输出一个私钥x，x随机均匀分布于有限域 $Z_q$，一个公钥 y，$y = g^x$。
- 签名计算。输入任意消息M，执行
- 计算M的哈希值 $m = H(M) \in Z_q$
- 选择随机数 $k \in_RZ_q$
- 计算 $R = g^{k^{-1}}$，$r = H’(R) \in Z_q$
- 计算 s = k(m + xr) mod q
- 输出签名结果 $\sigma = (r, s)$
- 验证签名。给定消息M，签名结果 $\sigma$ 和公钥y
- 检查 $r, s \in Z_q$
- 计算 $R’ = g^{ms^{-1}\ mod\ q} y^{rs^{-1}\ mod\ q} \in G$
- 判断 H’(R’) == r，true则验证通过
传统的DSA算法被给定了两个大素数p, q，满足 q和(p-1)互素，给定循环群G，元素由给定素数q的阶数组成，以及子群 $Z_p*$。在这种情况下，循环群G的乘法运算是乘法模数p。哈希函数H’定义为 H’(R) = R mod q.
ECDSA方法被给定群G，元素由一个椭圆曲线上的坐标q组成。在这种情况下，群G的乘法运算变为曲线上的乘法运算。哈希函数H’定义为 $H’(R) = R_x\ mod\ q$，其中 $R_x$为x坐标下的点R。
2.6. Feldman’s VSS协议
回想一下Shamir’s方法，当共享一个密钥 $\sigma \in Z_q$，某个处理人需要生成一个随机t次多项式p，并且满足 $p\in Z_q$，和$p(0) = \sigma$。这个密钥分片符合如下多项式
$$
p(x) = \sigma + a_1x + a_2x^2 + … + a_tx^t \ mod \ q
$$
每个参与者$P_i$会收到自己的密钥分片 $\sigma_i = p(i)\ mod\ q$。
在科炎症的密钥分片方法中，辅助信息被公开出来用于允许参加者检查他们的密钥分片有效的，并且关联了一个唯一的密钥。
Feldman’s VSS是一个Shamir密钥分片技术的扩展，处理人同时向所有t个参与者公开了 $v_i = g^{a_i} \in G$，并且 $v_0 = g^{\sigma} \in G$。
使用这些辅助信息，每个参与者 $P_i$ 能够检查他的密钥分片 $\sigma_i$，可以被下面公式验证有效性：
$$
g^{\sigma_i} = \prod_{j=o}^t v_j^{i^j} \in G
$$
如果所有参与者都不能够自我检查，它可以触发一个投诉并且协议会终止。注意，这于Feldman VSS最初提出的方案并不相同，因为它假定诚实者占多数，并且当一个不诚实参与者提出诉讼后可以恢复。然而，因为在这篇论文中我们假定不诚实者占多数，这个协议当有诉讼被提出即被终止。
虽然Feldman’s方法泄漏了 $g^{\sigma}$，可以通过模拟参数表明不会泄漏任何其他信息，我们再次忽略细节讨论。
2.7. 假定
DDH。设G是一个素数阶的循环群，由g生成。DDH假定表明，以下两个分布在 $G^3$ 域内计算上是无法区分的
- DH = {( g^a, g^b, g^{ab} )}，其中 $a, b \in_R Z_q$
- R = {(g^a, g^b, g^c)}，其中 $a, b, c \in_R Z_q$
强RSA。设N是两个安全素数的乘积， N = pq，并且 p = 2p’+1，q = 2q’ + 1，其中p’ 和q’均为素数。根据欧拉函数 $\Phi(N)$，则 $\Phi(N) = (p-1)(q-1) = p’q’$。使用 $Z_N^*$ 表示一个整数集合，区间为 [0, N - 1]，并且区间元素选择为与N互质。
设e是一个与 $\Phi(N)$ 互质的整数。
RSA假设表明，在整数集合 $Z_N^*$ 是无法计算 $e^{roots}$，
即给定一个随机元素 $ s\in_R Z_N^*$，很难找到x满足 $x^e = s\ mod\ N$。
强RSA假定表明，在整数集合$Z_N^*$的一个给定的随机数s，很难找到一个数x，在 $e \neq 1$ 情况下满足 $x^e = s\ mod\ N$。这个假定不同于传统的RSA假定，传统RSA假定允许对手任意选择指数e，因此她能够计算 $e^{-roots}$。
现在我们给出正式定义。设SRSA(n)是一个整数集合N，满足 two n/2-bit 安全素数。
设定1 假定强RSA设定成立，所有概率多项数倍数对手A遵守以下概率分布
$$
Prob[N \leftarrow SRSA(n); s\leftarrow Z_N^* : A(N,s) = (x, e) s.t. x^e = s\ mod\ N]
$$
在n值下可以出现概率可以忽略不计。
3. 分片转换协议
假定有两方，分别是Alice和Bob持有两个密钥 $a, b \in Z_q$分别我们认为满足一个密钥x的乘法分片，其中 x = ab mod q。Alice和Bob都想计算x的密钥加法分片 $\alpha \beta$，这是一个随机值，满足$\alpha + \beta = x = ab\ mod\ q$，Alice持有 $\alpha$和a，Bob持有$\beta$和b。
这里我们基于加法同态方法给出一个协议，这种方法已经在诸多文献被引用，并且满足我们的需求。我们假设 Alice 与一个在整数 N 上的加法同态方案 $\xi$ 的公钥 $E_A$ 相关联。
接下来，我们将该协议命名为MtA（乘法到加法转换）分片转换协议。在我们的协议中，假定 $B = g^b$ 是可公开的。在这个情况下，一个额外的检查要求Bob使用正确的值b。这种增强的协议命名为MtAwc（即MtA with check）。
- Alice如下初始化协议
- 发送 $c_A = E_A(a)$ 给Bob
- 借助范围证据使用零知识证明Bob知道 $a<q^3$
- Bob计算密文 $c_B = b \times_E c_A +_E E_A(\beta’) = E_A(ab + \beta’)$，
其中 $\beta’$在 $Z_{q^5}$中被随机均匀指定。Bob设置他的分片 $\beta = \beta’\ mod\ q$。给Alice返回如下消息
- 发送 $c_B$
- 使用零知识证明他知道 $b<q^3, \beta’<q^7 并满足 c_B = b \times_E c_A +_E E_A(\beta’)$
- 只有 $B = g^b$ 是公开的
- Alice解密 $c_B$ 以获得 $\alpha’$ 并且设置 $\alpha = \alpha’\ mod\ q$
正确性。假定两个参与者都是诚实的，并且 $N>q^8$。Alice解密得到的值 $\alpha’ = ab + \beta’$。
同时 $\beta’ < N - ab$ 并且因此模N的值减少不会被执行，这意味着协议正确计算 $\alpha , \beta$，使得 $ \alpha + \beta = x\ mod\ q$。
模拟。我们首先指出作为一个独立协议，我们能够证明其安全性，即使没有范围证明。事实上，如果对手腐化了Alice，接下来Bob的消息能够被在不知道他输出的b的情况下呗模拟。模拟者可以仅仅通过随机选择一个 $b’ \in Z_q$来充当Bob。在这个模拟场景中，Alice解密的消息分片在统计学上能够接近当Bob使用真实b来解密得到的消息，因为这个噪声 $\beta’$ 是均匀的分布在有限域 $Z_{q^5}$。
如果对手腐化了Bob，那么Alice的消息能够在不知道她的输入a的情况下被模拟，事实上这个模拟者能够紧紧通过选择一个随机数 $\alpha’ \in Z_q$ 来充当Alice。在这个情况下，从Bob的视角是无法从计算上分辨是否真实，因为$\xi$在加密方法上是语义安全的。
然而如果这个范围证明不被使用，恶意的Alice或者Bob能够通过选择巨大的输入数而引发协议失效。作为一个独立协议，这并不是问题，因为参与者甚至没有意识到模数N的减少，也并没有泄漏其他方的输入。然而，当内部使用我们的门限DSA协议时，这种攻击会引发签名验证失效，并且此信息与其他方输入的大小有关系。
举例说明，设Alice输入 $a’ = q^7 + a$来运行协议。如果Bob的输入很小，那么对N值的模数减少将不会发生，协议会成功运行，并且最终我们的门限数字签名协议产生的签名信息会得到验证（因为 a’ = a mod q）。但是如果Bob的输入信息很大，协议则会失效。当任何一方没有检查 $b 和 \beta’$ 的范围时候，相似的问题都会发生。
因此，我们需要保证一个预言机存在，来告诉所有参与方是否发生了N的模数减少，但是由于零知识范围证明，这种减少只会在可以忽略不计的概率和安全范围情况下发生。
Remark。关于零知识证明和模数N的大小。因为协议中要求存在的零知识证明，我们使用了文献[30]提出的与零知识证明相似的简化版本。这些零知识的论点是由强RSA来保证安全的。进一步讲，要求 $N \approx q^8$（上文曾提到）。我们指出这些典型参数的选择，N需要接近 $q^8$ （因为q通常是256-bit长度，而N是2048-bit的RSA模数（参数）），因此这些要求是没有问题的。然而参与方检查N的大小是至关重要的，因为这保证了零知识证明的属性。
上一个版本的注意事项：在之前的版本里，我们选择均匀分布于有限域$Z_N \beta’$，并且没有执行任何范围（大小）检查。当选择的$\beta’$接近N的时候，会导致上文提到的相似的信息泄漏问题，即一个模数减少（进而引发协议的失效）发生于输入数据a的分散。
4. 我们的方法
本节开始介绍我们的协议。参与者在G上运行协议，其中 g 是DSA签名方法使用的循环群（记为 $G(q) = q^n | n\in Z$）。
我们设定每个参与者 $P_i$都关联一个符合加法同态加密方法（表示为 $\xi$）的公钥分片 $E_i$。
4.1. 密钥生成协议
- 第一步。每个参与者 $P_i 在实数域选择一个 u_i\in_R Z_q$；计算 $[KGC_i, KGD_i] = Com(g^{u_i})$，然后广播 $KGC_i$。
同时每个参与者 $P_i$ 在Paillier’s加密系统内对应的广播自己的公钥分片 $E_i$。 - 第二步。每个参与者广播$KGD_i$。设$y_i 为 P_i 未提交的值$。参与者 $P_i 执行 输入值为 u_i 的 (t,n) Feldman=VSS门限计算，其中 y_i 作为指数自由项$。公钥被设为 $y = \prod_i y_i$。
每个参与者在 n范围内的Feldman VSS协议中加入自己收到的私钥分片。结果值 $x_i 是一个 (t, n) Shamir’s 密钥分片， 密钥 x = \sum_i u_i$。$X_i = g^{x_i}$是公开的。 - 第三步。设 $N_i = p_iq_i$ 是关联 $E_i$的RSA模数。每个参与者 $P_i$ 使用零知识证明他知道对应的 Schnorr’s协议的 $x_i$，并且 $N_i$ 是一个 Gennaro, Micciancio, Rabin协议下的无平方数因数的数。
4.2. 签名生成
我们来描述一下签名生成协议，这个协议接受m作为输入，其中m是待签名的消息M的hash值，协议的输出跟上文描述一致。我们注意到后面的协议是一个 t-out-of-n 协议（因此密钥x使用 $(t,n)$ Shamir方法实现分享）。
定义 $S \subseteq [1..n]$ 为参与签名协议的参与者集合。我们假定 |S| = t + 1。对于签名协议，我们能使用 (t, t+1) 密钥分享方法，分享任意的短密钥，并且分享过程不需要使用一般的 $(t, n)$ 门限结构。我们注意到选择合适的拉格朗日系数 $\lambda_i$，S集合中的每一个参与者能够本地映射到他自己的 $(t, n)$ 门限分享的 $x_i$密钥分片，x是 $(t, t+1)$ 门限分享中的密钥， $w_i = (\lambda_{i, s}(x_i))$，例如
$x = \sum_{i\in S}w_i$。因为 $X_i = g^{x_i} 和 \lambda_{i,S}$ 是公开的值，所有的参加者都能够完成计算 $W_i = g^{w_i} = X_i^{\lambda_{i, S}}$。
阶段1. 每个参与者 $P_i 选择 k_i, \gamma_i \in_R Z_q$；计算 $[C_i, D_i] = Com(g^{\gamma_i}$ 并且广播 $C_i$。定义 $k=\sum_{i\in S}k_i, \gamma=\sum_{i\in S}\gamma_i$。并且定义乘法
$$
k\gamma = \sum_{i, j\in S}k_i\gamma_j\ mod\ q
$$
$$
kx = \sum_{i, j\in S}k_iw_j\ mod\ q
$$阶段2. 每一对参加者 $P_i, P_j$ 参加两个乘法到加法的分片转换子协议
- $P_i, P_j$ 各自使用自己的 $k_i, \gamma_j$ 密钥分片计算 MtA（乘法转加法）. 设 $\alpha_{ij} [另一个是\beta_{ij}]$ 是参加者 $P_i [和P_j]$ 分别得到的分片，符合以下计算协议
$$
k_i \gamma_j = \alpha_{ij} + \beta_{ij}
$$
参与者 $P_i 令 \delta_i = k_i\gamma_j + \sum_{j \neq i}\alpha_{ij} + \sum_{j \neq i}\beta_{ji}$。注意到 $\delta_i 是一个符合 k\gamma = \sum_{i\in S}\delta_i 的 (t, t+1) 加法门限分片$。
- $P_i, P_j 使用分片 k_i, w_j$分别执行 MtAwc计算。令 $\mu_{ij} [另一个参与者对应 \nu_{ij}]$ 为两个参与者分别得到的分片，符合以下计算协议
$$
k_iw_j = \mu_{ij} + \nu_{ij}
$$
参与者 $P_i 令 \sigma_i = k_iw_j + \sum_{j \neq i}\mu_{ij} + \sum_{j \neq i}\nu_{ji}$。注意到 $\sigma_i 是一个符合 k\gamma = \sum_{i\in S}\delta_i 的 (t, t+1) 加法门限分片$。
阶段3. 每个参与者 $P_i 广播 \sigma_i，所有参与者使用 \sigma = \sum_{i\in S}\sigma_i = k\gamma 重构 \sigma$。所有参与者计算 $\sigma^{-1}\ mod\ q$。
阶段4. 每个参与者 $P_i 广播 D_i$。令 $\Gamma_i 是参与者 P_i基于零知识证明他知道 \gamma_i 所提交的值。\Gamma_i=g^{\gamma_i} 符合Schnorr协议$。
参与者分别计算
$$
R = [\prod_{i\in S}\Gamma_i]^{\sigma^{-1}} = g^(\sum_{i\in S}\gamma_i)^{k^{-1}\gamma^{-1}} = g^{\gamma k^{-1} \gamma^{-1}} = g^{k^{-1}}
$$
和$r = H’(R)$。阶段5. 每个参与者 $P_i 令 s_i = mk_i + r\sigma_i$。使得
$$
\sum_{i\in S} = m\sum_{i\in S}k_i + r\sum_{i\in S}\sigma_i = mk + rkx = k(m + xr) = s
$$
也就是 $s_i 是 s的 (t, t+1) 门限分片$。5A 参与者 $P_i 选择 \iota_i, \rho_i \in R Z_q 计算 V_i = R^{s_i}g^{\iota_i} ， A_i = g^{\rho_i}，以及 [C_i, D_i] = Com(V_i, A_i) 并广播 C_i$。
令 $\iota = \sum_i\iota_i，\rho = \sum_i\rho_i$5B 参与者 $P_i 广播D_i，并且使用零知识证明他知道 s_i, \iota_i, \rho_i，并且满足 V_i = R^{s_i}g^{\rho_i}， A_i^{\rho_i}$。如果零知识证明失败，协议终止。令 $V = g^{-m}y^{-\gamma} \prod_{i\in S}V_i (需要满足 V = g\iota 以及 A = \prod_{i\in S}A_i )$。
5C 参与者 $P_i 计算 U_i = V^{\rho_i} 和 T_i = A^{\rho_i}。 承诺 [C_i, D_i] = Com(U_i, T_i) 并广播 C_i$。
5D 参与者 $P_i 广播 D_i 来撤销承诺 U_i, T_i， 如果 \prod_{i\in S} [T_i] \neq \prod_{i\in S} U_i，则协议终止$。
5E 否则参与者 $P_i 广播 s_i。 所有参与者计算 s = \sum_{i\in S}s_i$。 如果 (r, s) 不是一个合法签名，参与者终止，否则接受并完成协议。
- $P_i, P_j$ 各自使用自己的 $k_i, \gamma_j$ 密钥分片计算 MtA（乘法转加法）. 设 $\alpha_{ij} [另一个是\beta_{ij}]$ 是参加者 $P_i [和P_j]$ 分别得到的分片，符合以下计算协议
让我们直观的解释一下阶段5的背后逻辑。为了避免昂贵的零知识证明，我们可能正在重构一个不正确的签名，在检查的时候很可能被拒绝。为了实现阶段5有一种想当然的方法，就是向所有参与者揭示$s_i，并能重构 s = \sum_is_i$。但是由于证明会被所有人获得，这无法保证安全，直观的原因是对手通过输出一个非法签名让协议终止，那么诚实的参与者所持有的 $s_i$ 可能会透漏他们拥有的有价值的信息。这个可能通过广播 $S_i = R^{s_i} 并且根据DSA验证算法执行检查计算 \prod_iS_i = R^s = g^my^\gamma$ 而完成。但由于相似的原因，这步导致协议失败。因此在我们的协议中，参与者使用一个随机数$g^{\iota_i}来隐藏R^{s_i}$。
令 $V_i = R^{s_i}g^{\iota_i}， 那么 \prod_iV_i = R^sg^{\iota}，并且 V = g^{\iota}$。
参与者不能揭示 $g^{\iota_i}$来检查V的正确性，因为这消除了 $R^{s_i}，所以我们随机化了这个聚合值，变成 U = g^{\iota \rho}$。所有参与者通过分布式”Diffie-Hellman”交换，共同计算$g^{\iota\rho}$。如果这种分布式的随机化签名验证执行了，那么就实现了安全的分法分片值$s_i$，但是如果这个签名无法验证，则协议直接终止并且诚实参与者持有的分片值$s_i$永远不会被清晰的呈现出来。
4.3. 关于零知识证明
在 5B 这步，参与者 $P 输出了 V = R^sg^{\iota} 和 A = g^{\rho}，并且必须证明他知道 s, \iota, \rho 满足上面的等式关系$。关于A的证明是经典的Schnorr证明。V值的计算则是经典的（诚实验证者）零知识证明，计算步骤如下：
- 证明者选择 $a, b \in_R Z_q 并且发出 \alpha = R^ag^b$
- 验证者发出一个随机挑战 $c \in_R Z_q$
- 证明者回答验证者的挑战，通过如下计算 $t = a + cs\ mod\ q 和 u = b + c\iota\ mod\ q$
- 验证者检查如下等式是否成立 $R^tg^{\mu} = \alpha V^c$
4.4. 安全证明
本章证明下述定理
定理1 假定
- DSA签名方法不可伪造
- 强RSA方法的假设前提成立
- KG, Com, Ver, Equiv 是非扩展的具有二义性的承诺方法
- DDH方法的假设前提成立
那么我们在前面章节提到的门限DSA算法是不可伪造的。
该定理的证明将通过传统的模拟论据完成，这里我们展示了一个对手A，以极大概率伪造了门限签名，那么我们就能够设定一个伪造者F，使用中心化的DSA方法也以极大概率伪造了签名。
因此让我们假定使用门限方法伪造签名的对手A的概率关系如下， $ \epsilon \geq \lambda^{-c}$。
我们假定对手控制了 {$P_2, …, P_{t+1}$} 个参与者，并且 $P_1$ 是最诚实的参与者。因为我们使用同时非扩展承诺（即对手能够看到所有诚实参与者的承诺信息数据），那么这个证明在当对手控制了少于t个参与者并且我们有多于1个诚实参与者的条件下也会成立。因此上述假定仍然具有一般性。
因为我们假定对手是并未充分准备的，诚实参与者$P_1$在每一轮计算中都是率先执行并广播。我们的模拟器将充当 $P_1$ 参与者的角色，并且与控制了 {$P_2, …, P_n$} 的对手进行交互。回想一下对手A的工作：它首先参与了key-gen协议来为门限方法生成公钥y。接下来它要求其他参与者来签名一系列消息 {$m1, …, m_{\iota}$}，并且他们都加入到针对这系列消息的签名协议运行。最后它至少有概率 $\epsilon$ 输出消息 $m \neq m_i$ 和一个DSA公钥y下的合法签名 (r, s)。这个概率依赖于A选择的随机数 $\tau_A$以及 $P_1选择的随机数 \tau_1$。
假设我们用 $A(\tau_A)_{P_1(\tau_1)}$来表示A在上述描述的实验过程的最后输出，我们可以将概率表示为
$$
Prob_{\tau_1, \tau_A}[A(\tau_A)_{P_1(\tau_1)} 是伪造的] \geq \epsilon
$$
我们指出对手A选择的随机数 $\tau_A$ 如果满足下面条件，则是恰当的
$$
Prob_{\tau_1}[A(\tau_A)_{P_1(\tau_1)} 是伪造的] \geq \frac{\epsilon}{2}
$$
通过马尔可夫不等式的标准应用，我们知道如果 $\tau_A$ 被均匀随机的选择，那么选择恰当值的概率至少低于 $\frac{\epsilon}{2}$。
我们现在转而构建对手F，使用中心化的方法来伪造签名。这个伪造者将使用A作为子程序来进行模拟门限签名过程：F充当诚实者 $P_1$ 的角色，同时A控制其他参与者。F将为A选择随机数 $\tau_A$：我们知道这个合适的值的选择概率低于 $\frac{\epsilon}{2}$。从现在开始我们假定A已经选择了合适的随机数。
F以公钥y为输入运行中心化的DSA签名算法，随机数在均匀分布的集合G中随机选定。F的第一个任务是设定一套不可区分的模拟的密钥生成协议，以得到相同的公钥y。
近似的，每次A要求对消息$m_i$进行签名，伪造者F会从他的签名预言机中接收到外部的真实签名信息$(r_i, s_i)$。然后进将以一种难以区分的方式进行模拟门限签名的执行过程，实现以消息$m_i$为输入，产生签名$(r_i, s_i)$。
因为对于A来说，这个模拟过程与真实协议的运行是无法区分的，那么对手将输出与真实场景中一摸一样的概率结果。这种伪造的 m, r, s是关于消息的签名，永远不会被F通过它的签名预言机查询到，并且因而对F是一个有效的伪造。我们现在转向模拟的细节。
4.5. 模拟key-gen协议
下面描述Sim-Key-Gen模拟。以 $y = g^x$ 计算DSA公钥并输入，伪造者F接下来充当 $P_1$ 的角色。伪造者F同样通过输入一个Paillier公钥E继续运行，但是F并不知道对应的私钥（当我们需要对Paillier加密方法的语义安全做减法时，私钥是必须的）。
模拟：重复下述步骤，直到A发送有效信息（也就是一个正确的解除承诺）给 参与两次迭代的{$P_2, …, P_n$}。
- F(作为 $P_1$) 选择一个随机数 $\mu_1 \in Z_q，计算[KGC_1, KGD_1] = Com(g^{\mu_1}) 并广播 KGC_1$。A广播所有的承诺信息 $KCG_i, i>1$。
- 每个参与者 $P_i 分别广播 KGD_i$；设$y_i 是解除承诺的值，由Feldman-VSS产生 (F将按照协议指令执行)$。每个参与者 广播 $E_i。F广播 E_1 = E$。
- 令 $y_i$ 表示为每一个参与者公开的承诺值。F转回对手解除承诺的步骤
- changes the opening of $P_1 to KGD_1$，这样被公开的承诺值变为 $y_1 = y \prod_{i=2}^n y_i^{-1}$。
- 使用上面计算出来的自有值 $y_1$ 模拟 Feldman-VSS
- 对手A广播$KGD_i$。令 $y_i$是A公开的承诺值。$(this\ could\ be\ ⊥\ if\ the\ adversary\ refused\ to\ decommit)$.
- 参与者计算 $y = \prod_{i=1}^n y_i (set\ to\ ⊥\ if\ any\ of\ the\ ˆyi\ are\ set\ to\ ⊥\ in\ the\ previous\ step)$
现在对这个模拟的引理做一些证明。
引理1. 这个模拟过程会在可期望的二项式时间内结束，并且无法与真实协议相区分。
证明（引理1）。因为A以一个合适的随机数运行，我们知道基于这个随机数选择的F的概率，那么A将正确的解除承诺的概率至少符合如下公式 $\frac{\epsilon}{2} > \frac{1}{2\lambda^c}$。因而我们将有必要在一个多项式约束的期望时间内重复这个过程。
模拟过程和真实过程的唯一区别是 $P_1 以指数自由项 y_1 运行模拟Feldman-VSS 过程$，并且它不知道其离散对数。但是我们知道这个模拟与真实的Feldman-VSS有相同的分布。因此这个协议的模拟是完美的。
引理2. 对于一个有大分子的多项式输入y，模拟过程终止于输出y的概率非常小。
证明（引理2）。首先我们证明如果当输出不是⊥的时候，这个模拟过程会终止，那么它终止于输出y，不过这个概率非常低。这是承诺方案不可扩展的结果。事实上，如果A两次正确解除承诺 $KGC_i$，必须使用相同的字符串，不管$P_1也解除(亦即忽略概率)$。因而在 i>1的情况 $ˆy_i = y_i$，进而 ^y = y。
接着我们证明上述过程会发生在输入y具有多项式大分子项的情况下。令 $y_A = \prod_{i=2}^n y_i$，也就是对手对协议输出的贡献。注意到因为非延展性，这个值在F转为对手是由其决定并掌握。在这个点上F转换为对手，并且选择 $^y_1 = y(y_A^{-1})$。因为y是均匀分布的，则$^y_1$也是均匀分布的。因为A运行于一个合适的随机数上，我们知道有一部分概率为 $\frac{\epsilon}{2} > \frac{1}{2\lambda^c}$ 的 $^y_1$ 由A正确的解除承诺提交。因为 $y 和 ^y_1$ 有一一对应的关系，我们能够得出如下结论，对于发生概率满足 $\frac{\epsilon}{2} > \frac{1}{2\lambda^c}$ 的一部分输入y，这个协议将正确完成。
4.6. 签名生成模拟
密钥生成完后，F需要处理由对手A发起的签名查询。当A发起队消息m的签名，伪造者F将加入这个门限签名协议的模拟过程。在模拟过程中，F将访问签名预言机，这个签名预言机在之前发给F的公钥y下产生DSA签名。
半正确执行. 设k满足 $R = g^{k^{-1}}$， 并且 令 k’ 为由 MtA 和 MtAwc 协议参与者输入值定义的值。具体来说，如果 $c_i$ 是在第一轮协议中的参与者发出的加密值，那么定义 $k’_i = Dec_i(c_i)，并且 k’ = \sum_i k’_i$。
我们指出，如果在步骤4中，它满足 k = k’，那么这个协议执行是半正确的。注意到因为 k, k’ 的值是在步骤4中被唯一确定的，那么这个条件是很好定义的。也要注意到，如果对手A通过在 $\deta$ 的计算中暴露错误的分片来扰乱R的计算过程，那么这个执行就不是半正确的。
在协议真实的运行过程中，决定一个执行过程是否是半正确的是不可行的。然而，正如我们即将看到的，在模拟过程中，我们能够探测到是否一个执行过程是半正确的，并且依赖它是否是半正确的，这个模拟过程将决定如何模拟阶段5.
模拟鸟瞰. 首先我们注意到，对于半正确执行，对手在步骤4后已经能够探测到好的参与者在步骤5广播的值 $R^{s_1}$ 是否正确。事实上通过这点，对手有了 $s_i i>1$ 并且对于一个参加者， $R^{s_1}$的值能够通过下面公式检查
$$
\prod_i R^{s_i} = R^s = g^my^r
$$
而且在这些执行过程中，当我们达到步骤5A，这个模拟器将能够为好的参与者提供到 $s_1$ 的值，这些好的参与者将保证模拟过程成功结束。
第二步，我们展示对于非半正确的模拟，将有很大概率在步骤5D失败，因为好的参与者提供的 $U_1$ 值更像随机数。这允许我们通过简单的为$P_1$使用一个随机数来模拟阶段5.
最后，模拟器需要检测执行过程是否是半正确的，目的是知道选择的执行路径。虽然在真正的协议中，这种检测是不可能的，但是模拟器能够提供恰当的值来促进这个检测。下面是这个过程的详细描述。
4.7. 半正确执行
现在，我们提供一个工作与半正确执行的模拟。
我们指出F不知道$P_1$关联的所有秘密值，包括：它的正确的密钥分片$w_1$，以及密钥对应的公钥$E_1$。不知道公钥是必要的，这是为了降低加密方案的语义安全的不可伪造性。
然而F确实知道所有其他参与者的私钥分片 $w_j$ 。它同时知道 $P_1$ 的公钥，根据密钥生成协议的模拟定义， $W_1 = g^{w_1}$。
接下的模拟过程中，当协议应该中止的时候，F中止它，也就是说$如果对手(i)拒绝在步骤4、5B或者5D中解除承诺，或者在步骤2、5中未通过零知识证明，或者签名(r, s)无法验证$。
阶段1. 所有参与者通过广播$C_i (F为P_1正确执行协议)$执行协议.
阶段2.
- 所有参与者使用在阶段1中选择的 $k_1 和 \gamma_1 执行 MtA协议 计算 k和\gamma$。F为$P_1$正确运行协议。对于每一个其他参与者 $P_i i>1$，F运行两次MtA协议，一次它使用 $k_1$ 初始化，另一次它使用$\gamma_1$ 作为响应者。F从 i>1 的范围证明中得到以下值
- $k_i$
- $\gamma_i$
- $\beta_{1i}’$
注意到当F作为初始化的协议执行方时，在使用$k_1, \gamma_j作为输入的 P_j方的协议运行期间$，它不能解密它自己的加密分片$\alpha_{1j}$。然而，使用它得到的这些值，它能够计算 $\alpha_{1j} = k_1\gamma_i + \beta_i’\ mod\ q$。
- 所有参与者使用MtAwc协议计算k和x。这里F根据第三章描述的方式来模拟$P_1$，因为它不知道它自己的$w_1$。
然而它通过零知识证明得到 $P_j’s 的结果分片 v_{1j}$ - 使用$k_j, w_1作为输入的P_j的协议运行过程中$， F不知道 $w_1$，因此它就发送随机数$\mu_{j1} 给 P_j$。
注意，此时F知道所有坏的参与者的 $\delta_i$ 的合。事实上
$$
\sum_{i>1}\delta_i = \sum_{i, j>1}k_iw_j + \sum_j\mu_{j1} + \sum_j\nu_{1j}
$$
并且F知道等式右边的所有值。
- 所有参与者使用在阶段1中选择的 $k_1 和 \gamma_1 执行 MtA协议 计算 k和\gamma$。F为$P_1$正确运行协议。对于每一个其他参与者 $P_i i>1$，F运行两次MtA协议，一次它使用 $k_1$ 初始化，另一次它使用$\gamma_1$ 作为响应者。F从 i>1 的范围证明中得到以下值
阶段3. 所有参与者通过暴露$\delta_i$来参与协议。令 $\delta = \sum_i\delta_i (F使用它在步骤2中选择的随机分片来为P_1正确运行协议 - 因而F有效广播一个随机 \delta_1 )$。
阶段4.
- 每个参与者暴露 $D_i 来解除对 \Gamma_i 的承诺$
- F通过签名预言机查询并收到一个关于m的签名 $(r, s)$， 并计算 $R = g^{ms^{-1}} y^{rs^{-1}} \in G (注意， H’(R) = r \in Z_q )$
- F转回A解除承诺的步骤，并且充当 $P_1 改变承诺值为 \Gamma_1’ = R^{\delta} \prod_{i>1}\Gamma_i^{-1}。 注意 [\Gamma_1’\prod_{i>1}\Gamma_i]^{\delta^{-1}} = R$
注意，此时F知道坏的参与者持有的 $s_i$的值，由于$s_i = k_i m + \sigma_i r$，因此F能够将$P_1 持有的正确的s_1 计算为 s - \sum_{i>1}s_i$。
阶段5. 所有参与者在此阶段执行所有步骤。 F使用 $s_1 作为 P_1 的分片$。
我们证明以下关于模拟的引理。
引理3. 假定
- 强RSA前提成立
- KG，Com， Ver， Equiv 是不可延展的模糊承诺；
那么模拟具有下列属性 - 当输入消息m，则输出一个合法签名 $(r, s)$ 或者中止。
- 与半正确真实执行过程，在计算上无法区分
证明（引理3）。
真实过程和模拟过程唯一的区别：在MtA协议中，$c_i = E_i(k_i) 被公开，真实协议中 R = g^{k^{-1}}，其中 k = \sum_i k_i，在模拟过程中， R = g^{k’^{-1}}，其中k’来源于签名预言机$。在语义安全的Paillier加密保证下，这两个过程被看作计算上是无法区分的。
事实上，当F转而成为对手来“修正”R的值，那么它隐式的改变了F作为 $P_1被用于计算R 的k_1的值$。当 $R = g^{k’^{-1} }$，隐式的另 $k_1’ = k’ - \sum_{i>1} k_i$ 。
注意到 $R^{k_1’}$ 可以被知道，因为 $R^{k_1’ + \sum_{i>1}k_i} = g$，因而 $R^{k_1’} = g R^{- \sum_{i>1} k_i}$。因此，为了区分真实执行和模拟执行，对手必须检测在第一轮MtAwc协议中F充当$P_1$ 发出的密文是否包含一个随机数 $k_1$ 或者由计算 $log_R(g R^{- \sum_{i>1} k_i}) $ 确定的随机数 $k_1’$，这在语义安全的Paillier加密中是不可行的（给出所有的值被证明是足够小，并且没有对N取模计算）。
注意到我们正在用非半正确执行模拟一个半正确执行，但是因为两者无法区分，也并没有什么问题。
