International Association for Cryptologic Research

International Association
for Cryptologic Research


New SIDH Countermeasures for a More Efficient Key Exchange

Andrea Basso , University of Bristol, United Kingdom
Tako Boris Fouotsa , EPFL, Switzerland
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
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, i.e. 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 a high-level SageMath implementation, it already outperforms existing implementations of other isogeny-based encryption schemes, which suggests that terSIDH might be the most efficient isogeny-based encryption protocol.
  title={New SIDH Countermeasures for a More Efficient Key Exchange},
  author={Andrea Basso and Tako Boris Fouotsa},