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
SIKEisogeny-based cryptographypublic key compressiondiscrete 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.