实用异步分布式密钥生成

Practical Asynchronous Distributed Key Generation

摘要

​ 分布式密钥生成(DKG Distributed Key Generation)是一种在没有可信第三方的情况下引导门限密码系统(threshold cryptosystems)的技术，是随机性信标、门限签名和通用多方计算等去中心化协议的组成部分。一直到前不久，大部分DKG协议都基于同步模型假设，因此当其基本网络假设不成立时(不是同步模型时)，它们就很脆弱。异步DKG协议的最新进展也存在不足，因为它们要么效率很低，要么功能有限，导致缺失具体实践。

​ 本文提出了一种简单而具体高效的异步DKG (ADKG Asynchronous Distributed Key Generation)协议。在一个n个节点的网络中，该ADKG协议可以容忍多达t<n/3个恶意节点，并且具有期望为O(κn³)的通信成本，其中κ为安全参数。我们的ADKG协议产生一个域元素作为秘密，因此与现成的门限密码系统兼容。在按地理分布的AWS(亚马逊云)实例中使用多达128个节点的网络来实现ADKG协议并对其进行评估。我们的评估表明，对于32个和64个节点，我们的协议分别只需要3秒和9.5秒就可以完成。在两次实验中，每个节点分别发送0.7兆字节和2.9兆字节的数据。

缩写、全称以及中文含义

缩写	全称	中文含义
DKG	Distributed Key Generation	分布式密钥生成
ADKG	Asynchronous Distributed Key Generation	异步分布式密钥生成
sspk	secret-shared private keys	秘密共享私钥
BFT	Byzantine Fault Tolerant	拜占庭容错
FLP Impossibility	Fischer,Lynch,Patterson Impossibility	FLP不可能性
ACSS	Asynchronous Complete Secret Sharing	异步完全秘密共享
RO	Random Oracle	随机预言机
DCR	Decisional Composite Residuosity	判定性合数剩余
Amazon EC2	Amazon Elastic Compute Cloud	亚马逊弹性计算云
CBA	Computationally Bounded Adversary	计算能力有限的对手
PPT	Probabilistic Polynomial-Time	概率多项式时间
VSS	Verifiable Secret Sharing	可验证秘密共享
AVSS	Asynchronous Verifiable Secret Sharing	异步可验证秘密共享
RBC	Reliable BroadCast	可靠广播
ABA	Asynchronous (Byzantine) binary Agreement	异步二进制协议
DDH	The Decisional Diffie-Hellman Problem	DH判断问题
FC	Feldman Commitment	费尔德曼承诺
FPC	Feldman Polynomial Commitment	费尔德曼多项式承诺
HPC	Homomorphic-Partial-Commitment	同态部分承诺
NIZK proof	Non-Interactive Zero-Knowledge proof	非交互零知识证明

部分背景知识

• 同步网络环境：即整个网络环境里存在一个最大的延迟上界。例如，一个消息发给A，一秒钟之内(及时到达)可以到达。
• 半同步网络环境(弱同步网络环境)：即整个网络环境里存在一个最大的延迟上界，但并不知道具体是多少。例如，一个消息发给A，在一定的时间内(不知道具体是多久，但最后可以到达)可以到达。
• 异步网络环境：即整个网络环境里不存在一个最大的延迟上界(或者延迟上界极大)。例如，一个消息发给A，消息可能丢失，可能被修改，可能永远收不到这个消息。(即现实互联网环境)
• FLP不可能性：在一个异步系统中,即使只有一个进程出现了故障,也没有算法能保证达成共识。
• 判定性合数剩余假设(Decisional Composite Residuosity Assumption, DCRA)：即给定一个合数n和整数z,判定z是否模n²下是否是n次剩余是困难的。即判断xⁿ ≡ z mod n²是否有解是困难的。
• 概率多项式时间(Probabilistic Polynomial-Time)：线性时间为kn，多项式时间为n^k,指数时间为kⁿ，概率多项式时间是一种在多项式时间内运行的算法，它不是确定性算法，而是随机性算法。给定同一输入，可能产生不同输出。因此，如果我们把x输入A，不是得到一个确定性的输出值y=A(x)，而是得到一个随机变量Y，它有一定的概率是一组不同的值。
• 可验证秘密共享(Verifiable Secret Sharing)：如果参与方可以验证其他参与方秘密共享内容的一致性，那么该秘密共享方案就是可验证的。
• The Decisional Diffie-Hellman Problem：如果AB执行Diffie-Hellman密钥协议，那么G,g,g^a,g^b都是公共的，g^ab是密钥，DDH问题就是对手能否从随机的元素中区分A和B的密钥g^ab，也就是说，给定G,g,g^a,g^b和T_x(x被随机均匀的从{0,1})中选择使得T₀是G中随机的一个元素，T₁=g^ab，如果找到x的概率大于1/2则解决了DDH问题，则说明G,g,g^a,g^b一定泄露了一些关于g^ab的信息。
• Feldman Commitment：密钥持有者发送密钥的时候，还要附加一个commitment(承诺)，commitment是密钥持有者拥有该密钥的一个证据，密钥接收者接收到密钥后，首先验证commitment，验证通过后，再接受密钥碎片。
• CPA-secure：选择明文攻击下，密码体制抵抗攻击的能力。

I 介绍

​ DKG协议使一组互不信任的节点能够共同生成公/私钥对。私钥通过门限秘密共享方案在节点之间秘密共享，并且永远不会在单个节点上被重现或存储。秘密共享私钥稍后可以在门限密码系统中使用，例如，生成门限签名，解密门限加密的密文，或用于达成共识的共同代币。(可能是一种实现共识机制的方法。)

​ 互联网上对分散的拜占庭容错(BFT Byzantine Fault Tolerant)应用的需求日益增长，重新引起了人们对DKG协议的兴趣。许多最先进的BFT协议使用门限签名来提高通信效率，或者使用门限加密来防止审查。对于假设无界消息延迟的异步BFT协议，需要共享随机性来规避FLP不可能性。在门限密码学中，所有这些密码学基元都要求节点持有私钥的秘密份额。一种简单的方式是通过一个可信的分配者来分发这些秘密份额，但是这个分配者的腐败会破坏整个系统。因此，为了避免任何中央信任或单点故障，有必要使用DKG来引导上述门限密码学基元。

