高效的零知识证明：理论与实践

核心观点与贡献

• 动机：研究秘密分享（SS）、可验证秘密共享（VSS）、Shamir秘密共享（SSS）及可验证的Shamir秘密共享（VSS）。
• 主要贡献：
  • 提出具有可信设置的最佳VSS方案。
  • 设计高效的一对多经销商算法，无需可信设置即可实现近乎最佳的VSS方案。

以前的工作（使用受信任的设置）

• 通过数学方法优化算法，实现高效计算（如FFT和IFFT）。
• 独立提出类似算法的Dankrad Feist和Dmitry Khovratovich。

实验结果

• 验证数学推导的正确性，确保方案有效性。

方案细节

• GKR协议：
  • 活板门电路模型：GKR协议，证明大小为\(O((\log n, \log |G|))\)，验证时间为\(O((\log n, \log |G|))\)。
  • 推广到所有电路，实现高效验证。
• 新的菲亚特-沙米尔启发式非交互式（Hide处女座）：
  • 无活板门设计，实现高效非交互式协议。

总结

• 具有受信任设置的VSS：
  • 时间复杂度：\(O(\log n)\)。
  • DKG构建方案：证明大小和验证时间为\(O(\log n)\)，每个派对时间为\(O(\log n)\)，每方通信交易时间为\(O(1)\)。
• 一对多经销商算法：
  • 时间复杂度：\(O(\log n)\)每方通信。