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. These include alternatives that exploit Mersenne and Montgomery-friendly primes, as well as the possibility of significantly reducing the size of the primes in the Jao-De 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 post-quantum 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 memory-free. The upshot is that removing the big-O's and obtaining concrete security estimates is a matter of costing the circuits needed to implement the corresponding isogeny. In contrast to other post-quantum proposals, this makes the security analysis of B-SIDH 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 434-bit prime used to target NIST level 1 security in the SIKE proposal. One noteworthy example is a 247-bit prime for which Alice's secret isogeny is 7901-smooth and Bob's secret isogeny is 7621-smooth.
Category / Keywords: public-key cryptography / Post-quantum cryptography, supersingular isogenies, SIDH, SIKE, quadratic twists Original Publication (in the same form): IACR-ASIACRYPT-2020 Date: received 3 Oct 2019, last revised 19 Nov 2020 Contact author: craigco at microsoft com Available format(s): PDF | BibTeX Citation Version: 20201119:213708 (All versions of this report) Short URL: ia.cr/2019/1145