​ 已知有许多DKG协议是基于同步网络的。相比之下，只有少数最近的工作研究了异步网络的DKG，即ADKG。Kokoris等人提出了第一个ADKG协议。它们的构建采用了n个并发高门限异步完全秘密共享(ACSS asynchronous complete secret sharing)方案，构建了一个预期总通信成本为O(kn⁴)的ADKG协议，该协议预计在O(n)轮结束。这里κ是安全参数。最近，Abraham等提出了一种特殊用途的ADKG协议，期望总通信成本为O(κn³ log n)，后来由Gao等和Das等将其改进为O(κn³)。我们说这些ADKG方案是专用的，因为分布式秘密密钥是一个群元素(group element)而不是域元素(filed element)(即，gz而不是z)，因此它们不能用于大多数现成的门限加密或门限签名协议。

下表是现有DKG协议的比较

​ 文章的研究结果：针对基于离散对数的门限密码系统，设计了一种新的简单而具体有效的ADKG协议。在n个节点的异步网络中，该ADKG协议可以容忍多达t<n/3个恶意节点，并实现了O(kn³)的预期通信代价，并预期在O(log n)轮中终止。因此，我们的协议在之前已知的KokorisKogias等的通用ADKG协议的基础上，在通信方面提高了n倍，在预期运行时长方面提高了n/log n倍。对于初始化假设，Kokoris-Kogias等[43]假设随机预言机(RO Random Oracle)，我们的协议假设RO和PKI (PKI仅用于我们的ACSS构建)。

​ 在我们的协议结束时，每个节点接收到一个随机选择的秘密z∈Z_q的门限秘密共享，其中Z_q是一个大小为q的域。因此，我们的协议兼容现有的基于离散对数的门限密码系统。

​ 我们的协议还支持任何重构门限l∈[t+1,n−t]，即l个节点需要使用秘钥z(例如，生成门限签名或解密门限加密)。为了有效地获得这一特性，我们设计了一种新的加法同态高门限ACSS方案，期望通信代价为O(κn²)。我们的高门限ACSS假设随机预言机模型中判定性合数剩余(DCR)的困难，并且不需要可信设置。我们的高门限ACSS方案比之前的最佳方案提高了log n倍的通信成本。这一结果可能具有独立的意义。

评估

​ 我们实现了ADKG，并在https://github.com/sourav1547/adkg上提供了该实现。我们的实现既支持curve25519和bls12-381椭圆曲线，也支持在[t+1, n−t]范围内的任何重构门限。我们在地理上分布的Amazon EC2实例中使用多达128个节点进行评估。对于具有32个节点和二者中任一曲线的t+1重建门限，我们的单线程实现大约需要3秒，每个节点发送0.7兆字节的数据。当重建门限为n-t时，对于32个节点，我们的ADKG分别在curve25519和bls12-381椭圆曲线上需要38秒和41秒，而每个节点发送大约4.2兆字节的数据。

论文组织

• 第I节进行介绍。
• 第II节中，我们描述了我们的系统模型，定义了ADKG问题，并概述了我们的ADKG协议。
• 第III节中描述了我们的方案中使用的预备条件。
• 第IV节给出了ADKG协议的详细设计。
• 第V节对ADKG协议的详细设计进行了分析。
• 第VI节简要地描述了如何扩展我们的ADKG协议以支持高达n−t的重构门限。
• 第VII节描述了我们新的具有二次通信代价的加同态高门限ACSS方案。
• 第VIII节，我们提供了实现细节和评估结果。
• 第IX节讨论相关工作。
• 第X节总结。

II 系统模型和概述

A.符号和系统模型

​ 我们用κ表示安全参数。例如，当我们使用抗碰撞哈希函数时，κ表示哈希函数输出的大小。我们用|S|表示集合S的大小。设Z_q是一个阶为q的有限域。对于任意整数a，用[a]表示有序集合{1,2,…,a}。对于a < b的两个整数a和b，用[a, b]表示有序集合{a, a + 1,…,b}。

​ 威胁模型和网络假设:我们考虑一个有n个节点的网络，其中每一对节点都通过一对身份验证通道连接。我们考虑存在一个恶意对手A，它可以破坏网络中至多t个节点，而总节点数最少为3t+1个。我们假设网络是异步的，即A可以任意延迟任何消息，但最终必须在诚实节点之间传递所有消息。

B. ADKG的定义

​ 如I所述，在本文中，我们重点研究了基于离散对数的密码系统的ADKG，如ElGamal加密和BLS签名。我们的定义受到Gennaro等人对DKG定义的启发。

​ 离散对数密码系统的DKG相当于秘密共享一个均匀随机值z∈Z_q，并公开值y=h^z，其中h是q阶群G的随机数发生器。

​ 在协议结束时，n个节点每个节点输出秘密z的(n,l)Shamir的门限秘密共享(此处(n,l)表示，在n个节点中，需要至少l个节点才能还原出z，通常表达为(l,n))，其中需要l份共享才能使用z。更准确地说，设p(·)∈Z_q[x]是一个l-1次的随机多项式，使得p(0) = z。

​ 在DKG协议结束时，第i个节点输出他那份密钥z_i = p(i)，每个节点输出公钥y=h^z。即使存在破坏最多t个节点的对手A，ADKG协议依旧保持以下正确性和保密性属性，则该协议可以称为t-secure。

正确性Correctness：

• Correctness 1诚实的部分节点提供的l份子集定义了同一个唯一密钥z。

• Correctness 2所有诚实节点输出相同的公钥y=h^z，其中z是(Correctness 1)所保证的唯一秘密。

• Correctness 3秘钥z在计算上与Z_q中的均匀随机元素无法区分。

  此外，门限签名和门限加密等DKG应用程序要求除公钥y外，所有节点的门限公钥也都是公开的。因此，我们添加了Correctness 4。

