University of Waterloo
Classical and Quantum Algorithms for Isogeny-based Cryptography
Abstract
dc:description.abstractIsogeny-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.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2015
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Sankar, Anirudh
Subjects
dc:subject × 5Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/9756