We provide an explicit algorithm for computing the trace of an endomorphism of an elliptic curve which is given by a chain of small-degree isogenies. We analyze its complexity, determining that if the length of the chain, the degree of the isogenies, and the log of the field-size are all O(n), the trace of the endomorphism can be computed in O(n⁶) bit operations. This makes explicit a theorem of Kohel which states that such a polynomial time algorithm exists. The given procedure is based on Schoof's point-counting algorithm. / Master of Science / The developing technology of quantum computers threatens to render current cryptographic systems (that is, systems for protecting stored or transmitted digital information from unauthorized third parties) ineffective. Among the systems proposed to ensure information security against attacks by quantum computers is a cryptographic scheme known as SIKE. In this thesis, we provide and analyze an algorithm that comprises one piece of a potential attack against SIKE by a classical computer. The given algorithm is also useful more generally in the field of arithmetic geometry.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/103821 |
| Date | 10 June 2021 |
| Creators | Wills, Michael Thomas |
| Contributors | Mathematics, Matthews, Gretchen L., Morrison, Travis William, Shimozono, Mark M., Orr, Daniel D. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Thesis |
| Format | ETD, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.0028 seconds