• Correctness 4所有诚实节点同意并输出所有节点的门限公钥。节点j的门限公钥为y_j = h^z_j。

保密性Secrecy:

• 除了公钥y=h^z之外，没有任何关于秘密z的信息可以被可以计算有限次的对手(不能无限次计算)所了解。

​ 我们根据可模拟性来定义秘密性:对于可以破坏最多t个节点的概率多项式时间(PPT)对手A，存在一个概率多项式时间模拟器S，这样在一个均匀随机元素y∈G的输入上，产生一个与A的ADKG协议运行视图无法区分的视图，该视图以y作为其公钥输出结束。(即对于能够以概率多项式时间复杂性进行攻击的对手，存在模拟器S可以模拟ADKG协议的运行过程，并产生与真实的运行结果几乎无法区分的输出。则代表任何PPT对抗者也无法区分真实运行结果和模拟运行结果。)

C.协议概述

​ 现有的DKG协议具有以下典型结构:每个节点运行一个可验证秘密共享(VSS)的并发实例，与其他每个节点共享一个随机选择的秘密。一旦t+1个节点的秘密共享完成，节点在本地聚合它们的份额以计算最终秘钥z的份额。简单地说，聚合的秘钥包含至少一个诚实节点的贡献，因此对对手保持隐藏。(因为最多有t个恶意节点，t+1个节点里面中至少有一个诚实节点，因此拥有t个恶意节点的对手无法获得这个聚合的秘钥。)

​ 尽管这个想法很简单，但是要在异步网络中实现这个想法还存在许多挑战。最大的挑战是决定哪些份额聚合成为最终密钥z。众所周知，在异步下达成协议需要随机性，通常是共享随机性。现有的高效生成共享随机性的机制通常需要门限秘密共享密钥，这就造成了循环。先前工作的低效率或缺乏通用性往往是由于处理这种循环的困难。

​ 我们使用图1所示的新方法来解决这个循环问题。在节点完成其秘密共享步骤后，我们让每个节点使用可靠广播(RBC)提出一组它认为正确执行了秘密共享的节点。我们将节点i提出的集合称为第i个中间密钥集合，并用T_i表示。然后我们运行n个并发异步拜占庭二进制协议(ABA)实例。第i个ABA实例使用第i个中间密钥集合T_i来生成共享随机性。第i个ABA实例的输出决定是否应该将T_i包含在最终键中。最后，一旦所有的ABA实例终止，我们使用Neji等人的方法来计算最终的公钥h^z。

然而，上述方法仍然面临两个挑战：

• Challenge 1 确保所有诚实节点都收到生成共享随机性和计算最终秘钥z的共享所需的所有份额。

​ 根据定义，异步可验证秘密共享(AVSS)方案允许足够多的诚实节点(但不是所有节点)从dealer那里接收其共享。通常会出现这样一种情况，当恶意的dealer将有效份额发送给诚实节点的子集时，恶意的节点也声称拥有份额，以至于所有诚实节点终止共享阶段。因此，对于AVSS，可能不是所有诚实节点都接收到包含在中间密钥集合T_i中的每个AVSS实例的共享。这种情况禁止节点在T_i中聚合AVSS实例，这(节点在T_i中聚合AVSS实例)是生成共享随机性和计算其最终秘钥z的份额所必需的。

​ 我们用两个想法来解决这个问题。首先，我们使用异步完全秘密共享(ACSS)代替VSS。ACSS的一个关键性质是，它确保如果它在一个诚实节点成功终止，那么所有诚实节点最终都将获得有效的共享。其次，诚实节点i只有在T_j中的每个ACSS实例都在节点i终止后才会参与密钥集提案T_j的可靠广播(RBC)。这保证了如果一个RBC实例在任何一个诚实节点上传递了T_j，那么T_j中的每个ACSS实例最终都会在所有诚实节点上终止，从而进一步保证了诚实节点可以构造第j个异步拜占庭二进制实例(ABA)的共享随机性以及最终的秘密密钥。

• Challenge 2 确保所有的ABA实例终止，即使一些恶意节点没有发送它们的中间密钥集合。

​ 到目前为止，我们所描述的方法中存在一个不易察觉的活性问题。如果一个恶意节点j没有提出第j个中间密钥集合，那么对于第j个ABA来说，就没有可用的共享随机性来规避FLP不可能性。为了解决这个问题，我们做出了关键的观察，即FLP不可能性仅适用于初始状态为二值的情况，即诚实节点具有不同的输入。对于一元初始状态，即所有诚实节点具有相同的输入，不存在FLP不可能性，协议可以在没有任何随机性的情况下终止。因此，我们设计了我们的协议，以确保如果恶意节点不提出中间密钥集合，它将导致ABA的单价初始状态。特别是，在这种情况下，所有诚实节点输入0，我们需要ABA在不使用随机性的情况下输出0。我们将此属性称为Good-Case-Coin-Free，实际上，由于Crain的ABA协议具有此属性。因此，要么所有诚实节点向ABA输入0，并确定地终止，要么由于ACSS，最终所有诚实节点都收到中间密钥集合，从而可以生成共享随机性以规避FLP不可能性。

III 预备条件

在本节中，我们将描述ADKG协议中使用的初始设置。我们在表二中总结了论文中使用的符号。

Table II

符号	描述
n	总节点数
t	最大恶意节点数
Zq	q阶域，q为素数
G	q阶群，且该群的DDH问题难解
g, h	G的随机独立生成元
z, hz	ADKG私钥和公钥
zi	节点i输出的z的秘密份额(节点i的门限私钥)
hzi	节点i的门限公钥
l	ADKG重构门限(l份秘密份额即可重构秘密)
κ	安全参数
pki, ski	第i个节点的公钥和私钥
si	节点i在共享阶段选择的秘密
pi(·)	第i个节点分享si所选择的多项式
vi	多项式pi(·)的Feldman commitment
si,j	pi(j)，pi(·)多项式在j处的值
vi,j	si,j的commitment，具体计算为gsi,j
Ti	RBC中节点i提出的中间密钥集合
Ti‘	终止于节点i的ACSS的索引

