Succinct Zero Knowledge for Floating Point Computations
Succinct Zero Knowledge for Floating Point Computations
复制标题
浮点计算的简洁零知识
DOI：
10.1145/3548606.3560653
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Zhang, Yinuo
中科院分区：
文献类型：
--
作者：
Garg, Sanjam;Jain, Abhishek;Jin, Zhengzhong;Zhang, Yinuo
本文研究了浮点计算中构造简洁的零知识证明系统的问题。处理浮点计算的标准方法需要转换为二进制电路，遵循IEEE-754浮点标准。这种方法在w位精度计算的证明器效率中产生了poly（w）开销，导致非常高的证明器运行时间-已经是简洁参数设计中的关键瓶颈。我们作出以下贡献：-我们提出了一个新的模型验证浮点计算，保证近似正确性w.r.t.相对误差界。该模型受数值分析的启发，对机器学习和科学计算等应用具有重要意义。使用这个模型，我们提出了一种通用方法，从现有的公共硬币“提交和证明”系统开始，为浮点计算构建简洁的零知识证明。对于具有w位精度的计算，我们的方法在证明器运行时间中仅产生log（w）开销。我们的编译器几乎保留（高达2倍）的底层协议的通信复杂性，并需要次线性验证时间。由此产生的证明可以在随机预言模型中进行非交互式。具体地说，我们的方案比完全遵循IEEE标准[35]的32位浮点计算方法快约57倍。中央我们的主要结果，和独立的利益，是一个新的批量范围证明系统在标准的素数阶组，不依赖于位分解。
We study the problem of constructing succinct zero knowledge proof systems for floating point computations. The standard approach to handle floating point computations requires conversion to binary circuits, following the IEEE-754 floating point standard. This approach incurs a poly(w) overhead in prover efficiency for computations with w-bit precision, resulting in very high prover runtimes -- already the key bottleneck in the design of succinct arguments. We make the following contributions: -We propose a new model for verifying floating point computations that guarantees approximate correctness w.r.t. a relative error bound. This model is inspired by numerical analysis, and is very meaningful for applications such as machine learning and scientific computing. -Using this model, we present a general method for constructing succinct zero-knowledge proofs for floating point computations starting from existing public-coin "commit-and-prove'' systems. For computations with w-bit precision, our approach incurs only a log(w) overhead in prover running time. Our compiler nearly preserves (up to a factor of 2) the communication complexity of the underlying protocol, and requires sub-linear verification time. The resulting proof can be made non-interactive in the random oracle model. Concretely, our scheme is ~57x faster than the method following IEEE standard exactly [35] for 32-bit floating point computations. Central to our main result, and of independent interest, is a new batch range proof system in standard prime order groups that does not rely on bit decomposition.
登录
查看更多内容
DOI：
10.1145/3460120.3484767
发表时间：
2021-11
期刊：
Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
影响因子：
--
作者：
Jiaheng Zhang;Weijie Wang;Yinuo Zhang;Yupeng Zhang
通讯作者：
Jiaheng Zhang;Weijie Wang;Yinuo Zhang;Yupeng Zhang
IV.21 数值分析
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
L. Trefethen
通讯作者：
L. Trefethen
DOI：
--
发表时间：
2020-10
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Srinath T. V. Setty;Jonathan Lee
通讯作者：
Srinath T. V. Setty;Jonathan Lee
安全计算中 IEEE 算法的成本
DOI：
--
发表时间：
2021
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
David W. Archer;S. Atapoor;N. Smart
通讯作者：
N. Smart