Secure Multi-Party Computation Against Passive Adversaries
#Shamir秘密分享 2024-06-20

Shamir分享

问题

  1. 什么是Shamir秘密分享？
  2. 怎么进行Shamir秘密分享？
  3. 进行Shamir秘密分享时需要注意什么？
  4. 如何证明Shamir秘密分享的安全性？

什么是Shamir秘密分享？

基本概念

通过构建在有限域上的多项式，对多项式上点的坐标进行分发，实现对常数项的秘密分享

主要特点

相比于GMW，二者在加法操作上相同，但Shamir的乘法操作相比于GMW而言更加高效；同时由于Shamir乘法操作对门限的限制(即 )，该分享主要针对诚实大多数场景

怎么进行Shamir秘密分享？

基本原理

  1. 在二维平面上， 个评估点可以唯一确定一个在有限域上的 次多项式；
  2. 该次多项式不能通过小于 个评估点的已知信息计算得到；

分享方法

  1. 令共有 方进行秘密分享， 方可恢复出秘密分享的值，即 -out-of- 的Shamir秘密分享形式;
  2. 我们将秘密分享的值作为 次多项式的常数项，并在有限域上随机选取其余项的系数（最高次项系数不为0），得到构造出的多项式形式，并将多项式上取到的点分发给 方;

重构方法 — Lagrange多项式插值法

在 上，，

其中

我们可以通过 个评估点，重构得到，其中 是我们进行秘密分享的值

进行Shamir秘密分享时需要注意什么？

  1. 有限域的应用
  2. 次数的选取
  3. 份额的分发

如何证明Shamir秘密分享的安全性？

  1. 完美安全

pending ...

原文链接