A.经过验证的可靠广播RBC

• Definition 1 RBC：一组节点{1,….,n}的协议，其中被称为广播者的区分节点持有初始输入M，如果满足以下属性，则是可靠广播(RBC)协议：

• 一致性:如果一个诚实节点输出消息m’，另一个诚实节点输出消息m’’，则m’=m’’。
• 有效性:如果广播者是诚实的，所有诚实的节点最终输出消息M。
• 整体性:如果一个诚实节点输出一条消息，那么每个诚实节点最终都会输出一条消息。

​ 我们将使用最近验证的RBC协议。对于消息M，其通信代价为O(n|M|+κn²)，其中|M|为M的大小，κ为抗碰撞哈希函数的输出大小。

B.异步完全秘密共享ACSS

• Definition 2 ACSS：ACSS协议包括两个阶段:共享和重构。在共享阶段，dealer L使用Sh共享秘密s。在重构阶段，节点使用Rec恢复秘密。我们说(Sh,Rec)是一个可复原的ACSS协议，如果以下属性对控制最多t个节点的对手具有1−negl(κ)（negl为可忽略函数）的概率:

Termination终止性:

• 如果dealer L是诚实的，那么每个诚实的节点最终都会终止Sh协议。
• 如果一个诚实节点终止了Sh协议，那么每个诚实节点最终都会终止Sh协议。
• 如果所有诚实节点都启动Rec，那么每个诚实节点最终都会终止Rec。

Correctness正确性:

• 如果L是诚实的，则每个诚实节点在终止Rec时输出共享密钥s。
• 如果某个诚实节点终止了Sh，则存在一个固定的秘密s’∈Z_q，使得每个诚实节点在完成Rec后都会输出s’。

Secrecy保密性:

• 如果L是诚实的，并且没有诚实的节点已经开始执行Rec，那么最多破坏t个节点的对手没有关于s的信息。

Completeness完备性:

• 如果某个诚实节点终止了Sh，那么存在一个Z_q上的t次多项式p(·)，使得p(0) = s’，并且每个诚实节点i最终将持有一份s_i=p(i)。而且，当L是诚实的时候，s’=s。

​ 我们需要稍微放宽上述标准secrecy保密性概念:对于均匀随机的s∈Z_q，我们允许ACSS对随机生成元g∈G透露g^s。我们在V中证明，透露g^s并不影响我们的ADKG协议的secrecy保密性质。

​ 我们还要求ACSS方案满足下列Homomorphic-Partial-Commitment性质:

• 同态部分承诺(Homomorphic-Partial-Commitment HPC):如果某些诚实节点为秘密s终止Sh，则每个诚实节点为所有i输出s_i的承诺(如Completeness中定义的)。此外，这些Commitment在不同的ACSS实例之间是加法同态的。

​ 我们需要Homomorphic-Partial-Commitment属性有两个原因:首先，我们需要节点输出每个节点的门限公钥h^zj；第二，我们需要汇总不同ACSS实例的Commitment。

​ 我们观察到，如果一个ACSS协议输出一个底层多项式的Feldman Commitment，那么它保证了Homomorphic-Partial-Commitment。接下来我们简要地描述Feldman多项式的Commitment。

Feldman polynomial Commitment.
$$
p(x)=a_0+a_1x+a_2x^2+…+a_dx^d
$$
​ 随机d次多项式的承诺对于每个k∈[0,d]的均匀随机系数a_k∈Z_q，是一个如下计算的向量v:
$$
v=[g^{a_0},g^{a_1},g^{a_2},…,g^{a_d},]
$$
​ 很容易看出，给定多项式p(·)的费尔德曼承诺，我们可以通过在指数中插入p(i)来计算p(i)的承诺g^p(i)。同样，给定多项式p(·)和p‘(·)，命题g^p(i)和g^p’(i)是加法同态的。注意，这个承诺并不是完全隐藏的，因为它泄漏了每个k∈[0,d]的g^a_k。我们在V中表明，泄露g^a_k并不违反我们的ADKG的保密属性secrecy。同样，承诺的大小在d中是线性的。给定承诺v和共享s_i，节点通过下面公式检查是否s_i=p(i)
$$
g^{s_i}=\sum_{k=1}^dv_k^{i^k}
$$
​ 在本文中，我们使用了两种不同的ACSS协议;Das等人提出的在Yurek等人的基础上改进的ACSS方案，以及我们在VII中提出的新的ACSS方案。我们将把一个费尔德曼承诺合并到它们中，以确保它们的HPC同态部分承诺性质。

​ 对于Das等人的ACSS格式，我们可以简单地使用Feldman承诺代替底层多项式的Pedersen承诺。我们在VII中的高门限ACSS通过构造输出费尔德曼承诺。

C.异步二进制协议ABA

Definition 2 ABA：一组节点{1,….,n}的协议，每个节点持有初始二进制输入b∈{0,1}，如果以下属性在异步下成立则是一个异步二进制协议(ABA)协议：

• 一致性:没有两个诚实节点输出不同的值。
• 有效性:如果所有诚实节点的输入值相同，则没有诚实节点输出不同的值。
• 终止性:每个诚实节点最终都会输出一个值。

​ 所有ABA协议都依赖于随机化来规避FLP不可能性。最有效的方法是使用共享随机性，这是由抛硬币协议提供的。我们的ADKG协议需要具有以下额外属性的ABA协议。

• Good-Case-Coin-Free:如果所有诚实节点向ABA输入相同的值，则所有诚实节点不调用抛硬币输出。

​ crain的ABA协议具有Good-Case-CoinFree特性。它期望O(n²)通信和O(1)轮。为了完整起见，我们在附录B中提供了Crain的ABA的伪代码，并解释了为什么它满足Good-Case-Coin-Free属性。

IV ADKG协议的详细设计

