Paper 2022/1007
zkQMC: Zero-Knowledge Proofs For (Some) Probabilistic Computations Using Quasi-Randomness
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
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
-
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} }