Paper 2025/933 Original: eprint.iacr.org/2025/933 ↗
Fast elliptic curve scalar multiplications in SN(T)ARK circuits
Abstract
Proof systems of arbitrary computations have found many applications in recent years. However, the proving algorithm has a consequent complexity tied to the size of the computation being proved. Thus, proving large computations is quite inefficient. One of these large computations is the scalar multiplication over an elliptic curve. In this work, we provide new techniques for reducing the time corresponding to proving a scalar multiplication, using integer lattice reduction or a (half) extended Euclidean algorithm in a ring of integers. We investigate optimizations in the case of small (complex multiplication) discriminant curves, and its generalization for multi scalar multiplications as used in signature verification. We provide an optimized Golang implementation for different elliptic curves in different proof systems settings. The speed-up in proving time is between 22% and 53% compared to the previous state-of-the-art.
Metadata
- Available format(s)
PDF- Category
- Implementation
- Publication info
- Preprint.
- History
- 2025-10-17: last updated
- 2025-05-22: published
- Short URL
- https://ia.cr/2025/933
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/933,
author = {Liam Eagen and Youssef El Housni and Simon Masson and Thomas Piellard},
title = {Fast elliptic curve scalar multiplications in SN(T)ARK circuits},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/933},
year = {2025},
url = {https://eprint.iacr.org/2025/933}
}