抗合谋的秘密分享协议

堇墨浮华

隐私计算研习社

0
摘要
在密码学时代，组织面临的最大问题之一是保护敏感数据，如用于加密和认证的私钥。区块链中，个人的私钥用于管理其个人资产，因此丢失或被盗可能会造成灾难性后果。目前的解决方案谁通过复杂的硬件存储设备来控制私钥的访问，或者使用多因素认证系统来访问私钥。然而，私钥仍然会被黑客获取，原因很简单：单一故障点。黑客只需渗透一个位置，无论是硬件设备还是网页服务器，就能完全控制个人的私钥。
那么，我们是否接受了这个永恒的真理，即某一天，一些戴着“达利”面具的黑客凭借几行代码就能窃取一切？对这个问题的答案是由姚期智在20世纪80年代给出的，并由Goldreich、Micali和Wigderson 在引入多方计算（MPC）后进行了探讨。
今天的MPC已经成为回答互联网上如何存储私人数据（如私钥）的转折点。
考虑一个分发随机选择的私钥给用户的组织。每次用户登录组织的中央服务器时，系统会查找相应的公钥并验证用户身份，私钥可以存储在服务器或用户的某个硬件设备中，但在这两种情况下，私钥有可能被窃取。
MPC可以在加固对服务器或用户存储设备方面发挥重要作用，在这两种情况下，私钥可以被分割成多个部分，并存储在多个服务器或用户驱动器上。现在，攻击者必须入侵所有存储份额的位置才能获取完整的密钥。每当用户登录时，他必须从所有位置获取自己的份额，并使用MPC安全地重新计算私钥以进行身份验证。
1
MPC核心--秘密分享
秘密分享方案，简而言之是多个不同的参与方，能够在不泄露私钥的情况下，计算对应函数，正如上面的例子所示，用户通过将私钥的份额汇集在一起进行身份验证。将私钥分片成几个部分是多方计算的核心概念之一，而秘密分享的概念实现了这一点，让我们通过一个例子来理解秘密分享方案的概念。
通过以下例子来理解秘密分享方案的概念：想象一下，你在一个洞穴里发现了一个古老的宝库。当你触摸宝库时，一个神谕出现并要求你找到所有100块宝库钥匙的碎片才能获得宝藏。假设你找到了99块钥匙的碎片并试图打开宝库——你仍然失败！除非你找到最后一块钥匙，否则这99块碎片是没有用的。
只有当找到了所有的100块碎片，宝库才可能通过一个魔法咒语打开，而在密码学中，这个魔法咒语是通过秘密分享方案来实现的。
此外，我们并不需要秘密分享方案的所有碎片，因为有些参与方可能会在实际场景中出现异常，例如：一个节点可能丢失或某些参与方的份额可能被损坏。
因此，根据异常的程度，门限秘密分享方案定义了一个阈值。例如，在(3,4)阈值秘密分享方案中，私钥被分布在4个参与方之间，其中任意三个参与方都可以恢复它。而低于阈值的参与方永远无法恢复该秘密。
1. Shamir的秘密分享
Shamir的秘密分享方案是一个经典的t-of-n阈值秘密分享的例子。它利用了在二维平面上的任意t+1个点上，可以生成具有唯一x值的曲线f(x)的理论，详情请参见图1。此外，可以使用任意t个曲线上的点使用“拉格朗日插值”来重构多项式f(x)。

