安全多方计算——秘密共享机制

开始看隐私计算的东西了，感觉很有趣。于是写了一下关于秘密分享的东西。

秘密分享(Secret Sharing):

Shamir阈值秘密分享方案：

该方案基于拉格朗日插值法，支持n个参与方中的任意t个可以联合解开秘密数据。 A的目的是将其秘密数据$a_0$共享给$S_1,S_2,\cdots,S_n$，那么他先生成一个$t-1$次多项式$f(x)=a_0+a_1x+a_2x^2+\cdots+a_{t-1}x^{t-1}$ 接下来A将$f(1),f(2),\cdots,f(n)$分别分发给n个人（相当于把秘密拆分成n份），那么当且仅当$n$个人中任意$t$个将他们所拿到的值放在一起的时候才可以通过拉格朗日插值法解出原多项式，然后将$x=0$代入就可以获得秘密$a_0$

Shamir阈值秘密分享方法应用场景：

很容易发现$Shamir$方法是线性的，所以支持加法同态。具体的应用场景有，某个数据需求方需要用到A, B, C三方秘密之和$a_0+b_0+c_0$ 首先A构造出多项式$f_a(x)=a_0+a_1x+a_2x^2$，并将其秘密拆分为$f_a(1),f_a(2),f_a(3)$ 然后B，C分别构造出多项式$f_b(x),f_c(x)$，并将其秘密拆分为$f_b(1),f_b(2),f_b(3)$和$f_c(1),f_c(2),f_c(3)$ 然后三方分别将自变量为1的函数值发给A，自变量为2的函数值发给B，自变量为3的函数值发给C，于是形势如下图： 各方经过计算之后将结果发给数据需求方，于是可以就得到了$a+b+c$的结果

不经意传输(Oblivious Transfer):

不经意传输指的是数据发送方有n个数据，而数据接收方接受其中一个数据，而且数据接收方不能获取其它数据，数据发送方不能直到接收的数据具体是哪一个。 例如在两个数据中选择一个的方法。 假设P1是发送方，持有$m_1,m_2$，P2是接收方，不妨设P2想要第一个数据

1. P1生成一对公钥和私钥e与d，并生成两个随机数$s_1,s_2$，将公钥与两个随机数都发送给P2。 P1所知：$m1,m2,s1,s2,e,d$ P2所知：$s_1,s_2,e$</p>

2. P2生成一个随机数s并用公钥e将其加密，加上$s_1$之后发送给P1 P1所知：$m1,m2,s1,s2,e,d,Enc(s)+s_1$（不妨设为$s^\star$） P2所知：$s_1,s_2,s,e$

3. P1利用私钥计算$Dec(s^\star-s_1),Dec(s^\star-s_2)$（容易发现其中有一个会变成P2产生的随机数s，但是P1并不知道P2随机的数是什么，不知道P2随机数的位置是哪一个）然后将$m_1,m_2$信息分别异或上这两个值，并发送给P2 P1所知：$m1,m2,s1,s2,e,d,Enc(s)+s_1$

   P2所知：$s1,s2,s,e,Dec(s^\star-s_1)\oplus\ m_1=s \oplus m_1 ,Dec(s^\star-s_2)\oplus m_2=Dec(enc(s)+s_1-s_2)\oplus m_2$

   </li>

4. 于是P2用第一个数（P2想要信息对应的位置）计算$s\oplus m_1\oplus s$就可以获得$m_1$，与此同时P2并不能从第二个数获得或者推断出任何关于$m_2$的信息。

</ol>