Paper 2018/932

18 Seconds to Key Exchange: Limitations of Supersingular Isogeny Diffie-Hellman on Embedded Devices

Philipp Koppermann, Eduard Pop, Johann Heyszl, and Georg Sigl

Abstract

The quantum secure supersingular isogeny Diffie-Hellman (SIDH) key exchange is a promising candidate in NIST's on-going post-quantum standardization process. The evaluation of various implementation characteristics is part of this standardization process, and includes the assessment of the applicability on constrained devices. When compared to other post-quantum algorithms, SIDH appears to be well-suited for the implementation on those constrained devices due to its small key sizes. On the other hand, SIDH is computationally complex, which presumably results in long computation times. Since there are no published results to test this assumption, we present speed-optimized implementations for two small microcontrollers and set a first benchmark that can be of relevance for the standardization process. We use state-of-the art field arithmetic algorithms and optimize them in assembly. However, an ephemeral key exchange still requires more than 18 seconds on a 32-bit Cortex-M4 and more than 11 minutes on a 16-bit MSP430. Those results show that even with an improvement by a factor of 4, SIDH is in-fact impractical for small embedded devices, regardless of further possible improvements in the implementation. On a positive note, we also analyzed the implementation security of SIDH and found that appropriate DPA countermeasures can be implemented with little overhead.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
Post-quantum cryptographysupersingularisogenySIDHECCembedded devicesefficient implementationside-channel analysis
Contact author(s)
philipp koppermann @ aisec fraunhofer de
History
2018-10-02: received
Short URL
https://ia.cr/2018/932
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/932,
      author = {Philipp Koppermann and Eduard Pop and Johann Heyszl and Georg Sigl},
      title = {18 Seconds to Key Exchange: Limitations of Supersingular Isogeny Diffie-Hellman on Embedded Devices},
      howpublished = {Cryptology ePrint Archive, Paper 2018/932},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/932}},
      url = {https://eprint.iacr.org/2018/932}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.