You are here
ANALYSIS OF CRYPTOGRAPHIC EFFICIENCY: ELLIPTIC CURVE SCALAR MULTIPLICATION AND CONSTANT-TIME POLYNOMIAL INVERSION IN POST-QUANTUM CRYPTOGRAPHY
- Date Issued:
- 2024
- Abstract/Description:
- An efficient scalar multiplication algorithm is vital for elliptic curve cryptosystems. The first part of this dissertation focuses on a scalar multiplication algorithm based on scalar recodings resistant to timing attacks. The algorithm utilizes two recoding methods: Recode, which generalizes the non-zero signed all-bit set recoding, and Align, which generalizes the sign aligned columns recoding. For an ℓ-bit scalar split into d subscalars, our algorithm has a computational cost of ⌈⌈ℓ logk(2)⌉/d⌉ point additions and k-scalar multiplications and a storage cost of kd−1(k − 1) – 1 points on E. The “split and comb” method further optimizes computational and storage complexity. We find the best setting to be with a fixed base point on a Twisted Edwards curve using a mix of projective and extended coordinates, with k = 2 generally offering the best performance. However, k = 3 may be better in certain applications. The second part of this dissertation is dedicated to constant-time polynomial inversion algorithms in Post-Quantum Cryptography (PQC). The computation of the inverse of a polynomial over a quotient ring or finite field is crucial for key generation in post-quantum cryptosystems like NTRU, BIKE, and LEDACrypt. Efficient algorithms must run in constant time to prevent side-channel attacks. We examine constant-time algorithms based on Fermat’s Little Theorem and the Extended GCD Algorithm, providing detailed time complexity analysis. We find that the constant-time Extended GCD inversion algorithm is more efficient, performing fewer field multiplications. Additionally, we explore other exponentiation algorithms similar to the Itoh-Tsuji inversion method, which optimizes polynomial multiplications in the BIKE/LEDACrypt setup. Recent results on hardware implementations are also discussed.
Title: | ANALYSIS OF CRYPTOGRAPHIC EFFICIENCY: ELLIPTIC CURVE SCALAR MULTIPLICATION AND CONSTANT-TIME POLYNOMIAL INVERSION IN POST-QUANTUM CRYPTOGRAPHY. |
![]() ![]() |
---|---|---|
Name(s): |
Dutta, Abhraneel, author Persichetti, Edoardo, Thesis advisor Karabina, Koray, Thesis advisor Florida Atlantic University, Degree grantor Department of Mathematical Sciences Charles E. Schmidt College of Science |
|
Type of Resource: | text | |
Genre: | Electronic Thesis Or Dissertation | |
Date Created: | 2024 | |
Date Issued: | 2024 | |
Publisher: | Florida Atlantic University | |
Place of Publication: | Boca Raton, Fla. | |
Physical Form: | application/pdf | |
Extent: | 122 p. | |
Language(s): | English | |
Abstract/Description: | An efficient scalar multiplication algorithm is vital for elliptic curve cryptosystems. The first part of this dissertation focuses on a scalar multiplication algorithm based on scalar recodings resistant to timing attacks. The algorithm utilizes two recoding methods: Recode, which generalizes the non-zero signed all-bit set recoding, and Align, which generalizes the sign aligned columns recoding. For an ℓ-bit scalar split into d subscalars, our algorithm has a computational cost of ⌈⌈ℓ logk(2)⌉/d⌉ point additions and k-scalar multiplications and a storage cost of kd−1(k − 1) – 1 points on E. The “split and comb” method further optimizes computational and storage complexity. We find the best setting to be with a fixed base point on a Twisted Edwards curve using a mix of projective and extended coordinates, with k = 2 generally offering the best performance. However, k = 3 may be better in certain applications. The second part of this dissertation is dedicated to constant-time polynomial inversion algorithms in Post-Quantum Cryptography (PQC). The computation of the inverse of a polynomial over a quotient ring or finite field is crucial for key generation in post-quantum cryptosystems like NTRU, BIKE, and LEDACrypt. Efficient algorithms must run in constant time to prevent side-channel attacks. We examine constant-time algorithms based on Fermat’s Little Theorem and the Extended GCD Algorithm, providing detailed time complexity analysis. We find that the constant-time Extended GCD inversion algorithm is more efficient, performing fewer field multiplications. Additionally, we explore other exponentiation algorithms similar to the Itoh-Tsuji inversion method, which optimizes polynomial multiplications in the BIKE/LEDACrypt setup. Recent results on hardware implementations are also discussed. | |
Identifier: | FA00014492 (IID) | |
Degree granted: | Dissertation (PhD)--Florida Atlantic University, 2024. | |
Collection: | FAU Electronic Theses and Dissertations Collection | |
Note(s): | Includes bibliography. | |
Subject(s): |
Cryptography Curves, Elliptic Polynomials |
|
Persistent Link to This Record: | http://purl.flvc.org/fau/fd/FA00014492 | |
Use and Reproduction: | Copyright © is held by the author with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder. | |
Use and Reproduction: | http://rightsstatements.org/vocab/InC/1.0/ | |
Host Institution: | FAU |