MOV 安全多方计算

概要

随着 MOV 的推出,OFMF 的门限方案也将率先落地。完整的 OFMF 是从体制体系和托管技术两方面构建可行性。在托管技术上,我们将签名托管做到极致,不仅拥有成熟的多签方案,还花了很长时间攻坚了可实用的有限方门限签名方案,使得网关托管在安全性和灵活性之间找到了平衡关系,也给系统的攻击成本和难度增加了不少。门限签名,管中窥豹,代表了我们对安全和先进密码学的自主掌控,是对这个网关和生态构建安全性的重要保障。

我们认为一个优秀的商业门限签名系统大致总结为以下几点特征:(1)无中心 dealer 的密钥生成(key generation)机制(2)降低通信复杂度(3)可实用性(4)兼容性(5)参与方隐私保护(6)灵活与其他签名方案组合保障托管安全(7)对多样性公链生态接入友好

准备工作

所谓门限 t,指在一个 n 个节点集合中,只有满足包含至少 t+1 个节点的子集才能共同协作生成签名,即门限签名,所以理论上可以防止最多 t 个节点联合作恶。

与传统中心化签名相比,门限的概念主要体现在密钥生成和签名这两个过程,需要在多方之间构造一种安全通信协议,而在验证签名这个过程,则与中心化签名一样,仅需节点自身即可进行验证(这对公链业务层是十分友好的)。

随着比特币等公链资产频繁发生失窃,最近几年门限签名在安全方面的重要意义开始得到越来越多的关注和认可,比如避免单一私钥被单一托管,门限的思想也体现了区块链去中心化共治的思想,存在多方博弈。

在比特币出现之前,Gennaro 等人为了实现一个 t 门限签名,需要在至少 2t+1 参与方之间分享密钥,并且要求至少 2t+1 方联合才能生成签名。随后 Mackenzie 等人提出 2-2 门限方案(即 t=1,n=2),相较于前者,这种方案避免了密钥被过多参与方分享而导致攻击概率上升。但 2-2 方案毕竟具有局限性,近些年来人们在不断追寻更为通用和灵活的 (t, n) 门限方案,即 n >= t+1,且只需要 t+1 方即可完成签名。但是更多的阻碍出现在了分布式密钥生成协议(DKG)上,往往都是极具消耗性的,难以用于实际生产。在这篇文章中,我们提出了一种更快速更少通信消耗的门限签名方案,不需要特别复杂的 DKG 协议。

在通用的 DSA 签名算法中,假设循环群 G 由素数阶 q 和基点 g 来定义,密钥(secret key) x 统一从以素数 q 为模数的有限域 Z/q 中随机选取,相对应的公钥(public key)为 y = g^x;定义哈希函数 H 为从任意字符串映射为 Z/q,定义另一个哈希函数 H' 为从 G 映射到 Z/q;则对于消息 M 的签名操作,计算 m = H(M),从 Z/q 中随机选取 k,计算 R = g^{k^{-1}},以及 r = H'(R);再计算 s = k(m+xr) mod q;最后获得 M 的签名 (r, s),验证签名:

如果 H'(R') = r,则验证通过。

大致我们可以看到对 DSA 门限签名的实现难度在于需要多方共同来计算 R (涉及 g 求幂和 k 求反操作)和 s (涉及两个秘密值 k 和 x 的乘操作),这种非线性的计算对多方安全计算来说是十分困难的,为此有人提出了基于 Paillier 加法同态加密的密钥分享操作。在本文中,我们受到著名的 MPC 实现 SPDZ 的启发,采用了一种不同的多方计算法:假设有两个秘密值 a 和 b 在多方之间分享,有 a = a1+...+an,b = b1+...+bn,对于参与方 Pi 拥有 ai 和 bi;此时我们需要生成 c = ab 的分享,注意到有

这需要对每一项秘密值 aibj 都进行分享;这给予我们的启示是,可以让参与方们根据各自拥有的 a 和 b 的秘密份额两两配对组合生成秘密值 aibj,基于此我们创建一种简单而又优雅的门限 ECDSA 协议。开始时,通过 (t, n)-Shamir sharing 在成员间分享密钥 x,当 t+1 成员要进行签名时,创建两个随机值分享:

