Paper 2023/858
Effective Pairings in Isogeny-based Cryptography
Abstract
Pairings are useful tools in isogeny-based cryptography and have been used in SIDH/SIKE and other protocols. As a general technique, pairings can be used to move problems about points on curves to elements in finite fields. However, until now, their applicability was limited to curves over fields with primes of a specific shape and pairings seemed too costly for the type of primes that are nowadays often used in isogeny-based cryptography. We remove this roadblock by optimizing pairings for highly-composite degrees such as those encountered in CSIDH and SQISign. This makes the general technique viable again: We apply our low-cost pairing to problems of general interest, such as supersingularity verification and finding full-torsion points, and show that we can outperform current methods, in some cases up to four times faster than the state-of-the-art. Furthermore, we analyze how pairings can be used to improve deterministic and dummy-free CSIDH. Finally, we provide a constant-time implementation (in Rust) that shows the practicality of these algorithms.
Note: Version finalised for LATINCRYPT 2023.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. LATINCRYPT 2023
- Keywords
- post-quantum cryptographyisogeniespairingsCSIDHdeterministic
- Contact author(s)
- krijn @ cs ru nl
- History
- 2023-08-07: revised
- 2023-06-07: received
- See all versions
- Short URL
- https://ia.cr/2023/858
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/858,
author = {Krijn Reijnders},
title = {Effective Pairings in Isogeny-based Cryptography},
howpublished = {Cryptology ePrint Archive, Paper 2023/858},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/858}},
url = {https://eprint.iacr.org/2023/858}
}
