Efficiency of SIDH-based signatures (yes, SIDH)

Abstract In this note, we assess the efficiency of a supersingular isogeny Diffie-Hellman (SIDH)-based digital signature built on a weaker variant of a recent identification protocol proposed by Basso et al. Despite the devastating attacks against (the mathematical problem underlying) SIDH, this identification protocol remains secure, as its security is backed by a different (and more standard) isogeny-finding problem. We conduct our analysis by applying some known cryptographic techniques to decrease the signature size by about 70% for all parameter sets (obtaining signatures of approximately 21 kB for <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="sans-serif">SIKE</m:mi> <m:mi mathvariant="sans-serif">p</m:mi> <m:mn>434</m:mn> </m:math> {\mathsf{SIKE}}{\mathsf{p}}434 ).

Moreover, we propose a minor optimisation to compute many isogenies in parallel from the same starting curve. Our assessment confirms that determining the most efficient methods for isogeny-based signature schemes, including optimisations such as those presented in this paper, is still a open problem, with much more work to be done.