​ 我们的ADKG协议有四个阶段:共享、密钥集提议、共识和密钥派生。前三个阶段具有类似的结构，我们分别运行n个并发的ACSS、RBC和ABA实例，其中每个节点启动一个ACSS和RBC实例，每个ABA实例就相应的RBC是否终止达成一致。我们将节点i调用或关联的ACSS (RBC或ABA)称为i^th ACSS (RBC或ABA)。我们在算法1中给出了ADKG协议的伪代码，并对每个阶段进行了描述。

​ 除了ACSS协议的其他公共参数外，我们的ADKG协议的公共参数是一对随机独立选择的素数阶群G的生成元(g, h)。在本节中，我们将重点关注l=t+1的情况(参见II-B)。

A.共享阶段

​ 在共享阶段，每个节点i采样一个均匀随机的秘密s_i∈Z_q，并使用ACSS方案与所有其他节点秘密共享(算法1中的1-2行)。

​ 对于l=t+1，我们使用来自Das等人的ACSS方案，但将其Pedersen多项式承诺替换为Feldman多项式承诺，以实现同态部分承诺。这只需要使用零多项式作为Pedersens多项式承诺中的隐藏多项式。

​ 设p(·)为t次多项式，
$$
p_i(x)=s_i+a_{i,1}x+a_{i,2}x^2+…+a_{i,t}x^t
$$
​ 其中a_i,k←Z_q随机选取。由于ACSS的完备性，一旦第i个ACSS实例终止，所有诚实节点都会在p_i(·)上输出一个求值点。每个节点额外输出p_i(·)的费尔德曼承诺v_i，
$$
v_i=[g^{s_i},g^{a_{i,1}},g^{a_{i,2}},…,g^{a_{i,t}}]
$$

B.密钥集提案阶段

​ 在密钥集提案阶段，每个节点i维护已终止的ACSS实例的一组T’_i(代码第11-15行)。特别是，每当第j个ACSS在节点i处终止时，节点i将索引j添加到集合T’_i(第15行)，并将其共享s_j,i=p_j(i)(节点j选择的秘密)添加到集合S_i(第14行)。设T_i为终止于节点i的第一个t+1个ACSS实例。节点i启动RBC将T_i广播到所有其他节点(第16-18行)。直观地说，T_i是节点i对一组节点的建议，这组节点的秘密将被聚合为最终的密钥z。

​ 这里需要注意的一个关键点是，每个节点i仅在T_j⊆T’_i(第19行)之后才参与第j个RBC，此时T_j中指定的所有ACSS实例都在节点i处终止。因此，如果RBC(T_j)终止，则至少有t+1个诚实节点保证Tj中的每个ACSS实例都已终止。因此，由于ACSS的完备性，对于每一个k∈T_j，第k个ACSS实例最终会在所有诚实节点处终止，并且每个诚实节点最终都会收到一份有效的秘密s_k。

C.共识阶段

​ 在共识阶段，节点尝试将上一阶段的有效密钥集提案得到一致的子集。然后，我们使用这些密钥集提案中的元素的并集来派生最终的秘密密钥。如前所述，如果节点i中的每个ACSS实例都已终止，则节点i的密钥集提案T_i有效。为了在提案的子集上达成一致，节点启动n个并发ABA实例，其中第j个ABA实例试图确定第j个键集建议是否有效。如果第j个键集建议RBC在节点i成功终止，节点i将向第j个ABA实例输入1(第21-24行)。此外，如果第j个ABA实例需要任何共享随机性，则节点使用T_j来生成共享随机性。更具体地说，设u_j为以下值：
$$
u_j=\sum_{k\in{T_j}}S_k
$$
​ 然后，在第j个ABA实例期间，每当需要投一次硬币时，因为具有共享密钥u_j节点使用Diffie-Hellman门限投币协议(第25-26行)。节点i在u_j中的份额为
$$
u_{i,j}=\sum_{k\in{T_j}}S_k
$$
​ 我们可以使用ACSS的同态部分承诺属性允许每个节点本地计算g^u_j和g^u_i,j用于让所有i和j完成抛硬币设置。

​ 如II的challenge 2所述，如果第j个节点是恶意的，并且没有可靠地广播密钥集合，则节点将无法访问第j个ABA中的共享随机性。在这种情况下，所有诚实节点将向该ABA输入0，并且由于Good-Case-Coin-Free属性，该ABA将在不使用抛硬币的情况下终止。对于二值情况，诚实节点向ABA输入不同的值，至少有一个诚实节点向ABA输入1。这意味着至少有一个诚实节点收到了中间密钥集合。通过ACSS的完备性和RBC的完备性，所有诚实节点最终也会收到中间密钥集合。

​ 最后，为了确保不是所有的ABA都以0结束，我们将使用Ben-Or等人的精妙想法。简而言之，每个诚实节点向所有密钥集提议阶段成功结束的ABA输入1，避免向任何ABA输入0直到至少一个ABA以1结束(第29-31行)。一旦一个ABA以1结束，每个节点将向所有尚未输入任何内容的剩余ABA输入0。使用类似于Ben-Or等人的分析，我们在Lemma 1（第V节分析中的内容）中表明，至少有一个ABA将以1终止。

D. 密钥派生阶段

​ 如果第j个ABA以1结束，我们说第j个键集提议被接受。设T为至少包含在一个可接受的密钥集提议中的节点集(第29-30行)。注意|T|≥t +1。然后，我们使用T导出最终的ADKG KEY为：
$$
z=\sum_{j\in{T}}s_j
$$
​ 为了计算最终的ADKG公钥h^z，每个节点i在本地计算h^z_i，其中
$$
z_i=\sum_{j\in{T}}s_{j,i}
$$
​ z_i是的密钥z的一部分份额。每个节点i还计算一个NIZK证明(非交互零知识证明)π_i(第43行)，
$$
\log_{g}g^{z_i}=\log_{h}h^{z_i}
$$
​ 这里log_g和log_h分别表示以g和h为底的离散对数。为此，我们对这个提案使用ChaumPedersen协议的非交互式变体。注意，对于任何给定的i，由于ACSS的同态部分承诺，所有诚实节点都可以使用T中包含的ACSS实例的部分承诺来计算g^z_i。

