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

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

秘密分享(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

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

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