Paper 2024/859
Novel approximations of elementary functions in zero-knowledge proofs
Abstract
In this paper, we study the computation of complex mathematical functions in statements executed on top of zero-knowledge proofs (ZKP); these functions may include roots, exponentials and logarithms, trigonometry etc. While existing approaches to these functions in privacy-preserving computations (and sometimes also in general-purpose processors) have relied on polynomial approximation, more powerful methods are available for ZKP. In this paper, we note that in ZKP, all algebraic functions are exactly computable. Recognizing that, we proceed to the approximation of transcendental functions with algebraic functions. We develop methods of approximation, instantiate them on a number of common transcendental functions, and benchmark their precision and efficiency in comparison with best polynomial approximations.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- zero-knowledgefixed-point numberselementary functions
- Contact author(s)
- peeter laud @ cyber ee
- History
- 2024-06-05: approved
- 2024-05-31: received
- See all versions
- Short URL
- https://ia.cr/2024/859
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2024/859,
author = {Kaarel August Kurik and Peeter Laud},
title = {Novel approximations of elementary functions in zero-knowledge proofs},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/859},
year = {2024},
url = {https://eprint.iacr.org/2024/859}
}
