Paper 2022/367

Efficient Algorithms for Large Prime Characteristic Fields and Their Application to Bilinear Pairings and Supersingular Isogeny-Based Protocols

Patrick Longa

Abstract

We propose a novel approach that generalizes interleaved modular multiplication algorithms to 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 GF(p^k), and demonstrate its impact in two popular cryptographic settings: bilinear pairings and supersingular isogeny-based protocols. For the former, we obtain a 1.37x speedup in the computation of a full optimal ate pairing over the popular BLS12-381 curve on an x64 Intel processor; for the latter, we show a speedup of up to 1.30x in the computation of the SIKE protocol on the same Intel platform.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Prime fieldsextension fieldsbilinear pairingsBLS12-381supersingular isogeny-based cryptographySIKEefficient computation.
Contact author(s)
plonga @ microsoft com
History
2022-03-22: received
Short URL
https://ia.cr/2022/367
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/367,
      author = {Patrick Longa},
      title = {Efficient Algorithms for Large Prime Characteristic Fields and Their Application to Bilinear Pairings and Supersingular Isogeny-Based Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2022/367},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/367}},
      url = {https://eprint.iacr.org/2022/367}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.