12306的网站建设,吴桥网站建设价格,微博推广的方法,企业建网站作用一、Shamir秘密共享
Shamir秘密共享方案是一种将秘密拆分成多份并分配给多个参与者保存#xff0c;只有在满足特定条件下才能恢复原始秘密的密码学方案。它具有良好的容错性、加法同态性和无条件安全性等特点。
具体地#xff0c;Shamir秘密共享方案可以概括为以下步骤只有在满足特定条件下才能恢复原始秘密的密码学方案。它具有良好的容错性、加法同态性和无条件安全性等特点。
具体地Shamir秘密共享方案可以概括为以下步骤 首先选择一个大质数 p p p且 s p sp sp并选择一个随机数 a 0 a_0 a0并生成 n − 1 n-1 n−1个不同的随机数 a 1 , a 2 , ⋯ , a t − 1 a_1,a_2,\cdots,a_{t-1} a1,a2,⋯,at−1。这些数可用于定义一个 t − 1 t-1 t−1阶多项式 f ( x ) a 0 a 1 x a 2 x 2 ⋯ a t − 1 x t − 1 f(x) a_0 a_1x a_2x^2 \cdots a_{t-1}x^{t-1} f(x)a0a1xa2x2⋯at−1xt−1。多项式中除了 a 0 a_0 a0以外的系数都是随机生成的。 然后将需要共享的秘密 s s s作为多项式中的常量项即 f ( 0 ) s f(0)s f(0)s并计算出 f ( 1 ) , f ( 2 ) , . . . , f ( n − 1 ) f(1),f(2),...,f(n-1) f(1),f(2),...,f(n−1)。每个参与者 i i i将会收到一个秘密分片 ( i , f ( i ) ) (i, f(i)) (i,f(i))其中 i i i是参与者的编号。 如果我们至少获得了 t t t个秘密分片我们就可以使用拉格朗日插值公式重建出原始秘密 s s s。具体地可以使用以下公式 s ∑ j 1 t f ( j ) ∏ i ≠ j , i 1 t k − i j − i s \sum\limits_{j1}^t f(j)\prod\limits_{i\neq j,\; i1}^t \frac{k-i}{j-i} sj1∑tf(j)ij,i1∏tj−ik−i 其中 k k k是需要重建秘密的参与者数。
下面以一个简单的例子来说明Shamir秘密共享方案的应用。假设Alice和Bob想要合作保管一个密码他们希望确保只有在两者都同意时才能访问该密码。为了实现这一目标他们使用Shamir秘密共享方案进行分割。
首先他们共同决定一个秘密值并将其分解成两个部分 s 1 s_1 s1和 s 2 s_2 s2。然后他们随机生成两个随机数 a 0 a_0 a0和 a 1 a_1 a1并计算出一个 t − 1 t-1 t−1阶多项式 f ( x ) a 0 a 1 x f(x) a_0 a_1x f(x)a0a1x。通过将 x 1 x1 x1和 x 2 x2 x2代入多项式他们分别获得了 ( 1 , f ( 1 ) ) ( 1 , s 1 a 0 a 1 ) (1, f(1))(1, s_1a_0a_1) (1,f(1))(1,s1a0a1)和 ( 2 , f ( 2 ) ) ( 2 , s 2 2 a 0 4 a 1 ) (2, f(2))(2, s_22a_04a_1) (2,f(2))(2,s22a04a1)两个秘密分片。
现在如果他们想要检索这个密码只有当他们两个人共同持有各自的秘密分片时他们才能还原出原始的秘密值。因为他们两个人各有一个秘密分片只需要使用拉格朗日插值公式即可还原出原始的秘密值 s ( 2 − 1 ) ( s 2 2 a 0 4 a 1 ) ( 1 − 2 ) ( s 1 a 0 a 1 ) ( 1 − 2 ) s 1 s 2 s \frac{(2-1)(s_22a_04a_1) (1-2)(s_1a_0a_1)}{(1-2)} s_1s_2 s(1−2)(2−1)(s22a04a1)(1−2)(s1a0a1)s1s2
从这个例子中可以看出Shamir秘密共享方案是一种实用而高效的方法可以帮助多个参与者在保护隐私的前提下对敏感信息进行安全的共享和计算。它的容错性能力很好可以适应各种网络条件和故障情况并且具有无条件安全性。 二、GMW方案
GMW和BGW方案是两种秘密共享的基本方案它们都可以用来将一个秘密拆分成多份并分配给多个参与者保存。它们的主要区别在于使用的加密算法不同。
GMW方案也被称为Shamir秘密共享的扩展方案它使用了广泛的家族算法来进行私钥共享具有高效的性质和通用的安全证明。
GMW方案的核心思想是将秘密拆分成多份并分配给多个参与者。每个参与者在本地留存一个秘密分片并使用插值算法将它们组合起来还原出秘密。此外为了保护参与者之间的数据隐私在这个过程中应用了RSA算法或其他家族算法来加密每个参与者的秘密分片使得单个参与者无法获得其他任何参与者手上的信息。
例如假设Alice、Bob和Charlie希望合作保管一个密钥他们使用Shamir秘密共享方案进行分割。首先他们共同决定一个秘密值并将其分解成三个部分 s 1 , s 2 , s 3 s_1, s_2, s_3 s1,s2,s3然后将这些部分秘密地分配给他们三个人。
Alice收到 s 1 s_1 s1、Bob收到 s 2 s_2 s2和Charlie收到 s 3 s_3 s3。现在当Alice、Bob和Charlie需要通过组合他们的密钥部分生成原始密钥时他们使用秘密共享方案中的插值算法并确保每个步骤都进行加密来防止信息泄露。 GMW方案的核心思想是将秘密拆分成与者持有一个秘密分片然后使用插值算法重新聚合这些分片得到原始秘密。
具体来说假设我们有一个秘密 s s s需要共享给 t t t个参与者其中至少需要 k k k个参与者才能重建秘密。对于每个参与者 i 1 , 2 , . . . , t i 1,2,...,t i1,2,...,t首先选择一个随机数 a i a_i ai并计算出一个函数 f ( x ) s ∑ i 1 t a i x i f(x) s \sum\limits_{i1}^ta_ix^i f(x)si1∑taixi。每个参与者 i i i都会获得一对(x, y)其中x为随机数y为 x x x代入 f ( x ) f(x) f(x)得到的结果。因此每个参与者 i i i都可独立存储自己的秘密分片 ( x i , y i ) (x_i, y_i) (xi,yi)。
接下来为了重建原始秘密参与者之间需要交换信息以恢复出秘密值。具体来说每个参与者都需要将自己的秘密分片发送给其他参与者。一旦所有参与者收到了足够数量的秘密分片他们可以通过多项式插值算法计算出完整的多项式并从中恢复出秘密值 s s s。根据Lagrange插值定理可以使用以下公式计算多项式 f ( x ) ∑ i 1 t y i ∏ j ≠ i x − x j x i − x j f(x) \sum\limits_{i1}^t y_i\prod_{j\neq i}\frac{x-x_j}{x_i - x_j} f(x)i1∑tyiji∏xi−xjx−xj 三、BGW方案
BGW是Ben-Or、Goldwasser和Wigderson的缩写。这种方法也被称为 t,N \text{t,N} t,N阈值方案其中 t t t表示阈值 N N N表示总共有多少个参与者。它是基于交互式协议的一个秘密分享方案利用了Shamir秘密共享方案、ElGamal加密和Garbled电路的特性通过多次通信构建应用程序或协议。该方案将所有秘密操作编码成部分执行和计算以保护隐私。
假设Alice、Bob和Charlie想要合作测试一个密钥他们希望使用BGW方案。他们开始时决定了如何将密钥拆分成子密钥。然后他们采取随机的ElGamal加密和解密协议按照预定的顺序对拆分的密钥段加密并将加密日志Garbled circuit logs发送回服务器。
对于密码学应用BGW对于安全计算具有显著的贡献。例如在联合梯度下降Federated Gradient Descent中参与者之间可以使用BGW方案共享计算梯度的秘密值而无需暴露原始数据从而实现了严格的隐私保护。 BGW方案基于阈值密码学也称为(t, n)阈值方案其中t表示需要恢复原始秘密的最小参与者数n表示总参与者数。
假设我们要将秘密 s s s拆分成 n n n份并将其中 t t t份重新聚合以求得原始秘密 s s s。BGW方案采用了同态加密和Garbled电路的方法来实现对保护隐私敏感计算任务的支持。
首先每个参与者都执行一组ElGamal加密 E G k ( x ) EG_k(x) EGk(x)其中 k k k是公钥 x x x是原始秘密/Plaintext。然后他们交换密文并在解密前将密文混合起来Shuffle。接下来他们执行类似于Garbled电路的解密过程Yao’s Garbled Circuits以及其特有的部分执行方案。具体来说他们会构造每个门关系的相应表其中包括外部输入变量、中间值变量和输出临时变量。接着他们通过网络发送这些表给下一个参与者接收方将使用ElGamal解密的方法来解密这些表并进行下一作。最后当所有密文混合、加密和半执行semi-computation完成后可以得到原始秘密的分量。
BGW方案的阈值门可以用以下公式表示 E ( 0 , r ) ^ ∏ i 1 t E i ( 0 , r ) \widehat{E(0, r)} \prod\limits_{i1}^t E_i(0, r) E(0,r) i1∏tEi(0,r)
其中 E ( 0 , r ) E(0, r) E(0,r)是加密一个明文0用随机数 r r r成为其伪随机性的密文 E i ( 0 , r ) E_i(0, r) Ei(0,r)是第 i i i个秘密共享方案中的密文。
总之GMW和BGW都是常见的机密分享方案。其核心思想是将保密数据拆分成若干片段然后分发给不同的参与者。这样每个参与者都持有一部分信息只有在集齐足够数量的信息时才能还原出完整的秘密。GMW使用插值算法而BGW使用ElGamal随机加密和Garbled电路等技术来实现秘密共享和计算任务。 学习导航http://xqnav.top