​ 最后，每个节点i将<KEY,h^z_i,π_i>发送给所有其他节点。节点接收到有效的<KEY,h^z_i,π_i>消息后，利用拉格朗日插值法计算出每个j∈[n]的公钥h^z和门限公钥h^z_j(第49-51行)。

V 对ADKG协议的详细设计进行分析

A. Correctness 为了证明正确性，我们将首先证明我们的ADKG协议在所有诚实节点处终止，并且在终止时，所有诚实节点就其输入包含在最终秘钥中的节点集达成一致。

• Lemma 1. 算法1在所有诚实节点处终止，所有诚实节点输出相同的节点集，这些节点的输入将包含在最终密钥中。
• Lemma 2 (Correctness C1 and C2). 诚实节点拥有的t+1份份额的所有子集定义唯一密钥z，此外，所有诚实节点输出相同的公钥y = h^z。
• Lemma 3 (Correctness C3). 假设决策Diffie-Hellman(DDH问题)的困难程度，密钥z在计算上与Z_q中的均匀随机元素是不可区分的。
• Lemma 4 (Correctness C4). 所有诚实节点都同意并输出所有节点的门限公钥。节点j的门限公钥为y_j=h^z_j。

B. Secrecy

​ 我们使用可模拟性来证明保密性。特别是，我们证明了对于每个概率多项式时间(PPT)静态对手A，它最多破坏t个节点，存在一个PPT模拟器S，它将一个均匀随机元素y∈G作为输入，并产生一个视图，该视图与输出y作为其公钥的ADKG协议运行的A视图无法区分。

• Lemma 5 (Secrecy S1). 假设DDH (Decisional Diffie-Hellman)问题的难度，一个最多破坏t个节点的PPT(概率多项式时间)的对手a除了从公钥y = h^z中揭示的信息外，没有获得关于秘密z的信息。

C. Performance

• Lemma 6. 我们的ADKG协议的预期总通信成本为O(n³)。
• Lemma 7. 在我们的ADKG协议中，以椭圆曲线幂次的次数来衡量，每个节点的预期计算成本为O(κn³)。
• Lemma 8. 我们的ADKG协议预期在O(log n)轮内终止。
• Theorem 1 在总结点n个、恶意节点最多t个、n≥3t+1的网络中，假设decision Diffie-HellmanDDH问题的难度，算法1实现ADKG协议，期望通信代价为O(κn³)，每个节点的期望计算代价为O(n³)，期望O(log n)轮数(κ为安全参数)。

VI 高门限ADKG协议

​ 到目前为止，我们已经讨论了门限为l=t+1的ADKG协议，即最终密钥是使用(n, t+1)门限秘密共享在节点之间共享的秘密。然而，许多应用要求秘钥通过(n, n−t)门限秘密共享共享。在这里，我们将引用一个ADKG协议，该协议使用l>t +1的门限作为高门限ADKG来共享秘密。在本节中，我们将描述如何扩展ADKG协议以支持高门限。

​ Design. 获得高门限ADKG所需的唯一更改是在共享阶段使用具有III-B中指定属性的高门限ACSS方案。协议的其余部分可以完全按照IV进行。

​ 但是，设计一个具有我们期望属性的高效高门限ACSS方案是具有挑战性的。先前最著名的具有这些特性的高门限ACSS是由于Kokoris Kogias等人的ADKG协议。然而，他们的ACSS的通信成本为O(κn³)，成本过高。Alhaddad等人和Das等人的高门限ACSS协议的通信代价分别为O(κn² log n)和O(κn²)，但不提供所需的同态部分承诺特性。我们设计了一种新的高门限ACSS，在保留Das等人的O(κn2)通信复杂度的同时，增加了同态部分承诺特性。我们在VII中提供了关于高门限ACSS的更多细节。

​ Analysis. 由于我们引入的唯一变化是使用高门限ACSS，因此我们的高门限ADKG的正确性直接来自V中的正确性分析。

​ 对于机密性secrecy，我们需要确保给定的机密s的g^s的高门限ACSS方案是可模拟的。

VII 高门限异步完全秘密共享ACSS

​ 本节描述了一种新的高门限ACSS方案，在保留Das等人方案的$$O(κn^2)$$通信复杂度的同时，增加了同态部分承诺特性。

​ 简而言之，我们需要离散对数的可验证加密，即，一个CPA-secure(选择明文攻击安全)的加密方案，允许加密者在对已知值的离散对数的正确加密进行零知识证明。我们使用基于Fouque的方案，该方案假定判定复合残差(DCR)困难。

A. 离散对数可验证加密

​ 离散对数的可验证加密问题涉及三方:证明者P、验证者V和接收者R。接收者R有一个公私钥对(pk, sk)。设G是一个合适的群，g∈G是G的一个随机生成元。给定(G, x, c, pk)，证明者P想让验证者V相信c是公钥pk下明文α的一个公钥加密密文，g^α=x且P知道α。

​ Fouque和Stern的离散对数可验证加密的协议是一个“Σ-protocol”，是零知识和知识可靠的。该协议有以下接口：

• KeyGen(1^k)→(pk, sk)。KeyGen算法为加密方案输出一个公私钥对。
• Decrypt(sk, c)→α:给定密文c和私钥sk, Decrypt使用sk对c进行解密并输出明文a。
• EncAndProve(pk, g, α)→(c, x, π): EncAndProve函数使用公钥pk对均匀随机消息α加密得到c，计算x=g^α，并创建一个NIZK proof(非交互式零知识证明)π，证明加密者知道存在a使得α=Decrypt(pk, c)且x=g^α。
• VerifyDLog(pk, g, x, c, π)→0/1。给定(pk, g, x, c, π)，如果π是存在a使得α=Decrypt(pk, c)且x=g^α的有效证明，则VerifyDLog(·)输出1。请注意，非交互式零知识证明π需要在不访问密钥或底层消息α的情况下进行验证。

