Shamir秘密共享场景下利用FFT加速Berlekamp Welch算法的咨询

在满足$t<n/3$的拜占庭容错条件下，Berlekamp-Welch（BW）算法可对存在最多t个恶意错误的Shamir秘密共享份额完成正确的秘密恢复。传统BW实现的时间复杂度为$O(n^2)$，借助快速傅里叶变换（FFT）及其有限域变体（数论变换NTT）可将核心运算的复杂度降至$O(n \log n)$量级，具体优化逻辑如下：

可通过FFT加速的核心运算环节 #

BW算法的核心是求解两个满足约束$Q(x_i) = y_i E(x_i)$的多项式：次数不超过t的错误多项式E(x)（错误份额对应的x坐标为其根），以及次数不超过$k-1+t$的乘积多项式Q(x)（满足$Q(x)=F(x)E(x)$，$F(x)$为原始秘密多项式）。其中三类核心运算都可以通过FFT大幅提速：

• 多项式乘法运算
  传统实现中两个次数为d的多项式相乘复杂度为$O(d^2)$，如果Shamir秘密共享的求值点选择为FFT友好的单位根点（有限域场景下对应本原单位根，适用NTT计算），那么多项式相乘可以通过「FFT转点值-点值相乘-逆FFT转系数」的流程在$O(d \log d)$时间内完成。BW流程中多项式乘积验证、除法前置计算等环节都可以复用该能力。
• 多点求值运算
  BW求解过程中需要多次验证多项式在所有n个份额点上的取值是否满足约束，传统逐点求值复杂度为$O(n^2)$。基于FFT的快速多点求值算法通过递归分组结合FFT计算，可以将该过程复杂度降至$O(n \log^2 n)$，在n规模超过1000时提升尤为明显。
• 多项式插值运算
  求解得到Q(x)和E(x)后，需要通过$F(x) = Q(x)/E(x)$得到原始秘密多项式，或对筛选后的合法份额做插值恢复秘密。传统拉格朗日插值复杂度为$O(n^2)$，基于FFT的快速插值算法可将该过程复杂度同样降至$O(n \log^2 n)$。

落地注意事项 #

仅当秘密共享的求值点选择为有限域本原单位根时，才能直接用NTT实现最优加速，普通求值点的快速多点求值/插值复杂度会略有上升，但仍远优于传统$O(n^2)$实现。

• 如果使用的是不支持本原单位根的有限域，可以仅将FFT/NTT用于多项式乘法环节，也能获得可观的效率提升。
• 小规模场景下（n<100）FFT的常数开销可能超过复杂度收益，此时传统BW实现反而更高效。

内容的提问来源于stack exchange，提问作者Ordinary