图1. Shamir秘密分享对应的多项式
假设用户想要创建（3, 4）-Shamir的秘密共享，共享的密钥是“Privkey”。首先，他生成一个具有两个系数a1和a2的函数f(x)，并将它们的私钥嵌入函数的常数项中。
f(x) = Privkey + a1* x¹ + a2*x²
现在他生成解析f(x)以获取曲线上的点（x1，y1），（x2，y2），（x3，y3）和（x4，y4）形式的份额。有一天，用户决定重新生成他的私钥。他收集了任意3个份额，将它们插入拉格朗日插值公式中，得到了他的原始函数f(x)。用户知道f(x)的常数项就是秘密。
2. 秘密分享方案中的合谋问题
在实现Shamir的秘密分享方案后，用户认为他可以防御任何黑客的攻击。不幸的是，乌托邦之外的事物并不完美，而且一些黑客总是会找到那些不完美的地方，向我们展示了我们所有努力都是徒劳。
这一次，假设黑客们以某种方式控制了服务器并参与了阈值秘密分享，目标是在用户不知情的情况下重新生成私钥。如果黑客们能够控制超过用户阈值数量的密钥存储服务器，他们可以轻松地重建私钥。
秘密分享方案中的这种特定漏洞，被称为合谋[6]。这些腐败方被称为彼此之间进行秘密通信，以从阈值秘密分享方案中获得最大利益。
为了理解合谋的影响，让我们看看以下涉及腐败方的例子：
2.1 示例：公开投标中的合谋
Westeros的公共福利部门对他们的建筑工作进行了招标，有几家建筑公司参与了投标，招标被以一个更高的市场价格授予了一个众所周知的Westeros公司——兰尼斯特集团。在调查过程中，揭示了兰尼斯特集团和其他五十家参与投标的建筑公司事先决定了结果，并故意提高了价格。作为回报，兰尼斯特集团向竞争对手支付了秘密费用。上述示例展示了兰尼斯特集团和其他五十家建筑公司的合谋，导致招标以不必要的高价提供。
这种情况在Westeros国内很普遍，所以开支部决定提出一些政策来解决这个问题。提出了两个解决方案：
形成一个可信的授权机构：可以组建一个可信的机构作为监管机构，以对抗虚假的价格。只有在可信方批准的情况下，投标才能成功。这个解决方案不会完全将投标结果的控制权交给投标者，而是与外部的可信方共享，可信方充当监管者。

