Paper 2022/367
Efficient Algorithms for Large Prime Characteristic Fields and Their Application to Bilinear Pairings
Abstract
We propose a novel approach that generalizes interleaved modular multiplication algorithms for the computation of sums of products over large prime fields. This operation has widespread use and is at the core of many cryptographic applications. The method reformulates the widely used lazy reduction technique, crucially avoiding the need for storage and computation of "double-precision" operations. Moreover, it can be easily adapted to the different methods that exist to compute modular multiplication, producing algorithms that are significantly more efficient and memory-friendly.
We showcase the performance of the proposed approach in the computation of multiplication over an extension field
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in TCHES 2023
- Keywords
- Prime fieldsextension fieldsbilinear pairingsBLS12-381supersingular isogeniesefficient computation
- Contact author(s)
- plonga @ microsoft com
- History
- 2023-09-11: last of 2 revisions
- 2022-03-22: received
- See all versions
- Short URL
- https://ia.cr/2022/367
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/367, author = {Patrick Longa}, title = {Efficient Algorithms for Large Prime Characteristic Fields and Their Application to Bilinear Pairings}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/367}, year = {2022}, url = {https://eprint.iacr.org/2022/367} }