Faster and Smaller Variants of BinSIDH and TerSIDH

Recently, \(\textsf{binSIDH}\) and \(\textsf{terSIDH}\) have been proposed as new isogeny-based key exchange protocols to resist \(\textsf{SIDH}\) torsion point attacks. In this work, we propose two novel types of isogeny-based key exchange protocols based on \(\textsf{binSIDH}\) and \(\textsf{terSIDH}\) . Firstly, we propose \(\textsf{binSIDH}^{\textsf{ext}}\) and \(\textsf{terSIDH}^{\textsf{ext}}\) using different forms of primes in \(\textsf{binSIDH}\) and \(\textsf{terSIDH}\) . Secondly, we introduce a similar hardness assumption that reveals an image of torsion point of small order based on the assumption of \(\textsf{binSIDH}\) . We show that this assumption is sufficient to build parallel isogenies and construct two key exchange protocols called \(\textsf{binSIDH}^{\textsf{mix}}\) and \(\textsf{terSIDH}^{\textsf{mix}}\) . Finally, we provide the corresponding parameters for the new protocol proposed at different security levels and develop a Sagemath implementation of these protocols. For example, compared to the original \(\textsf{binSIDH}\) , when the security strength is 128 bits, \(\textsf{binSIDH}^{\textsf{ext}}\) and \(\textsf{binSIDH}^{\textsf{mix}}\) achieve speeds that are 2.2 \(\times \) and 28.5 \(\times \) faster in the key generation phase and 2.0 \(\times \) and 19.1 \(\times \) faster in the key exchange phase. The size of the public key is reduced by factors of 1.1 \(\times \) and 2.7 \(\times \) , respectively.