图2. 拍卖师和竞拍者的通信过程
相信拍卖师并隔离竞标者：在这种情况下，拍卖师（如上述示例中的Westeros公益部门）可以限制竞标者之间的通信。任何竞标结果都将由拍卖师（参见图2）亲自向每个竞标者通知。只有在拍卖师不腐败的情况下，这才能成功。
在秘密分享方案中，数学公式无法区分诚实和不诚实的秘密重建，就像Westeros公益部门无法识别由建筑公司之间的勾结造成的价格炒作一样。
2
抵抗合谋的方法
如果一组参与者可以合法重建秘密，那么同一组参与者也可以恶意重建。因此，我们无法保证该协议能够在严格的点对点环境中防止隐藏通信。这意味着需要某个受信任的实体监视此类隐藏通信。该实体可以是参与秘密分享的各方之一，也可以是称为“代理商”的外部实体。
在有受信任实体的情况下，可以避免勾结的两种方法：
通过权限进行访问控制：可以赋予受信任的一方更高的权限/访问权限。思想是即使发生勾结，也不会影响最终结果。
将受信任的一方作为中介人：受信任的一方作为中介人，控制各方之间共享的所有消息。这里的目标是限制各方之间的通信，使它们通过中介人共享有效的消息。
我们进一步详细说明如何利用受信任的权威来建立访问控制和避免勾结。
1. 具有受信任权威的无勾结秘密分享协议
这种用于无勾结秘密分享协议的方法基于通过分层秘密分享方案（HSS）定义的访问结构的实施[1]。在该方案中，除了阈值之外，还为每个共享方分配一个信任因子。不同方拥有不同的信任级别，由它们的等级形成层次结构。只有最高级别的参与者（其中最值得信任的）在场时，才能重新生成秘密。
1.1权威构建
让我们通过以下示例了解如何使用层次结构构建权威和访问结构：
卡吉尔战争结束，协议“Grave”被激活，旨在由国防组织销毁所有战争机密文件。这些文件存放在一个安全的地方，仍然受到严格保护。不仅国防部长一个人无法销毁该文件，协议还必须要求海军总司令、陆军总司令和空战总司令与他们的海军上将、陆军将军和空军元帅一同在场。
2. 在激活《墓穴协议》的那天，至少有10名成员可以提供他们的份额。这些分享的秘密由10名墓穴成员在激活日呈现。请注意，在每个层次上都会执行层级。
3. 只有在满足所有层级规则的情况下，保险库才能打开，即使至少有10名成员在场，秘密代码的再生成也失败了，失败的原因是层级规则没有得到满足。请注意，在协议激活日，国防部长缺席。
以上示例展示了如何利用级别定义访问结构。在上述示例中，受信任的权威——国防部长在重新生成秘密代码方面具有重要利益。即使在没有他参与的情况下进行秘密通信，也没有任何团体成员可以串通起来访问保险库。
1.2 层级秘密分享方案
层级秘密分享方案通过利用Birkhoff插值实现细粒度的访问策略。Birkhoff插值的目标是以份额的形式向更高级别和更低级别的参与者提供有关秘密的更多数据。最终，需要高层次份额的存在来重新生成秘密。
这构建了高级参与者的权威观念。在本节中，我们解释了为什么具有最高级别的参与者份额具有避免串通的权威：
所有参与者通过提供随机系数和随机x值以及保持在f(x)常数项中的秘密生成函数f(x)，为每个参与者生成份额，根据他们的级别。
受信任的参与者份额：对于受信任的参与者，将x值插入f(x)以评估y。他们接收的份额的形式为（x，y）。
对于其他人，根据他们的级别对f(x)进行微分。假设一个参与者的级别为1（受信任的参与者的级别为0），f(x)微分一次，然后将x值插入并从f(x)评估y。
在重新生成过程中，所有份额都被收集，但在没有受信任权威的份额的情况下，协议无法完成。为了理解这一点，让我们假设我们有3个参与者P1、P2、P3，P1是级别为0的受信任参与者，P2和P3的级别为1，阈值为t=2。
参与者生成f(x)如下：
f(x) = secret + a1 * x + a2 * x^2, 令 f(x) = secret + x + 2*x^2
生成的份额如下：
P1的份额：x=23，级别=0，f(x) = secret + 23 + 2 * 23 * 23
P1的份额：x=24，级别=1，f′(x) = 0 + 1 + 2 ∗ 2 ∗ 24
P2的份额：x=25，级别=2，f′’(x) = 0 + 0 + 2 ∗ 25
观察到P1（受信任的参与者）的份额包含一个秘密实体，而不是P3和P2。因此，在没有P1的情况下，不可能重新生成秘密并完成秘密重建。
3
无合谋秘密分享的应用
分布式存储所有者的私钥：如果用户想要以合谋免费秘密分享协议的方式分布式存储他们的私钥，那么他们可以作为具有最高级别的受信任权威。这意味着，没有用户的份额，其他任何一方都无法重新生成私钥。
具有垂直访问结构的授权：层级秘密分享可以在各种垂直组织结构的大型组织中使用。该方案可以确保在组织中授权访问时的公平性。
4
引用
[1]. Tassa, T. Hierarchical Threshold Secret Sharing. J Cryptology 20, 237–264 (2007). https://doi.org/10.1007/s00145-006-0334-8
[2]. Alwen, J., Katz, J., Lindell, Y., Persiano, G., Visconti, I. (2009, August). Collusion-free multi- party computation in the mediated model. In Annual International Cryptology Conference (pp. 524–540).
[3].Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613, https://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf.
[4]. Lindell, Y. (2020). Secure multiparty computation (MPC). Cryptology ePrint Archive, https://eprint.iacr.org/2020/300.
[5]. A beginner’s guide to Secure Multiparty Computation, https://medium.com/@keylesstech/a-beginners-guide-to-secure-multiparty-computation-dc3fb9365458
[6]. Zhang, X., & He, M. (2010, April). Collusion attack resistance and practice-oriented threshold changeable secret sharing schemes. In 2010 24th IEEE International Conference on Advanced Information Networking and Applications (pp. 745–752). IEEE, https://ieeexplore.ieee.org/document/5474795.
[7]. Lecture on Yao’s protocol https://people.eecs.berkeley.edu/~sanjamg/classes/cs294-spring16/scribes/1.pdf
[8]. Lecture on Secret Sharing https://www.cs.purdue.edu/homes/hmaji/teaching/Fall%202020/lectures/08.pdf
本文来源：
https://medium.com/silence-laboratories/collusion-free-protocol-with-an-honest-mediator-in-secret-sharing-scheme-3993dddc7a10
作者：Lucy
翻译：杨赟博
分享仅供学习参考，若有不当，请联系我们处理。

来源：
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！