云中雨雾

    基于秘密共享的安全计算

    2021/05/10 19:15 下午 标签: #密码学理论

    当前有两种主要方案来构造安全计算协议: 一是秘密共享, 二是同态加密. 同态加密要求计算开销很大, 因而需要更长的计算时间, 在大数据和物联网中不适用. 秘密共享方案是密码学领域中用于数据加密的一种方法, 它将单个秘密分成多个秘密份额, 然后将其共享给多个用户. 比较有名的秘密共享方案是Shamir于1979年提出的\((k,n)\)门限秘密共享, 原始秘密只能由至少\(k\)个秘密份额重构, 而任意\(k-1\)个及以下均无法获得原始秘密的任何信息, 因此, 当\(n>k\)时, \((k,n)\)门限秘密共享方案最多可以容忍\(n-k\)个秘密份额丢失.

    SPDZ方案

    Damgård等人提出了一个基于\((k,n)\)门限秘密共享的安全多方计算框架SPDZ, 它使用了Somewhat同态加密(BGV同态加密), 在\(n=k\)的情形下, 可以安全抵抗不诚实大多数的参与方. 在SPDZ中, 数据拥有者也是计算参与方之一, 因此即使\(n-1\)个参与方合谋, 只要秘密拥有者保持秘密份额的安全, 原始秘密就无法从\(n-1\)个秘密份额中重建出来. SPDZ包含两个阶段: 预处理阶段(preprocessing phase)和在线阶段(online phase). 可以通过加法秘密共享来确保秘密的机密性. SPDZ中的秘密加法是容易实现的, 但是秘密乘法则需要基于Beaver在1991年提出的电路随机化(circuit randomization)方案, 即乘法三元组(multiplication triple)来实现. 随机数份额\((\langle a\rangle, \langle b\rangle, \langle c\rangle)\)被称为一个乘法三元组, 如果它满足\(ab=c\). 在SPDZ中, \(x\)的秘密信息是从其份额\(\langle x\rangle\)重构的, 表示为\(x=open(\langle x\rangle)\). SPDZ计算秘密乘法的\(x\cdot y\)的方式如下:

    1. (Offline phase, 离线阶段) 准备乘法三元组\((\langle a\rangle, \langle b\rangle, \langle c\rangle)\);
    2. (Distribution phase, 秘密分发阶段) 计算秘密\(x,y\)的份额\(\langle x\rangle, \langle y\rangle\);
    3. (Online phase, 在线阶段) 每个参与方重构\(d=open(\langle x\rangle-\langle a\rangle), e=open(\langle y\rangle-\langle b\rangle)\), 并计算\(\langle x\cdot y\rangle=d\cdot e+e\cdot\langle a\rangle+d\cdot\langle b\rangle+\langle c\rangle\).

    其原理非常简单:

    \[\begin{aligned} z=xy&=(x-a+a)(y-b+b) \\ &=(x-a)(y-b)+a(y-b)+b(x-a)+ab\\ &=de+ae+bd+c. \end{aligned} \]

    2-out-of-3秘密共享方案

    Araki等人[AFL2016]针对\(n=3,k=2\)的情形给出了进行快速保密计算的一种方案, 该方案是诚实大多数方案, 可以抵抗1个恶意敌手, 且每次乘法只需要进行一次通信. 注意到预处理阶段存在通信, 通常不认为在预处理阶段需要进行通信是一个问题. 此外, 安全计算秘密加法仍然是本地计算的. Araki等人的详细的方案描述如下:

    1. (Preprocessing Phase, 预处理阶段) 参与方\(P_1,P_2,P_3\)生成并持有\(\beta_1,\beta_2,\beta_3\in\mathbb{Z}_{2^\ell}\), 满足\(\beta_1+\beta_2+\beta_3=0\).

    2. (Computation Phase, 计算阶段) 设\(D\)的秘密为\(v_1,v_2\), 记\(i=1\)时, \(a_{i-1}\)表示秘密\(a\)的\(P_3\)的份额, 记\(i=3\)时, \(a_{i+1}\)表示秘密\(a\)的\(P_1\)的份额. (1) 秘密分发

      • 数据拥有者\(D\)选取随机数\(x_1,x_2,x_3\in\mathbb{Z}_{2^n}\), 其中\(x_1+x_2+x_3=0\);

      • \(D\)发送秘密\(v_1\)的份额\((x_i,a_i)\)给参与方\(P_i\), 其中\(a_i=x_{i-1}-v_1(i=1,2,3)\);

      • \(D\)重复上述两步, 发送秘密\(v_2\)的份额\((y_i,b_i)\)给参与方\(P_i\), 其中\(b_i=y_{i-1}-v_2(i=1,2,3), y_1+y_2+y_3=0\).

      (2) 秘密加法(设三方需要秘密计算\(m=v_1+v_2\))

      • 参与方\(P_i\)本地计算\((z_i,c_i)=(x_i+y_i,a_i+b_i)\), 并将\((z_i,c_i)\)作为\(m=v_1+v_2\)的秘密份额.

      (3) 秘密乘法(设三方需要秘密计算\(m=v_1v_2\))

      • 参与方\(P_i\)计算\(r_i=(a_ib_i-x_iy_i+\beta_i)/3\), 并发给\(P_{i+1}\);
      • 参与方\(P_i\)计算\(z_i=r_{i-1}-r_i, c_i=-2r_{i-1}-r_i\), 并将持有的\((z_i,c_i)\)当作\(m=v_1v_2\)的秘密份额.

      (4) 秘密重构

      对于任意两方\(P_i,P_{i-1}\)分别拥有\((z_i,c_i)\)和\((z_{i-1},c_{i-1})\), 通过计算\(m=z_{i-1}-c_i\)可以轻易地重构获得秘密\(m\).

      对于加法而言, 有

      \[ \begin{aligned} z_{i-1}-c_i&=x_{i-1}+y_{i-1}-(a_i+b_i)\\&=(x_{i-1}-a_i)+(y_{i-1}-b_i)\\&=v_1+v_2\\&=m. \end{aligned} \]

      对于乘法而言, 可以证明\(r_1+r_2+r_3=v_1v_2\), 而

      \[\begin{aligned} c_i&=-2r_{i-1}-r_i\\ &=-r_{i-1}-r_{i-1}-r_i-r_{i+1}+r_{i+1}\\ &=(r_{i+1}-r_{i-1})-(r_{i-1}+r_i+r_{i+1})=z_{i-1}-v_1v_2, \end{aligned} \]

      因此\(m=v_1v_2=z_{i-1}-c_i\).

    参考文献

    1. Damgård I., Pastro V., Smart N., Zakarias S. Multiparty computation from somewhat homomorphic encryption. In CRYPTO 2012. LNCS, vol 7417, pp.643-662. Springer, Berlin, Heidelberg.
    2. Damgård I., Keller M., Larraia E., Pastro V., Scholl P., Smart N.P. Practical covertly secure MPC for dishonest majority – Or: Breaking the SPDZ Limits. In ESORICS 2013. LNCS, vol. 8134, pp. 1-18. Springer, Berlin, Heidelberg.
    3. Araki T., Furukawa J., Lindell Y., Nof A., Ohara K. High throughput semi-honest secure three-party computation with an honest majority. In CCS 2016, pp. 805-817. ACM, New York, NY, USA.


    本文标题: 基于秘密共享的安全计算
    本文作者: 云中雨雾
    本文链接: https://weiviming.github.io/16206453366291.html
    本站文章采用 知识共享署名4.0 国际许可协议进行许可
    除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
    最后编辑时间: 2021-05-10T19:15:36+08:00