Paper 2020/021

eSIDH: the revenge of the SIDH

Daniel Cervantes-Vázquez, Eduardo Ochoa-Jiménez, and Francisco Rodríguez-Henríquez

Abstract

The Supersingular Isogeny-based Diffie-Hellman key exchange protocol (SIDH) was introduced by Jao an De Feo in 2011. SIDH operates on supersingular elliptic curves defined over quadratic extension fields of the form GF($p^2$), where $p$ is a large prime number of the form $p = 4^{e_A} 3^{e_B} - 1,$ where $e_A, e_B$ are positive integers such that $4^{e_A} \approx 3^{e_B}.$ In this paper, a variant of the SIDH protocol that we dubbed extended SIDH (eSIDH) is presented. The eSIDH variant makes use of primes of the form, $p = 4^{e_A} \ell_B^{e_B}\ell_C^{e_C} f - 1.$ Here $\ell_B, \ell_C $ are two small prime numbers; $f$ is a cofactor; and $e_A, e_B$ and $e_C$ are positive integers such that $4^{e_A} \approx \ell_B^{e_B}\ell_C^{e_C}.$ We show that for many relevant instantiations of the SIDH protocol, this new family of primes enjoys a faster field arithmetic than the one associated to traditional SIDH primes. Furthermore, the proposed eSIDH protocol preserves the length and format of SIDH private/public keys, and its richer opportunities for parallelism yields a noticeable speedup factor when implemented on multi-core platforms. Using a single-core SIDH $p_{751}$ implementation as a baseline, a parallel eSIDH $p_{765}$ instantiation yields an acceleration factor of $1.05, 1.30$ and $1.41,$ when implemented on $k = \{1, 2, 3\}$-core processors. In addition, eSIDH $p_{765}$ yields an acceleration factor of $1.050, 1.160$ and $1.162.$ when both protocols are implemented on $k = \{1, 2, 3\}$-core processors. To our knowledge, this work reports the first multi-core implementation of SIDH.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
post-quantum cryptographyisogeny-based cryptographySIDHefficient implementation
Contact author(s)
francisco @ cs cinvestav mx
dcervantes @ computacion cs cinvestav mx
History
2020-01-14: last of 6 revisions
2020-01-07: received
See all versions
Short URL
https://ia.cr/2020/021
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/021,
      author = {Daniel Cervantes-Vázquez and Eduardo Ochoa-Jiménez and Francisco Rodríguez-Henríquez},
      title = {eSIDH: the revenge of the SIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2020/021},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/021}},
      url = {https://eprint.iacr.org/2020/021}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.