Design & Cryptanalysis of Isogeny-Based Post-Quantum Cryptosystems

Post-quantum cryptography is concerned with securing information against adversaries in the possession of a sufficiently large quantum computer, something which many current protocols in widespread use fail to do. Such computers currently only exist in theory, however promising trends in quantum computing, combined with modern society's dependence on secure communication, have fuelled the drive to create cryptographic systems which are quantum resistant.

Within this area, isogeny-based cryptography is an approach that has garnered much research interest in the past decade, proposed schemes appear to resist quantum computing attacks, as well as requiring comparatively little bandwidth. Isogeny based protocols typically rely on the comparative difficulty of finding an unknown function (an isogeny) given its endpoints, vs evaluating a known function. Recently, advances have been made in the former efficiency problem, increasing the appeal of these protocols. The latter security problem is still believed to be difficult, though this is still highly speculative.

Post-quantum protocols in general are unlikely to gain widespread use whilst their security is not fully understood. This is certainly the case for isogeny-based schemes, given their relative novelty. Indeed, the most prominent protocol SIDH/SIKE is only around a decade old, with an explosion of newer schemes proposed in the past 3 years. As a comparison, some algorithms in NIST's post-quantum standardisation process date back to the 70's. This project aims to improve understanding of the security of isogeny-based cryptosystems and thus improve confidence in those wishing to implement these protocols. Indeed, it is only through a better understanding of security that standardisation can begin, as this process requires concrete parameters.

Broadly, the best current attacks on isogeny schemes exploit general combinatorial structures, relying very little on the rich algebraic and geometric properties of the actual underlying elliptic curves. This seems remarkable on the surface and may install confidence in the security of these protocols. On the other hand, this may again be a symptom of the relative youth of this field of research, combined with the inaccessibility of the number theoretic tools required to possibly break these schemes. Objects such as quaternion algebras see little study outside of graduate level mathematics yet are fundamental in describing isogeny-based protocols. Reinterpreting these classical objects from a cryptographic and computational perspective will be key in better evaluating security arguments.

Further uncertainties revolve around the lack of clarity around the definition of quantum security goals. Current NIST definitions rely on a somewhat vague comparison with classical security notions, with little justification. This partly has not been addressed as many alternative approaches to post quantum cryptography have classical attacks that outperform their quantum counterparts. This is not the case for some isogeny-based schemes and as such, the validity of these definitions has been brought into question. Further work is required to build consensus on appropriate quantum cost metrics and define appropriate tools to compare these to classical costs. Assessing schemes with respect to these new metrics will then be required before concrete security claims can be made.

This project falls within the EPSRC Mathematical Sciences research area.