You are here

ANALYSIS OF CRYPTOGRAPHIC EFFICIENCY: ELLIPTIC CURVE SCALAR MULTIPLICATION AND CONSTANT-TIME POLYNOMIAL INVERSION IN POST-QUANTUM CRYPTOGRAPHY

Download pdf | Full Screen View

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.
29 views
7 downloads
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