Elliptic curves have played a large role in modern cryptography. Most notably, the Elliptic Curve Digital Signature Algorithm (ECDSA) and the Elliptic Curve Diffie-Hellman (ECDH) key exchange algorithm are widely used in practice today for their efficiency and small key sizes. More recently, the Supersingular Isogeny-based Diffie-Hellman (SIDH) algorithm provides a method of exchanging keys which is conjectured to be secure in the post-quantum setting. For ECDSA and ECDH, efficient and secure algorithms for scalar multiplication of points are necessary for modern use of these protocols. Likewise, in SIDH it is necessary to be able to compute an isogeny from a given finite subgroup of an elliptic curve in a fast and secure fashion.
We therefore find strong motivation to study and improve the algorithms used in elliptic curve cryptography, and to develop new algorithms to be deployed within these protocols. In this thesis we design and develop d-MUL, a multidimensional scalar multiplication algorithm which is uniform in its operations and generalizes the well known 1-dimensional Montgomery ladder addition chain and the 2-dimensional addition chain due to Dan J. Bernstein. We analyze the construction and derive many optimizations, implement the algorithm in software, and prove many theoretical and practical results. In the final chapter of the thesis we analyze the operations carried out in the construction of an isogeny from a given subgroup, as performed in SIDH. We detail how to efficiently make use of parallel processing when constructing this isogeny.
|Commitee:||Klingler, Lee, Magliveras, Spyros, Steinwandt, Rainer|
|School:||Florida Atlantic University|
|School Location:||United States -- Florida|
|Source:||DAI-B 80/07/(E), Dissertation Abstracts International|
|Keywords:||Addition chains, Elliptic curve, Isogeny, SIDH, Scalar multiplication algorithm, d-MUL|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be