Paper 2022/1396

FPGA Acceleration of Multi-Scalar Multiplication: CycloneMSM

Kaveh Aasaraai, Jump Trading
Don Beaver, Jump Crypto
Emanuele Cesena, Jump Crypto
Rahul Maganti, Jump Crypto
Nicolas Stalder, Jump Crypto
Javier Varela, Jump Trading
Abstract

Multi-Scalar Multiplication (MSM) on elliptic curves is one of the primitives and bottlenecks at the core of many zero-knowledge proof systems. Speeding up MSM typically results in faster proof generation, which in turn makes ZK-based applications practical. We focus on accelerating large MSM on FPGA, and we present speed records for $\texttt{BLS12-377}$ on FPGA: 5.66s for $N=2^{26}$, sub-second for $N=2^{22}$. We developed a fully-pipelined curve adder in extended Twisted Edwards coordinates that runs at 250MHz. Our architecture incorporates a scheduler to reorder curve operations, that's suitable not just for hardware acceleration, but also for software implementations using affine coordinates with batch inversion. The software implementation achieves +$10-20$\% performance improvement over the state-of-the-art $\texttt{gnark-crypto}$ library.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Multi-Scalar Multiplication Elliptic Curve Cryptography FPGA Design Zero-Knowledge Proofs MSM ECC FPGA ZK ZKP
Contact author(s)
kaasaraai @ jumptrading com
dbeaver @ jumpcrypto com
ecesena @ jumpcrypto com
rmaganti @ jumpcrypto com
nicolas @ jumpcrypto com
jvarela @ jumptrading com
History
2022-10-15: approved
2022-10-14: received
See all versions
Short URL
https://ia.cr/2022/1396
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2022/1396,
      author = {Kaveh Aasaraai and Don Beaver and Emanuele Cesena and Rahul Maganti and Nicolas Stalder and Javier Varela},
      title = {FPGA Acceleration of Multi-Scalar Multiplication: CycloneMSM},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1396},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1396}},
      url = {https://eprint.iacr.org/2022/1396}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.