然后根据上面提到的原理计算乘法分享:

(注:将 kx 最终获得的秘密值再进行一次分享,分享碎片被各成员掌握保存,以供后用)

k^{-1} 的分享:

因此可以获得 R 的多方计算:

签名的 s 值分享组合:

至此,门限 ECDSA 签名的实现原理已经清晰。

零知识证明

这里我们用到了零知识证明(ZK Proofs)来检测成员里的恶意行为,采取先签后验的方式,即如果最终的签名未验证通过则证明至少一个成员未遵循规则。但是我们需要确保这个过程中(正确执行和中止执行)诚实成员暴露的信息不会被恶意利用。

范围证明(Range Proofs)。在验证签名这一步,需要运行两次比较昂贵的零知识证明:

  1. 一次范围证明:被 Paillier 加密的值 a 是很小的

  2. 证明成员知道 x 有如下操作:

(注:其中 E 为 Paillier 加密)

我们不仅实现了高效的密钥生成协议,在签名协议上,较之前的项目,数据传输量和运行时间有了很大的改进。

通信模型

假设存在一个点对点的广播通道(broadcast channel)用于连接每一对成员通信。恶意攻击者至多控制 t 个成员(dishonest majority),且 t <= n-1,我们假设攻击者是最后“说话”的,即看到诚实成员的信息后选择自己的信息方案。不过我们也说明目前的协议并不保障 liveness,即可能无法完成协议运行。

签名算法

一个数字签名机制包括三部分算法:(1)生成公私钥:随机密钥生成算法根据安全参数的输入返回签名私钥 sk 和验证公钥 pk。

(2)签名:根据输入私钥 sk 和待签名消息 m,输出签名 sigma。

(3)验签:确定性的验证算法,根据输入公钥 pk、消息 m 以及签名 sigma,输出一个比特 b,当且仅当签名是合法的,b = 1。

门限签名

(1)门限密钥分享(threshold secret sharing)。对秘密 x 进行 (t, n) 门限分享,会生成 n 个秘密碎片,其中 t+1 碎片作为输入即可输出秘密值 x,但 t 或者小于 t 碎片无法揭示秘密。(2)门限签名(threshold signature)。简称 TS,在依赖的底层签名机制 S=(Key-Gen, Sig, Ver) 基础上使得签名操作在成员间分布式协作完成,即各自生成各自的签名碎片,由其中至少 t+1 签名碎片即可生成最终的签名,同样的,TS 由以下两部分组成:(a) Thresh-Key-Gen,分布式密钥生成协议。在给定的安全参数输入下,向每个成员输出一个总的公共公钥 pk 以及各自秘密保管的私钥碎片 ski。(b) Thresh-Sig,分布式签名协议。每个成员根据各自的 ski 对消息 m 进行签名。(注:门限签名的验签函数跟所依赖的中心化底层签名机制的验签函数是一个)

加法同态加密

加法同态加密对于给定的两个基于同态加密算法 E 的密文:

定义同态加操作:

(注:N 整数集)定义标量乘法操作:

(注:

,a 为整数,

本文中我们的协议便基于 Paillier 加法同态加密机制:(1) Key-Gen:生成两个同样长度的大素数 P 和 Q,令 N = PQ,且定义 N 的卡迈克尔函数(Carmichael function)为

选取

则公钥和私钥分别为

(2) Encryption:对于要加密的消息 m

选取 x

然后返回

(3) Decryption:要解密密文 c

定义集合运算函数

其中集合为

则解密 c 有

(4)同态属性:给定两个密文

定义

如果

则有

同样,如果给定密文

以及整数 a

则有

不可延展的多义承诺协议

通常一个(非交互)陷门承诺(trapdoor commitment)机制包含四部分算法:(1) KG:密钥生成算法,输入一个安全参数,输出密钥对 {pk, tk},其中 pk 是与承诺机制有关的公钥,tk 为陷门。(2) Com:承诺算法,输入公钥 pk 和消息 M,输出

其中 R 来自“抛硬币机”,C(M) 便是承诺(commitment string),D(M) 是在揭开承诺之前都需要秘密保存的解承诺(decommitment string)。(3) Ver:验证算法,根据输入 C、D 以及 pk,要么输出消息 M,要么输出

(4) Equiv:通过给定的陷门打开承诺算法,根据输入 pk、M、R、T 以及

以及消息

如果 T = tk,则算法输出 D',

一个陷门承诺需要满足以下属性:(a) Correctness:如果

(b) Information Theoretic Security (信息论安全):对每一个信息对 M 和 M',C(M) 和 C(M') 的分布概率接近(c) Secure Binding:简单来讲,只能有一种方法解承诺

