区块链共识中的秘密共享-隐私计算和榫卯结构
一、引言
2018年5月正式生效的GDPR是欧盟“史上最严”条例,是数十年来数据安全和数据隐私法规方面最重要的一次变化。随后,2019年生效的加州CCPA,对个人数据及信息保护提出了严格的界定和保护要求。至此,GDPR和CCPA对欧美国家在数据安全和隐私行业的立法产生了持续的影响。在我国,2021年6月10日,*第十三届全国人民代表大会常务委员会第二十九次会议正式表决通过了《*数据安全法》。历经三次审议和修改通过的《数据安全法》将于2021年9月1日正式施行。在数据安全和隐私保护方面,企业合规性是一个迫在眉睫的事情。
随着对数据安全和隐私保护的重视和相关法案的出台,各种数据拥有者重新回到数据孤岛的状态。为了实现数据的可用不可见技术并使得互联网公司在合规下能利用大数据和AI技术做更多有意义的事情。在这个背景下,相应的互联网公司提出了一系列的解决方案,如:谷歌的联邦学习、腾讯微众的联邦学习、阿里的共享学习。其中,腾讯微众的联邦学习主要采用了同态加密。谷歌的联邦学习和阿里的共享学习则使用了秘密共享技术,这反映了对秘密共享的算法研究有着重要的意义。
纵观区块链的发展脉络,其经历了初始的1.0阶段,发展成熟的2.0阶段,即将进入新的发展阶段。其吞吐率和挖矿资源浪费问题一是阻碍区块链发展的瓶颈。如何突破这一瓶颈,去中心化的区块链共识算法的突破是核心。运用秘密共享技术的应用去探索去中心化区块链共识算法的突破有很实际的意义。
本文通过对秘密共享技术的介绍和思考,进一步探讨秘密共享的根源以及秘密共享在数据安全和区块链共识等领域的应用。
二、秘密共享
秘密共享(Secret Sharing,SS)是1979年由Shamir和Blakey提出的,并在此之后40多年秘密共享被广泛认识和深入的研究。
秘密共享著名的(t,n)阈值方案如图1所示:设秘密s被分成n个部分,每一部分被称为一个子秘密并由一个持有者持有,并且大于等于t个参与者所持有的子秘密可以重构(Reconstruction)秘密s,而少于t个参与者所持有的子秘密无法重构秘密并且无法获得秘密s的任何信息。
图1秘密分享的结构
秘密共享方案的三种实现技术:
- 基于超平面几何的秘密共享,包括Blakley方案和Brickell方案;
- 基于插值多项式的秘密共享,包括经典的Shamir阈值秘密共享方案;
- Mignotte,Asmuth & Bloom提出的基于中国剩余定理的秘密共享;
基于中国剩余定理的秘密共享是在环上的运算,而Blakley & Brickell的超平面几何秘密共享方案和Shamir阈值秘密共享方案是在有限域上的运算,所以基于中国剩余定理的秘密共享和其他两个秘密共享的理论基础不尽一样。鉴于此,本文暂未讨论中国剩余定理。以下内容主要探讨前两者技术,通过分析方案的结构对两者的关系进行了统一,总结了Shamir秘密共享的优点。
2.1Blakley和Brickell的超平面几何方案
Blakley通过多维欧几里得空间来构造阈值秘密共享机制。任何t非平行t-1维超几何平面在一个t维空间中交易一点。秘密通过编码在坐标中完成秘密共享。如图3所示的三维欧几里得空间中的三个平面交与一点,秘密可以嵌入到交点的某一个坐标中。Blakley方案的秘密分发和秘密重构过程如下:
秘密分发:构造n个t维空间中的t-1维超几何平面分发给n个参与者,其中n>=t;图2是一个3维空间中的2维平面生成,一个秘密拥有者Dealer通过空间中的一个已知点P(秘密s是P的一个坐标值)的条件下生成任意多个过该点的平面。
图2 秘密分发的2维超几何平面
秘密重构:n个参与者中的t个参与者可以重构秘密s。如图3:任意3个参与者即可实现对共享点(包含秘密s)的重构,即三个非平行平面的交点。
图3 三维欧几里得空间中的秘密重构
在秘密共享方案中,信息率是度量秘密共享方案安全性和效率的一个重要指标。所谓秘密共享的信息率可以简单理解为秘密的信息规模与每个子秘密的信息规模的比率。Brickell的向量方法(矢量方法)相比于Blakley超平面几何的方法能够有效提高信息率。
Brickell的秘密共享方案采用向量方法,一个秘密拥有者Dealer把秘密s嵌入到一个向量中,在通过一个矩阵把秘密共享为n个子秘密分发给n个参与者,具体方法如下:
选择秘密s,和随机向量(y2,y3,…… ,yt), 生成一个n*t矩阵M,M有n行,每行记为Mi,任意t个行向量都是线性无关的。秘密份额为(s1,s2,……,sn).每个份额是行向量Mi和列向量(s,y2,y3,…… ,yt),的乘积。即si = Mi* (s,y2,y3,…… ,yt)
其中M式一个公开参数任何一个参与者的子秘密维si,任意t个参与者对应矩阵M的t个行向量,这t个向量组成一个t*t的方阵,根据前面的要求任意t个行向量线性无关所以此方阵满秩,所以可以有效的求解到(ω1,ω2,……,ωt)使得:
也就是任意t个M矩阵的行向量可以张成(1,0,……,0)然后通过如下计算可以重构s。
2,2Shamir的阈值秘密共享方案
Shamir秘密共享是目前应用最为广泛的阈值秘密共享技术。Shamir秘密共享优点有哪些,它与Blakly & Brickell秘密共享的关系又是如何呢?
Shamir的方案的秘密分发和秘密重构过程如下:
秘密分发:
一个Dealer要共享一个秘密s,分给n个参与者,其中任意t个参与者可以重构秘密s,寻找一个t-1次多项式,
其中a0=s,Dealer为每一个参与者任意选择非0的xi计算si=f(xi),把si作为子秘密发送给参与者i.
秘密重构:
任何大于等于t个参与者通过其子秘密si和xi通过拉格朗日插值定理可以恢复上面多项式f(x),并且令x=0实现秘密s的重构。
进一步对shamir秘密分享过程进行分析,可以发现在秘密分享阶段的计算:
把以上的多项式用线性方程组的视角打开来看,是一个范德蒙德矩阵。和一个列向量(a0,a1……,at-1)乘积。其中范德蒙德矩阵和Brickell方案中的矩阵M是对应的。
因此,Shamir秘密共享是Blakley& Brickell方案中的特例。正因为范德蒙德矩阵的特殊性,线性无关性(xi不相等的任意t阶方阵都是满秩的)和构造简单(并且分布式节点很容易统一这个矩阵),所以大多数方案应用Shamir秘密共享。如果需要把Shamir秘密秘密共享应用到一般模式可以考虑把范德蒙德矩阵用一般矩阵替代。
三、可验证的秘密共享
3.1可验证秘密共享
在秘密共享中,为了解决参与者想验证Dealer是否欺骗自己以及Dealer如何证明自己没有欺骗参与者的问题,提出了可验证的秘密共享(VerifiableSecret Sharing,VSS)。FeldmanVSS 是一种基于Shamir秘密共享构造的可验证秘密共享方案。
Dealer要共享一个秘密s,分给n个参与者,其中任意t个参与者可以重构秘密s,寻找一个t-1次多项式,
其中a0=s,Dearler为每一个参与者任意选择非0的xi计算si=f(xi)为i的子秘密发送给参与者i.同时,Dealer计算Aj=gaj,其中j=0,1,2……,t-1并公开这些参数。
参与者收到秘密si后验证si的有效性,即通过验证以下等式是否成立:
其中Aj=gaj .
3.2分布式可验证秘密共享
在以上所有的方案中Dealer是一个知道秘密的实体。Joint Feldman VSS.方案既能实现上述的可验证的秘密共享又能去掉Dealer。一种无可信第三方的可验证秘密共享方案(Distributed Verifiable Secret Sharing,DVSS)
具体过程如下:
- 每一个参与者Pi选择要共享的秘密si=a0并随机选择其他参数生成t-1次多项式:
公开参数Aik并公布,对每一参与者Pj生成秘密si的子秘密sij=fi(xj),将sij发送给参与者Pj.
- 每一个参与者可以验证其他参与者发送给自己的秘密是否有效,并把所有验证通过的参与者记为集合Q;
- 所有参与者把秘密分享验证通过集合Q内的子秘密进行加运算就得到该参与者的子秘密si.
四、在区块链共识和隐私保护中的应用
被称为革命性的第三代加密货币的Cardano(ADA)的共识算法Ouroboros和致力于利用区块链打造一款具备无限扩容能力的自治分布式云计算网络项目Dfinity中的共识算法都不约而同的选择了分布式可验证的秘密共享技术。在信任环境、分布式结构上,区块链的共识节点和分布式可验证秘密的参与者都恰分的对应。这样分布式可验证秘密共享的特征在区块链共识中得到充分的展现,能恰到好处的解决区块链共识算法的吞吐率和资源浪费的问题。
在日趋严格的隐私保护政策下,各种隐私保护算法被提出,其中联邦学习和共享学习最为突出,其内部的安全层都有采用了秘密共享技术实现隐私保护的技术方案。在联邦学习中,基于秘密共享的逻辑回归模型中利用了秘密共享的加法同态性,数据拥有者将秘密共享给多方,在秘密共享的场景下,将明文的计算转换为子秘密的计算,实现了隐私保护。蚂蚁金服的共享学习框架中也采用秘密共享技术作为隐私保护实现的技术之一。
五、总结
本文简要地描述了秘密共享在区块链共识和联邦学习等方面的应用,重点介绍了Blakley和Brickell的超平面几何方案、Shamir秘密共享、可验证的秘密共享和分布式可验证的秘密共享算法。另外,通过应用场景的改变进一步分析了可验证秘密共享和分布式可验证秘密共享。通过对这些秘密共享的深入分析,能够更好地理解其在区块链共识和联邦学习、共享学习的应用。
参考文献
1. Beimel, A., Secure Schemes for SecretSharing and Key Distribution. phd thesis israel institute of technologytechnion, 1996.
2. Ito, M., et al., Secret sharing schemerealizing general access structure. Electronics and Communications in Japan(Part III Fundamental Electronic Science), 1989. 72(9): p. 56-64.
3. Shamir, A., how to share a secret. 1979.
4. Blakley, G.R. Safeguarding cryptographickeys (PDF). in 1979 International Workshop on Managing Requirements Knowledge.1979.
往期回顾(与该文章相关的往期公众号文章)
《数据安全法》9月1日施行,企业如何进行数据安全建设?
内容编辑:创新中心 吕亮 责任编辑:王星凯
本公众号原创文章仅代表作者观点,不代表绿盟科技立场。所有原创内容版权均属绿盟科技研究通讯。未经授权,严禁任何媒体以及微信公众号复制、转载、摘编或以其他方式使用,转载须注明来自绿盟科技研究通讯并附上本文链接。
关于我们
绿盟科技研究通讯由绿盟科技创新中心负责运营,绿盟科技创新中心是绿盟科技的前沿技术研究部门。包括云安全实验室、安全大数据分析实验室和物联网安全实验室。团队成员由来自清华、北大、哈工大、中科院、北邮等多所重点院校的博士和硕士组成。
绿盟科技创新中心作为“中关村科技园区海淀园博士后工作站分站”的重要培养单位之一,与清华大学进行博士后联合培养,科研成果已涵盖各类国家课题项目、国家专利、国家标准、高水平学术论文、出版专业书籍等。
我们持续探索信息安全领域的前沿学术方向,从实践出发,结合公司资源和先进技术,实现概念级的原型系统,进而交付产品线孵化产品并创造巨大的经济价值。
推荐阅读
-
区块链共识中的秘密共享-隐私计算和榫卯结构
-
反传销网8月30日发布:视频区块链里的骗子,币里的韭菜,杜子建骂人了!金融大V周召说区块链!——“一小帮骗子玩一大帮小白,被割韭菜,小白还轮流被割,割的就是你!” 什么区块链,统统是骗子 作者:周召(知乎金融领域大V,毕业于上海财经大学,目前任职上海某股权投资基金合伙人) 有人问我,区块链现在这么火,到底是不是骗局? 我的回答是: 是骗局。而且我并不是说数字货币是骗局,而是说所有搞区块链的都是骗局。 -01- 区块链是一种鸡肋技术 人类社会任何技术的发明应用,本质都是为了提高社会的生产效率。而所谓区块链技术本质不过是几种早已成熟的技术的大杂烩,冗余且十分低效,除了提高了洗钱和诈骗的效率以外,对人类社会的进步毫无贡献。 真正意义上的区块链得包含三个要素:分布式系统(包括记账和存储),无法篡改的数据结构,以及共识算法,三者互为基础和因果,就像三体世界一样。看上去挺让人不明觉厉的,而经过几年的瞎折腾,稍微懂点区块链的碰了几次壁后都已经渐渐明白区块链其实并没有什么卵用,区块链技术已经名存实亡,沦为了营销工具和传销组织的画皮。 因为符合上述定义的、以比特币为代表的原教旨区块链技术,是反效率的,从经济学角度来说,不但不是一种帕累托改进,甚至还可以说是一种帕累托倒退。 原教旨区块链技术的效率十分低下,因为要遍历所有节点,只能做非常轻量级的数据应用,一旦涉及到大量的数据传输与更新,区块链就瞎了。 一方面整条链交易速度会极慢,另一方面数据库容量极速膨胀,考虑到人手一份的存储机制,区块链其实是对存储资源和能源的一种极大的浪费。 这里还没有加上为了取得所谓的共识和挖矿消耗的巨大的能源,如果说区块链技术是屎,那么这波区块链投机浪潮可谓人类历史上最大规模的搅屎运动。 区块链也验证不了任何东西。 所谓的智能合约,即不智能,也非合约。我看有人还说,如果有了智能合约,就可以跟老板签一份放区块链上,如果明年销售业绩提升30%,就加薪10%,由于区块链不能篡改,不能抵赖,所以老板必须得执行,说得有板有眼,不懂行的愣一看,好像还真是那么回事。 但仔细一想,问题就来了。首先,在区块链上如何证明你真的达到了30%业绩提升?即便真的达到老板耍赖如何执行? 也就是说,如果区块链真这么厉害,要法院和仲裁干什么。 人类社会真正的符合成本效益原则的是代理制度。之前有人说要用区块链改造注册会计师行业,我不知道他准备怎么设计,我猜想他思路大概是这样的,首先肯定搞去中心化,让所有会计师到链上来,然后一个新人要成为注册会计师就要所有会计师同意并记录在链上。 那我就请问了,我每天上班累死累活,为什么还要花时间去验证一个跟我无关的的人的专业能力?最优做法当然是组织一个委员会,让专门的人来负责,这不就是现在注册会师协会干的事儿吗?区块链的逻辑相当于什么事情都要拿出来公投,这个绝对是扯淡的。 当然这么说都有点抬举区块链了,区块链技术本身根本没有判断是非能力,如果这么高级的人工智能,靠一个无脑分布式记账就能实现的话,我们早就进入共产主义社会了。 虽然EOS等数字货币采用了超级节点,通过再中心化的方式提高效率,有点行业协会的意思,是对区块链原教旨主义的一种修正,但是依然无法突破区块链技术最本质的局限性。有人说,私有链和联盟链是区块链技术的未来,也是扯淡,因为区块链技术没有未来。如果有,说明他是包装成区块链的伪区块链技术。 区块链所涉及的所有底层技术,不管是分布式数据库技术,加密技术,还是点对点传输技术等,基本都是早已存在没什么秘密可言的技术。 比特币系统最重要的特性是封闭性和自洽性,他验证不了任何系统自身以外产生的信息的真实性。 所谓系统自身产生的信息,就是数据库数据的变动信息,有价值的基本上有且只有交易信息。所以说比特币最初不过是中本聪一种炫技的产物,来证明自己对几种技术的掌握,你看我多牛逼,设计出了一个像三体一样的系统。因此,数字货币很有可能是区块链从始至终唯一的杀手应用。 比特币和区块链概念从诞生到今天已经快10年了,很多人说区块链技术在爆发的前夜,但这个前夜好像是不是有点过长了啊朋友,跟三体里的长夜有一拼啊。都说区块链技术像是90年代初的互联网,可是90年代初的互联网在十年发展后,已经出现了一大批伟大的公司,阿里巴巴在99年都成立了,区块链怎么除了币还是币呢? 正规的数字货币未来发展的形式无外乎几种,要么就是论坛币形式,或者类似股票的权益凭证等。问题是论坛币和股票之前,本来也都电子化了,区块链来了到底改变了什么呢? 所有想把TOKEN和应用场景结合起来的人最后都很痛苦,最后他们会发现区块链技术就是脱裤子放屁,自己辛苦搞半天,干嘛不自己作为中心关心门来收钱?最后这些人都产生了价值的虚无感,最终精神崩溃,只能发币疯狂收割韭菜,一边嘴里还说着我是个好人之类的奇怪的话。 因此,之前币圈链圈还泾渭分明,互相瞧不起,但这两年链圈逐渐坐不住了,想着是不是趁着泡沫没彻底破灭之前赶快收割一波,不然可能什么都捞不着了。 前段时间和一个名校毕业的链圈朋友瞎聊天,他说他们“致力于用区块链技术解决数字版权保护问题”,我就问他一个问题,你们如何保证你链的版权所有权声明是真实的,万一盗版者抢先一步把数据放在链上怎么办。他说他们的解决方案是连入国家数字版权保护中心的数据库进行验证…… 所以说区块链技术就是个鸡肋,研究到最后都会落入效率与真实性的黑洞,很多人一头扎进链圈后才发现,真正意义上的区块链技术,其实什么都干不了。 -02- 不是蠢就是坏的区块链媒体 空气币和区块链的造富神话,让区块链自媒体也开始迎风乱扭。一群群根本不知道区块链为何物的妖魔鬼怪纷纷进驻区块链自媒体战场,开始大放厥词胡编乱造。 任何东西,但凡只要和区块,链,分,分布式,记账,加密,验证,可追溯等等这些个关键词沾到哪怕一点点,这些所谓的区块链媒体人就会像狗闻到了屎了一样疯狂地把区块链概念往上套。 这让我想起曾经一度也是热闹非凡的物联网,我曾经去看过江苏一家号称要改变世界的“物联网”企业,过去一看是生产路由器的,我黑人问号脸,对方解释说没有路由器万物怎么互联,我觉得他说得好有道理,竟无言以对。 好,下面让我们进入奇葩共赏析时间,来看看区城链媒体经常有哪些危言耸听的奇谈怪论 区块链(分布式记账)的典型应用是*?? 正如前面所说,真正意义上的区块链分布式记账,不光包括“记”这个动作,还包括分布式存储和共识机制等。而*诞生远远早于区块链这个词的出现,勉强算是“分布式编辑”吧,就被很多区块链媒体拿来强行充当区块链技术应用的典范。 其实事实恰恰相反,*恰恰是去中心化失败的典范,现在如果没有精英和专业人士的编辑和维护,*早就没法看了。 区块链会促进社会分工?? 罗振宇好像就说过类似的话,虽然罗振宇说过很多没有逻辑的话,但这句话绝对是最没逻辑思维的。很多区块链自媒体也常常用这句话来忽悠老百姓,说分工代表效率提高社会进步,而区块链“无疑”会促进分工,他们的理由仅仅是分工和分布式记账都共用一个“分”字,就强行把他们扯到一起。 实际情况恰恰相反,区块链是逆分工的,区块链精神是号召所有人积极地参与到他不擅长也不想掺合的事情里面去。 区块链不能像上帝一样许诺他的子民死后上天国,只能给他们许诺你们是六度人脉中的第一级,我可以赚后面五级人的钱,你处于金字塔的顶端。