区块链中的数学 - Feldman的可验证的密钥分享

  • blocksight
  • 更新于 2020-11-24 21:49
  • 阅读 7607

Feldman的方案提供了可验证的密钥分享机制,验证子密钥的正确性的关键是密钥分发者公布了承诺信息$(c_i)$,$c_i$ 绑定了多项式系数,从而使得每个参与者收到的承诺都来自同一个多项式

写在前面

上一节讲了Shamir原始的密钥分享方案,使用m of n 阈值签名,但也存在以下问题:

  1. 密钥分发者知晓完整的密钥,有作恶的可能,例如对部分秘密持有者发放错误的分片数据。
  2. 密钥分片的持有者可能提供非真实的分片数据

当考虑存在不诚实参与方时,对于一个秘密需要有相应的算法来验证其确实是秘密的有效片段,否则不存在秘密可言。 本文将介绍基于Shamir密钥分享的改进机制:可验证的密钥分享(verifiable secret sharing, VSS)。 关于VSS我们直接讲实用的Feldman的VSS方案,尽管在Shamir提出密钥分享(1979)到Feldman的VSS方案提出(1987)也存在一些其他方案设计【注:VSS概念由Benny Chor, Shafi Goldwasser, Silvio Micali等人在1985年首次提出 】。

Feldman方案

实际工程中使用的密钥分享都是有限域上的循环群的运算,采用公共g作为生成元。 为了使得分发的秘密碎片的数据可验证,秘密分发者除了给出秘密的分片数据外,还要提供对应的系数承诺$(c_0,c_1,... )$。

符号约定

设 p 是一个大素数,q 为 p -1 的一个大素数因子,g 属于$Z_p^*$ 且为 q 阶元素,(p, q, g) 是公幵可知的,n 是参与者的数目,s 为要共享的密钥,k 是门限值。

秘密分发阶段

选定多项式: $a(x) = a_0+a_1x+a2x^2+...+a{k-1}x^{k-1} $

a_0代表密钥,计算承诺(commitment):

$c_0=g^{a_0},c_1=g^{a1},...,c{k-1}=g^{a_{k-1}}$

以上运算是在mod p基础上的。 将承诺$c_i$和$s_i$[注:如同上篇是若干选定的点]一同发送给参与者$p_i$. 【具体工程实现中,由于承诺对所以参与者都是一样的,也可先广播承诺给所有参与者,然后单独秘密发送分片,以减少消息传输量】。

其次,当第i个参与者,收到数据碎片v时,作如下验证:

$g^{si}=\prod{j=0}^{k-1}(c_j)^{i^j} mod\ p$

容易验证等式成立。

由于承诺绑定了系数,如果分发者给出承诺不是用多项式方程真实系数,会导致验证失败。

秘密重构阶段

当一个参与者提供他保存的分片数据($c_i$和$s_i$)时,其他参与者会做同样的验证,这样可以保证参与者在恢复阶段的诚实行为。

Feldman的方案的安全性是建立在离散对数问题的困难性基础上的,所以它是条件安全的。

到此,我们提到过多次安全性,下面我看看密码学中的安全性如何定义的?

密码学安全性

以下为引用内容:

评估密码系统安全性主要有三种方法:(1)无条件安全性 这种评价方法考虑的是假定攻击者拥有无限的计算资源,但仍然无法破译该密码系统。 (2)计算安全性 这种方法是指使用目前最好的方法攻破它所需要的计算远远超出攻击者的计算资源水平,则可以定义这个密码体制是安全的。 (3)可证明安全性 这种方法是将密码系统的安全性归结为某个经过深入研究的数学难题(如大整数素因子分解、计算离散对数等),数学难题被证明求解困难。这种评估方法存在的问题是它只说明了这个密码方法的安全性与某个困难问题相关,没有完全证明问题本身的安全性,并给出它们的等价性证明。

对于实际应用中的密码系统而言,由于至少存在一种潜在破解方法,即强力攻击法,因此难以满足无条件安全性,大部分只提供计算安全性。即要满足以下准则: (1)破译该密码系统的实际计算量(包括计算时间或费用)十分巨大,以致于在实际上是无法实现的。 (2)破译该密码系统所需要的计算时间超过被加密信息有用的生命周期。 例如,战争中发起战斗部署和攻击命令,只需要在战斗打响前需要保密; 重要新闻消息在公开报道前需要保密的时间往往也只有几天时间或更短。 (3)破译该密码系统的费用超过被加密信息本身的价值。

如果一个密码系统能够满足以上准则之一,就可以认为是满足实际安全性的。

小结

Feldman的方案提供了可验证的密钥分享机制,验证子密钥的正确性的关键是密钥分发者公布了承诺信息$(c_i)$,$c_i$ 绑定了多项式系数,从而使得每个参与者收到的承诺都来自同一个多项式, $a_0$的秘密就是多项式的秘密!

关于多项式的知识,在零知识证明中有更多的应用,以后再说! 本文主要参考:https://www.cs.umd.edu/~gasarch/TOPICS/secretsharing/feldmanVSS.pdf https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing https://en.wikipedia.org/wiki/Verifiable_secret_sharing

Feldman方案有适用场景,也有一定局限性,下一篇将继续介绍密钥分享中的其他分案!

欢迎关注公众号:blocksight

相关阅读:

区块链中的数学 - Shamir密钥分享 Shamir原始的密钥分享方案

区块链中的数学 - 比特币使用的多签方式 比特币多签和Schnorr聚合签名

区块链中的数学 - 随机数和伪签名 随机数与伪签名构造

区块链中的数学 - EdDSA签名机制 EdDSA的发展及优点

区块链中的数学 - Ed25519签名 Ed25519签名

区块链中的数学-ElGamal算法 ElGamal算法签名及验证&实例演练

区块链中的数学-VRF基于ECC公钥体制的证明验证过程 基于椭圆曲线的VRF证明验证过程

Schorr签名与椭圆曲线 Schorr签名与椭圆曲线

区块链中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析(中)

点赞 0
收藏 2
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。