Paper 2019/1145
BSIDH: supersingular isogeny DiffieHellman using twisted torsion
Craig Costello
Abstract
This paper explores a new way of instantiating isogenybased cryptography in which parties can work in both the (p+1)torsion of a set of supersingular curves and in the (p1)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 xlines 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 jinvariant, 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 isogenybased public key cryptography. These include alternatives that exploit Mersenne and Montgomeryfriendly primes, as well as the possibility of significantly reducing the size of the primes in the JaoDe Feo construction at no known loss of asymptotic security. For a given target security level, the resulting public keys are smaller than the public keys of all of the key encapsulation schemes currently under consideration in the NIST postquantum standardisation effort. The best known attacks against the instantiations proposed in this paper are the classical path finding algorithm due to Delfs and Galbraith and its quantum adapation due to Biasse, Jao and Sankar; these run in respective time O(p^(1/2)) and O(p^(1/4)), and are essentially memoryfree. The upshot is that removing the bigO's and obtaining concrete security estimates is a matter of costing the circuits needed to implement the corresponding isogeny. In contrast to other postquantum proposals, this makes the security analysis of BSIDH rather straightforward. Searches for friendly parameters are used to find several primes that range from 237 to 256 bits, the conjectured security of which are comparable to the 434bit prime used to target NIST level 1 security in the SIKE proposal. One noteworthy example is a 247bit prime for which Alice's secret isogeny is 7901smooth and Bob's secret isogeny is 7621smooth.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in ASIACRYPT 2020
 Keywords
 Postquantum cryptographysupersingular isogeniesSIDHSIKEquadratic twists
 Contact author(s)
 craigco @ microsoft com
 History
 20201119: last of 4 revisions
 20191003: received
 See all versions
 Short URL
 https://ia.cr/2019/1145
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1145, author = {Craig Costello}, title = {B{SIDH}: supersingular isogeny DiffieHellman using twisted torsion}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/1145}, year = {2019}, url = {https://eprint.iacr.org/2019/1145} }