所谓承诺是不可展的(non-malleable)指,对于给定信息 m 的承诺 C,攻击者在看到承诺打开后,不可能找到另一个承诺 C',使之可以成功解承诺后得到消息 m',否则攻击者可以换成自己的承诺,使真正的承诺无效。

数字签名标准

Kravitz 在 1991 年提出的 DSA (Digital Signature Algorithm)被 NIST 于 1994 年采纳为 Digital Signature Standard (DSS)。ECDSA 为 DSA 的椭圆曲线变种,在加密货币领域尤为受欢迎。本文的结论对传统 DSA 和 ECDSA 都是适用的。公共参数(Public Parameters)包括一个素数阶 q 的循环群 G,定义 G 的基点 g,哈希函数 H

以及另外一个哈希函数 H'

Key-Gen:给定安全参数输入,输出从有限域 Z/q 上随机选取的私钥 x,及其通过 G 计算得到的公钥 y = g^x。Sig:输入任意消息 M, 计算 m

选择 k

计算 R 以及 r

计算 s

输出签名 sigma

Ver:给定输入 M、sigma 以及 y, 检查 r 和 s

计算 R'

接受(输出为 1)当且仅当

可验证秘密分享协议 Feldman's VSS 在 Shamir 秘密分享中,对于秘密值

dealer 生成一个 t 阶多项式 p

则每个成员拥有秘密碎片

对于一个可验证秘密分享协议,会有一个辅助信息(auxiliary information)被公开,以便允许成员可以据此验证它们的秘密碎片是否始终如一并可以构建出唯一的秘密。Feldman 方案便是对于 Shamir 秘密分享的一种可验证扩展,dealer 会公开

根据这个信息,每个成员通过验证如下公式检查其秘密碎片的一致性:

如果任何一个成员验证失败,都可以提出 complaint,协议中止。

Share Conversion 分享变换

Share Conversion 分享变换 Alice 和 Bob 分别拥有秘密 a 和 b,对于 ab 的乘法分享,令 x = ab mod q,Alice 和 Bob 需要计算 x 的秘密加法分享

这里我们呈现一个基于加法同态的协议,首先假设 Alice 拥有一个整数域 N 上加法同态机制下的公钥 EA,定义一个范围 K > q。我们定义一个名叫 MtAwc 的 share conversion 协议:(1) Alice 初始化协议: (a)向 Bob 发送

(b)通过范围证明(range proof)构建零知识证明 ZK:a < K

(2) Bob 计算密文

(注:是从整数域 ZN 上随机选取的)

Bob 设置他的分享

回复 Alice: (a)发送 cB (b)构建零知识证明 ZK:b < K (c) B = g^b 是公开的

(3) Alice 解密 cB 得

如果不使用 range proof,那么在这个场景里 Alice 或者 Bob 可以通过设置大的输入导致执行对 N 的模简化运算,协议失败——签名验证失败。具体的,Alice 解密获得

为了防止对 N 的模简化运算不被执行,要求

因为我们通过 ZK proof 保证了

所以,

即忽略不计。

因此零知识证明对实现一个防止作恶的门限签名系统而言是十分关键的,我们采纳了 MacKenzie 等人在 Two-party generation of dsa signatures 提出的简化版本,基于 Strong RSA 假设。

协议细节

我们假设每个成员 Pi 都拥有加法同态加密机制下的公钥 Ei。(1)密钥生成协议(a) Phase 1:每个成员设置各自的秘密值

计算(注:用于组合公共公钥)

