Cryptology ePrint Archive: Report 2018/932

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

Philipp Koppermann and Eduard Pop and 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.

Category / Keywords: implementation / Post-quantum cryptography, supersingular, isogeny, SIDH, ECC, embedded devices, efficient implementation, side-channel analysis

Date: received 30 Sep 2018

Contact author: philipp koppermann at aisec fraunhofer de

Available format(s): PDF | BibTeX Citation

Version: 20181002:041138 (All versions of this report)

Short URL: ia.cr/2018/932


[ Cryptology ePrint archive ]