Paper 2021/990

Secret Keys in Genus-2 SIDH

Sabrina Kunzweiler, Yan Bo Ti, and Charlotte Weitkämper

Abstract

We present a polynomial-time adaptive attack on the genus-2 variant of the SIDH protocol (G2SIDH) and describe an improvement to its secret selection procedure. G2SIDH is a generalisation of the Supersingular Isogeny Diffie--Hellman key exchange into the genus-2 setting which was proposed by Flynn and Ti. G2SIDH is able to achieve the same security as SIDH while using fields a third of the size. We analyze the keyspace of G2SIDH and achieve an improvement to the secret selection by using symplectic bases for the torsion subgroups. This allows for the near uniform sampling of secrets without needing to solve multiple linear congruences as suggested by Flynn--Ti. More generally, using symplectic bases enables us to classify and enumerate isogeny kernel subgroups and thus simplify the secret sampling step for general genus-2 SIDH-style constructions. The proposed adaptive attack on G2SIDH is able to recover the secret when furnished with an oracle that returns a single bit of information. We ensure that the maliciously generated information provided by the attacker cannot be detected by implementing simple countermeasures, forcing the use of the Fujisaki--Okamoto transform for CCA2-security. We demonstrate this attack and show that it is able to recover the secret isogeny in all cases of G2SIDH using a symplectic basis before extending the strategy to arbitrary bases.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Selected Areas in Cryptography (SAC) 2021
Keywords
Isogeny-based cryptographyGenus-2 SIDHcryptanalysisadaptive attack
Contact author(s)
C Weitkaemper @ pgr bham ac uk
History
2021-10-19: revised
2021-07-28: received
See all versions
Short URL
https://ia.cr/2021/990
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/990,
      author = {Sabrina Kunzweiler and Yan Bo Ti and Charlotte Weitkämper},
      title = {Secret Keys in Genus-2 {SIDH}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/990},
      year = {2021},
      url = {https://eprint.iacr.org/2021/990}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.