Classical and Quantum Algorithms for Isogeny-based Cryptography

cryptography;public-key;elliptic curve;isogeny;post-quantum;Combinatorics and Optimization

Sankar, Anirudh

University of Waterloo

关键词: cryptography;    public-key;    elliptic curve;    isogeny;    post-quantum;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/9756/3/Sankar_Anirudh.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Isogeny-based cryptography using supersingular elliptic curves --- most prominently, the constructions of De Feo-Jao-Plut --- is one of the few practical candidates for post-quantum public key cryptography. Its formidable security claim is earned through the continual exploration of quantum algorithms for `isogeny problems;; and the assessment of the threat they pose to supersingular isogeny-based cryptography. We survey the rich history of classical and quantum algorithms for isogeny problems, and close with an original result --- a quantum algorithm for the general supersingular isogeny problem, based on the discovery of Delfs and Galbraith in 2013 --- that has exponential-complexity in general and subexponential complexity in an important sub-case. As yet, this algorithm poses a limited threat to the schemes of De Feo-Jao-Plut; however, it is an important algorithm to consider, for it provides insight into the structure of supersingular curves and the isogenies between them, and may lead to newer destructive quantum algorithms.