Paper 2023/791

New SIDH Countermeasures for a More Efficient Key Exchange

Andrea Basso, University of Bristol
Tako Boris Fouotsa, École Polytechnique Fédérale de Lausanne
Abstract

The Supersingular Isogeny Diffie-Hellman (SIDH) protocol has been the main and most efficient isogeny-based encryption protocol, until a series of breakthroughs led to a polynomial-time key-recovery attack. While some countermeasures have been proposed, the resulting schemes are significantly slower and larger than the original SIDH. In this work, we propose a new countermeasure technique that leads to significantly more efficient and compact protocols. To do so, we introduce the concept of artificially oriented curves, which are curves with an associated pair of subgroups. We show that this information is sufficient to build parallel isogenies and thus obtain an SIDH-like key exchange, while also revealing significantly less information compared to previous constructions. After introducing artificially oriented curves, we formalize several related computational problems and thoroughly assess their presumed hardness. We then translate the SIDH key exchange to the artificially oriented setting, obtaining the key-exchange protocols binSIDH, or binary SIDH, and terSIDH, or ternary SIDH, which respectively rely on fixed-degree and variable-degree isogenies. Lastly, we also provide a proof-of-concept implementation of the proposed protocols. Despite being implemented in a high-level language, terSIDH has very competitive running times, which suggests that terSIDH might be the most efficient isogeny-based encryption protocol.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Key-exchangeIsogeniesSIDH
Contact author(s)
andrea basso @ bristol ac uk
tako fouotsa @ epfl ch
History
2023-10-12: revised
2023-05-30: received
See all versions
Short URL
https://ia.cr/2023/791
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/791,
      author = {Andrea Basso and Tako Boris Fouotsa},
      title = {New SIDH Countermeasures for a More Efficient Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2023/791},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/791}},
      url = {https://eprint.iacr.org/2023/791}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.