Paper 2019/1145

B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion

Craig Costello

Abstract

This paper introduces a new way of instantiating supersingular isogeny-based cryptography in which parties can work in both the ($p+1$)-torsion of a set of supersingular curves and in the ($p-1$)-torsion corresponding to the set of their quadratic twists. Although the isomorphism between a given supersingular curve and its quadratic twist is not defined over GF($p^2$) in general, restricting operations to the x-lines of both sets of twists allows all arithmetic to be carried out over GF($p^2$) as usual. Furthermore, since supersingular twists always have the same GF($p^2$)-rational j-invariant, the SIDH protocol remains unchanged when Alice and Bob are free to work in both sets of twists. This framework lifts the restrictions on the shapes of the underlying prime fields originally imposed by Jao and De Feo, and allows a range of new options for instantiating isogeny- based public key cryptography. This includes alternatives that exploit Mersenne, Solinas, and Montgomery-friendly primes, the possibility of halving the size of the primes of the Jao-De Feo construction at no known loss of asymptotic security, and more.