Memory Optimization Techniques for Computing Discrete Logarithms in Compressed SIKE

Aaron Hutchinson; Koray Karabina; Geovandro Pereira

Paper 2021/368

Memory Optimization Techniques for Computing Discrete Logarithms in Compressed SIKE

Aaron Hutchinson, Koray Karabina, and Geovandro Pereira

Abstract

The supersingular isogeny-based key encapsulation (SIKE) suite stands as an attractive post-quantum cryptosystem with its relatively small public keys. Public key sizes in SIKE can further be compressed by computing pairings and solving discrete logarithms in certain subgroups of finite fields. This comes at a cost of precomputing and storing large discrete logarithm tables. In this paper, we propose several techniques to optimize memory requirements in computing discrete logarithms in SIKE, and achive to reduce table sizes by a factor of 4. We implement our techniques and verify our theoretical findings.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: SIKE isogeny-based cryptography public key compression discrete logarithms
Contact author(s): a5hutchinson @ uwaterloo ca
profkarabina @ gmail com
geovandro pereira @ uwaterloo ca
History: 2021-03-22: received
Short URL: https://ia.cr/2021/368
License: CC BY

BibTeX

@misc{cryptoeprint:2021/368,
      author = {Aaron Hutchinson and Koray Karabina and Geovandro Pereira},
      title = {Memory Optimization Techniques for Computing Discrete Logarithms in Compressed SIKE},
      howpublished = {Cryptology ePrint Archive, Paper 2021/368},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/368}},
      url = {https://eprint.iacr.org/2021/368}
}