B. 设计与分析

​ 我们的高门限ACSS在算法2中给出。我们的算法2与Das等人的高门限ACSS的主要区别在于dealer加密份额和计算相应的NIZK证明的方式。

​ 在共享阶段，为了共享一个均匀随机的秘密s∈Z_q，dealer L对随机(l−1)次多项式p(·)进行检查，使p(0)=s。对每个j∈[n]，L计算(v_j, c_j, π_j)←EncAndProve(pk_j, g, p(j))。设
$$
v={v_1,…,v_n},c={c_1,…,c_n},and\space\space\pi={\pi_1,…,\pi_n}.
$$
​ 我们将把v、c、π分别作为承诺向量、加密向量和证明向量。然后，dealer L使用经过验证的RBC协议发送元组(v, c, π)。在经过验证的RBC协议中，只有断定$$P(·)$$返回true时，节点才会参与。在我们的例子中，这要求

​ (i) v是不超过l - 1次多项式的承诺;

​ (ii)对于每个元组(v_j, c_j, π_j)， VerifyDLog(pk_j, g, v_j, c_j, π_j)=1，即c_j是$$ \log_{g} v_j$$在节点j的公钥pk_j下的加密。

​ 对于多项式承诺v的幂次检验，我们使用Cascudo等人的方法。

​ 在重构阶段，每个节点$$i$$解密$$c[i]$$以恢复其份额$$\tilde{s}_i:=Decrypt(sk_i, c[i])$$。节点$$i$$然后向所有其他节点多播$$\tilde{s}_i$$。节点$$j$$从节点$$i$$接收到$$\tilde{s}_i$$后，检查$$v[i]$$是否等于$$g^{\tilde{s}_i}$$。在接收到$$l$$个或多个有效份额后，节点使用拉格朗日插值重建秘密。

​ 现在我们分析算法2中的ACSS方案。我们的ACSS的终止遵循RBC的终止属性和EncAndProve的完备性属性。同样，我们的ACSS的完备性(Completeness)来自于EncAndProve的可靠性(Soundness)和RBC的整体性(Totality)。我们的ACSS的正确性直接取决于底层零知识协议的可靠性(Soundness)。此外，由于dealer可靠地广播多项式的费尔德曼承诺，我们的ACSS具有同态部分承诺性质。其具备Secrecy。

​ Lemma 9. 对于均匀随机s，给定$$g^s$$，假设决策复合残差(DCR问题)的难度和随机Oracle的存在，存在一个PPT模拟器，可以模拟任意静态PPT对手的观察。(PPT，概率多项式时间。)

​ 现在，让我们分析高门限ACSS的通信成本。观察到每个v, c和π都是κn位长。因此，使用Das等人的RBC协议，在共享阶段的通信成本为$$O(κn^2)$$。在重构阶段，每个节点多播$$O(κ)$$位，因此重构阶段的通信代价为$$O(κn^2)$$。因此，总通信成本为$$O(κn^2)$$。

VIII 应用与评估

A.实现细节

​ 我们使用python 3.7.6在开源hbACSS库之上实现了ADKG协议的原型，用于重构任何范围在$$l∈[t+1,n−t]$$的门限。

​ 我们使用Rust库进行椭圆曲线操作，使用asyncio实现并发，尽管我们的原型只在单个处理器核心上运行。对于$$l=t+1$$，我们使用Das等人的ACSS协议。对于$$l≥t+1$$，我们从VII中实现ACSS协议。在这里，我们将前者称为低门限ACSS，将后者称为高门限ACSS。我们使用带有默认参数的python phe库来执行DCR操作。我们还实现了Crain的ABA协议和Das等人的RBC。

​ 在我们的实现中，我们同时使用了曲线25519和bls12-381椭圆曲线。我们在[curve25519](https://github.
com/dalek-cryptography/curve25519-dalek)实现和Zcash的bls12-381实现上使用Ristretto群来进行基本的椭圆曲线操作(每个都有python装饰器)。注意，bls12-381支持配对，因此我们的实现可用于双线性门限密码系统，如Boldyreva的。然而，有效实现双线性对的椭圆曲线的缺点是，在通信和计算成本方面，对于不需要它们的应用效率较低。例如，curve25519中的group元素是32字节，而bls12-381中的group元素是48字节和96字节。此外，我们的micro-benchmark(小规模基准测试)表明，bls12-381中的群幂比curve25519慢6倍。

​ 在常见情况下，即当所有节点都是诚实的，网络具有较小的延迟时，我们提升了ADKG协议的带宽使用和每个节点的运行时间。我们实现了以下优化:

​ (1)RBC协议(Das等人)的数据传播步骤，涉及纠错和两轮通信，除非有节点触发，否则可以省略。这在通常情况下减少了大约50%的带宽使用;

​ (2)在通常情况下，大多数ABA实例在没有coin的情况下终止;因此，我们从未显式地计算那些ABA实例的门限密钥。我们观察到，对于通常情况下$$l=t+1$$的ADKG实现，此优化减少了约65%运行时间。

B.评估设置

​ 我们使用不同数量的节点来评估我们的ADKG实现:16、32、64、128。对于给定$$n≥3t+1$$，我们用$$t+1和2t+1$$两个重构门限求值。我们在Amazon Web Services (AWS)t3a.medium虚拟机上以一台虚拟机运行一个节点的方式运行所有节点。每个虚拟机有两个vcpu(虚拟cpu)和4GB内存并且运行Ubuntu 20.04。

​ 我们将节点均匀地放置在八个不同的AWS区域:加拿大、爱尔兰、北加利福尼亚、北弗吉尼亚、俄勒冈、俄亥俄、新加坡和东京。我们在节点之间创建一个覆盖网络，其中所有节点都是成对连接的，即它们形成一个完整的图。

