Paper 2022/1007

zkQMC: Zero-Knowledge Proofs For (Some) Probabilistic Computations Using Quasi-Randomness

Zachary DeStefano, Los Alamos National Laboratory
Dani Barrack, Los Alamos National Laboratory
Michael Dixon, Los Alamos National Laboratory
Abstract

We initiate research into efficiently embedding probabilistic computations in probabilistic proofs by introducing techniques for capturing Monte Carlo methods and Las Vegas algorithms in zero knowledge and exploring several potential applications of these techniques. We design and demonstrate a technique for proving the integrity of certain randomized computations, such as uncertainty quantification methods, in non-interactive zero knowledge (NIZK) by replacing conventional randomness with low-discrepancy sequences. This technique, known as the Quasi-Monte Carlo (QMC) method, functions as a form of weak algorithmic derandomization to efficiently produce adversarial-resistant worst-case uncertainty bounds for the results of Monte Carlo simulations. The adversarial resistance provided by this approach allows the integrity of results to be verifiable both in interactive and non-interactive zero knowledge without the need for additional statistical or cryptographic assumptions. To test these techniques, we design a custom domain specific language and implement an associated compiler toolchain that builds zkSNARK gadgets for expressing QMC methods. We demonstrate the power of this technique by using this framework to benchmark zkSNARKs for various examples in statistics and physics. Using $N$ samples, our framework produces zkSNARKs for numerical integration problems of dimension $d$ with $O\left(\frac{(\log N)^d}{N}\right)$ worst-case error bounds. Additionally, we prove a new result using discrepancy theory to efficiently and soundly estimate the output of computations with uncertain data with an $O\left(d\frac{\log N}{\sqrt[d]{N}}\right)$ worst-case error bound. Finally, we show how this work can be applied more generally to allow zero-knowledge proofs to capture a subset of decision problems in $\mathsf{BPP}$, $\mathsf{RP}$, and $\mathsf{ZPP}$.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
Zero Knowledge Probabilistic Proofs NIZK Monte Carlo
Contact author(s)
zdestefano @ lanl gov
dbarrack @ lanl gov
mdixon @ lanl gov
History
2022-08-07: approved
2022-08-05: received
See all versions
Short URL
https://ia.cr/2022/1007
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1007,
      author = {Zachary DeStefano and Dani Barrack and Michael Dixon},
      title = {{zkQMC}: Zero-Knowledge Proofs For (Some) Probabilistic Computations Using Quasi-Randomness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1007},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1007}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.