DKG简介

很多密码学应用要求一个可信的权威持有秘钥。这种系统存在单点故障和秘钥托管的问题。分布式秘钥产生DKG（distributed key generation）通过多方参与，计算共享的公钥与私钥集，解决上述问题， 分布式秘钥产生不依赖任何可信的第三方。在(n,t)-DKG中， n为节点数量，t为阈值， DKG协议允许n个节点共同产生秘钥，使得任何数量大于阈值t的节点子集都能使用该共享秘钥，然而任何数量少于阈值t的节点子集都没有对该共享秘钥的任何知识。

可验证秘密共享 

可验证秘钥共享 (verifiable secret sharing， 简称VSS) 是DKG的基本构造块 ,VSS的概念被Shamir 和Blakley引入。

(n,t+δ, t) -秘密共享：对整数n, t ,δ 满足 n>=t+δ>t>=0 ,一个(n,t+δ, t) 秘密共享协议是被用于一个交易方（dealer） 在n个节点之间共享一个秘钥，使得其中任何t+δ或者更多的节点能够计算密钥s, 但是t个或更少的节点没有关于s的任何信息。

δ=1的秘密共享被称之为阈值秘密共享(threshold secret sharing) ，记为（n,t)-秘密共享。

在一些秘密共享应用中，客户端需要验证持续的交易（deal）来避免交易方（dealer）的恶意行为。一种拥有这种可验证性保证的模式被称之为可验证秘密共享（verifiable secret sharing) VSS 。

一个可验证秘密共享(n,t)-VSS 模式有两个阶段（phase）组成。共享阶段和重建阶段

共享阶段 ：一个交易方(dealer) 在n个节点之间分发一个秘密，K为足够大的秘钥空间。此阶段结束之后，每个诚实的节点 持有分布式秘密s中的一个秘密。

重建阶段：每个节点广播它的秘密共享，一个重建函数用于计算秘密  或者判断出是恶意的节点。对于诚实的节点 , 而对恶意节点可能不同于甚至没有 。

可验证秘密共享VSS要满足两个安全要求：

保密性（VSS-WS）：一个能够控制t个节点的敌人，在共享阶段无法计算出s。

正确性（VSS-C）：重建值应该等于共享秘密s或者每个诚实节点判断出是恶意节点。

任何t+1个或者2t+1个诚实节点能够重建s，所以引入强正确性要求。

强正确性(VSS-SC)：敌方用大于2t的节点和重建算法能重建出相同的唯一值s，进一步的，有的VSS模式需要更强的保密安全性。

强保密性(VSS-S) ：能够控制t个节点的敌方，除了共有的参数之外，没有任何关于s的信息。

同态承诺

对持续交易(deal)的验证机制是VSS的基础。验证机制是通过分布式计算技术来实现的，同态承诺（homomorphic commitments）对此提供一种有效的计算方案。

 

令  为的一个同态承诺， r 为可选的随机参数，G为乘法群。对于该同态承诺， 给定 和 ， 我们有

VSS使用两种形式的同态承诺。 设g和h为G的两个随机生成元, Feldman在他的VSS协议中使用了形如的离散对数承诺（DLog commitment）模式。Pedersen 使用了另一种形式

可以使用非交互式零知识证明证明，Pedersen承诺的值和离散对数承诺的值是相等的。

给定离散对数承诺，和Pedersen承诺  ， 对相同的s , 和生成元, ，一个证明者证明她知道s和r 使得，

记为： NIZKPK = 

分布式秘钥产生

Pedersen 引入了分布式秘钥产生(DKG)的概念，研发了一个DKG模式。 每个节点运行VSS实例，添加分布式共享(distributed shares)，在没有交易方（dealer）的情况下产生组合的共享秘钥。与VSS不同， DKG不需要可信方。

一个(n,t)-DKG模式包含两个阶段(phase)：共享阶段(sharing phase)阶段和重建阶段( reconstruction phase )

共享阶段：每个节点将一个秘密 分发到n个节点， 其中K为足够大的加法循环群。在共享阶段结束之后， 每个诚实节点持有分布式秘密s中的一个共享， 是由的线性组合计算出来的。

重建阶段： 每个节点 广播它的共享秘密，一个重建函数用于计算秘密  或者判断出是恶意的节点。对于诚实的节点 , 而对恶意节点可能不同于甚至没有 。

DKG 有很多用途。令G为阶为p的循环群， DKG协议产生共享秘密，发布 对作为对应的公钥。

Gennaro 建议 如下的保密性要求与正确性要求：

正确性 （DKG-C） 

1. 存在一个高效方法对于从2t+1个节点输入的共享值 和KDG协议 产生的公共消息，输出相同的唯一的值s, 甚至最多t个共享是被恶意节点提交的。
2. 在共享阶段结束之后， 所有的诚实节点持有相同的公钥, 其中s唯一的秘密
3. S和Y是分别在 和G中均匀分布。

保密性 （DKG-S）：敌方除了,无法知道任何关于秘密s的信息。

 

DKG在区块链中的应用

区块链作为分布式系统，区块链中的节点通过DKG分布式地产生秘钥，克服单点故障以及单个节点不可信任问题。在AnnChain OG共识算法中，  DKG与门限签名算法(BLS)结合，DKG的秘钥作为门限签名的秘钥，保证任意2/3的共识节点对一笔消息进行门限签名，都能够恢复出公钥并进行验证，具有有拜占庭容错性。

 

参考文献

1.  Aniket Kate , Yizhou Huang , Ian Goldberg. Distributed Key Generation in the Wild, 2012

2. https://www.cs.cmu.edu/~wing/publications/Wong-Wing02b.pdf