​ Baselines. 由于没有任何ADKG的实现，我们只比较Gennaro等人在Drand中实现的同步DKG。据我们所知，Drand是目前唯一使用的DKG协议。其他同步DKG的实现侧重于加密部分，而不实现网络部分。我们用默认的重门限$$n/2+1$$来评估Drand。我们最多只能运行64个节点的Drand;128个节点的Drand在我们的实验中异常终止。

C.评价结果

​ 我们的目标是通过评估证明我们的ADKG协议可以很好地随节点数量扩展并具有合理的运行时和带宽使用。

​ Runtime. 我们测量ADKG协议开始和节点输出共享公钥及其秘密共享之间的时间差。然后，我们计算所有节点的平均时间，以计算ADKG协议的运行时间。我们在图5中报告结果。

​ 对于l=t+1，我们的ADKG协议在64个节点上大约需要10秒，仅为Drand的19%。然而，当l=2t+1时，我们的ADKG协议需要更长的时间:64个节点需要160秒，大约是Drand的3倍。

​ 经过仔细检查，我们发现当l=t+1时，各种各样的步骤占据了运行时的大部分时间，而当l=2t+1时，Paillier操作占据了运行时大部分时间。表三证实了这一点。具体来说，一个高门限ACSS实例需要每个节点进行O(n)次Paillier操作，从而导致在高门限ADKG的共享阶段每个节点进行$$O(n^2)$$次Paillier操作。

​ Running time of sharing phase. 我们测量ADKG协议共享阶段的每个节点运行时间。更具体地说，首先我们分别测量dealer和非dealer节点的运行时间。然后将共享阶段的运行时间计算为一个dealer节点的运行时间与n个非dealer节点的运行时间之和。我们在表III中报告了结果。观察到，当l=t+1时，即使有128个节点，共享阶段的运行时间也不到我们ADKG协议总运行时间的7%。而当l=2t+1时，对于64个节点，ACSS步骤(共享阶段)的计算时间占总运行时间的80%以上。

​ **Bandwidth usage. **我们用整个ADKG协议中节点发送的字节数来衡量带宽使用情况。我们在图4中报告每个节点的带宽使用情况。与V的分析一致，我们协议的带宽使用随着节点数量的增加呈平方增长。

​ 我们的带宽使用明显低于Drand。以64节点实验为例，Drand的每个节点发送93.8M字节的数据;在我们的ADKG中，当l=t+1时，每个节点只发送2.96兆字节，仅为rand的1/30;当l=2t+1时，每个节点发送19.2兆字节，仍然只有rand的1/5。我们注意到，高门限的高带宽使用率再次来自高门限ACSS方案。

​ 我们还注意到，尽管在bls12-381中群元素比在curve25519中长16个字节，但由于其他数据(如DCR群元素、域整数和哈希)的可比较成本，这对协议的总带宽使用没有明显影响。

IX 相关工作

​ 从Pedersen的开创性工作开始，许多工作研究了具有各种加密假设，网络条件和其他属性的分布式密钥生成问题。我们根据网络假设将先前的工作大致分为两类:同步和异步。

​ Synchronous DKG. 同步网络中的DKG已经研究了几十年。Pedersen提出了第一个使用可验证秘密共享的DKG协议。Gennaro等人表明Pedersen协议允许攻击者对公钥分发产生偏差，并提出了一个不存在此问题但成本较高的方案。Neji等人提出了一种简单的机制来减轻偏差攻击。我们采纳了他们的想法，但我们发现他们在原始论文中提出的证明忽略了模拟器的一些细节。在本文中，我们提出了一种新的保密证明。

​ Canetti等人扩展Gennaro等人的方案确保对自适应对手的安全。Fouque和Stern使用了可公开验证的秘密共享(PVSS)而不是VSS来使协议具有非交互性。Gurkan等人设计了一个基于PVSS的、具有线性大小公开验证传输DKG协议。然而，他们的协议只能容忍O(log n)个故障节点。此外，在他们的协议中，密钥是一个群元素而不是域元素。因此，他们的协议与现有的门限签名或加密方案不兼容。最近，growth基于新的PVSS方案设计了一个新的DKG协议;该协议是非交互式的，假设存在广播通道。此外，他的协议中的密钥是一个域元素。

​ Asynchronous DKG. 只有少数研究在半同步或异步网络中的DKG问题。Kate等人将Pedersen的DKG扩展到半同步网络。该协议的总通信成本为0 (κn⁴)，可容忍最多三分之一的恶意节点，并且协议终止依赖于同步。Tomescu等人在通信成本呈对数增长的情况下，将Kate等人的计算成本降低了O(n/log n)倍。

​ Kokoris等人设计了第一种异步DKG方案，其总通信成本为O(κn⁴)，期望轮复杂度为O(n)。Abraham等人提出了一种通信代价为O(κn³ log n)的ADKG协议，Gao等人和Das等人给出了两种方法将Abraham等人的通信代价降低到O(κn³)。由于Abraham等人使用了Gurkan等人的PVSS方案，所以这三种构造都继承了密钥为群元素的限制，ADKG不兼容现成的门限加密或签名方案。

​ Aleph的随机信标的设置阶段针对不同的ABA实例使用了不同的硬币来源。他们的工作启发了我们密钥集提案阶段。但请注意，Aleph的设置阶段不是ADKG协议，我们的ADKG协议与它有很大不同。

​ DKG implementations. 门限签名的日益普及促进了许多DKG实现。所有这些实现都假定了同步网络。

X. 总结

​ 本文针对基于离散对数的门限密码系统，提出了一种简单而具体高效的异步分布式密钥生成协议。在n个节点的网络中，我们的ADKG协议的通信开销为O(κn³)，并在预期的O(log n)轮中终止。我们的协议以模块化的方式使用了许多基本的异步原语，如ACSS、RBC、门限common coin和ABA。因此，针对这些原语的改进协议，特别是高门限ACSS，直接改进我们的ADKG协议。我们正式证明了我们的ADKG协议的安全性和正确性。并提供了一个原型实现，并在多达128个地理分布节点上评估我们的原型，以说明我们的ADKG协议的实用性。