并广播

每个成员广播自己的 Ei。(b) Phase 2:每个成员广播

成员 Pi 对应的解承诺值为 yi,并对 ui (用于私钥)执行一个 (t, n) Feldman-VSS 操作,公共公钥可表示为

共存在 n 个并发 VSS 协议分发成员各自的秘密值,每个成员收集拼装来自其他 n-1 个成员的秘密值碎片,所以理论上在复现最终总私钥时,需要进行 n 次多方计算,最终的结果(成员各自掌握的总私钥碎片) xi 相当于是对密钥 x 的一次 (t, n) Shamir 秘密分享

对应的公钥碎片为

(c) Phase 3:RSA 模数为

每个成员需要进行零知识证明,证明自己知道 xi, pi, qi。

(2)生成签名参与签名协议的成员表示为

假设(t 为门限值)

对于分享短暂的秘密信息可以使用 (t, t) 秘密分享,而不必用通常的 (t, n) 结构。借助拉格朗日系数

S 中的每个成员可以将各自的 xi (t, n) 分享映射为 (t, t) 分享,

因为公钥碎片和系数都是公开的,所以每个成员都可以计算

(a) Phase 1:每个成员 Pi 选择各自的秘密值

并计算承诺

广播 Ci,并定义

同时注意到

(b) Phase 2:两两一对,Pi 和 Pj,参与到一个两方“乘转加”(multiplicativ-to-additive)分享变换(share conversion)的子协议中,即前面描述的 MtAwc。 (i) Pi 和 Pj 用各自的秘密值运行 MtA 协议

MtA 运行后成员 Pi (resp. Pj) 收到的分享碎片为

则获得两者的秘密值乘为

Pi 设置

这个值就是对如下最终要形成的总秘密值乘的一个 (t, t) 加法分享(additive sharing),

(ii) Pi 和 Pj 用各自的秘密值运行 MtAwc 协议

MtAwc 运行后成员 Pi (resp. Pj) 收到的分享碎片为

则获得两者的秘密值乘为

Pi 设置

这个值就是对如下最终要形成的总秘密值乘的一个 (t, t) 加法分享,

(c) Phase 3:每个成员 Pi 广播各自的

这样成员间就可以组合成

然后计算

(d) Phase 4: 每个成员 Pi 广播各自的解承诺字串 Di。Pi 解承诺后获得的值为

并且 Pi 零知识证明自己知道

成员间计算

以及

(e) Phase 5: 每个成员 Pi 设置各自的 si

注意到有

即 si 是对 s 的一个 (t, t) 分享: (5A)成员 Pi 选择

并计算

以及

并广播

(5B)成员 Pi 广播

并零知识证明自己知道:

如果 ZK proof 失败,协议中止。令,

(5C)成员 Pi 计算

计算承诺

并广播

(5D)成员 Pi 广播

解承诺

如果

协议中止。(5E)否则 Pi 广播 si,成员间计算最终的 s

如果 (r, s) 是合法的签名,则接受。

要说明的是,为了提高零知识证明的效率,我们构造的最终签名并不能保证一定正确,所以存在被拒绝的可能性。在第五步中,并没有简单让成员们去揭开 si 并组装,否则存在安全问题——攻击者通过让协议失败获取到其他诚实成员的 si (机密信息泄露)。所以我们采用了组合

即用随机值来“掩饰”

将这个组合值“randomize”处理得

成员间通过一个分布式“Diffie-Hellman”交换计算 U。如果这个分布式随机签名验证成功,那就可以安全地揭开 si,如果验证失败,则协议中止,诚实成员的 si 永远不会被暴露。

结论

我们提出了一个先进的门限 ECDSA 签名协议,可以用于 Bitcoin 或者用户钱包保障安全。其他协议往往存在一个无法被实用的分布式密钥生成协议,需要依赖一个可信的中心 dealer (分发者)分发密钥,也就存在了单点故障。而我们的协议实现了一个全新的高效 DKG 协议,拥有可实用的运行时间和数据量传输。我们相信,ECDSA 门限签名已经快要进入成熟商业应用了。

results matching ""

    No results matching ""