Paper 2025/166

Polynomial Inversion Algorithms in Constant Time for Post-Quantum Cryptography

Abhraneel Dutta, Florida Atlantic University
Emrah Karagoz, Florida Atlantic University
Edoardo Persichetti, Florida Atlantic University
Pakize Sanal, Florida Atlantic University
Abstract

The computation of the inverse of a polynomial over a quotient ring or a finite field plays a very important role during the key generation of post-quantum cryptosystems like NTRU, BIKE, and LEDACrypt. It is therefore important that there exist an efficient algorithm capable of running in constant time, to prevent timing side-channel attacks. In this article, we study both constant-time algorithms based on Fermat's Little Theorem and the Extended $GCD$ Algorithm, and provide a detailed comparison in terms of performance. According to our conclusion, we see that the constant-time Extended $GCD$-based Bernstein-Yang's algorithm shows a better performance with 1.76x-3.76x on \texttt{x86} platforms compared to FLT-based methods. Although we report numbers from a software implementation, we additionally provide a short glimpse of some recent results when these two algorithms are implemented on various hardware platforms. Finally, we also explore other exponentiation algorithms that work similarly to the Itoh-Tsuji inversion method. These algorithms perform fewer polynomial multiplications and show a better performance with 1.56x-1.96x on \texttt{x86} platform compared to Itoh-Tsuji inversion method.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Indocrypt 2024
Keywords
Post-QuantumPolynomial InversionConstant TimeQC-MDPC
Contact author(s)
adutta2016 @ fau edu
ekaragoz2017 @ fau edu
epersichetti @ fau edu
psanal2018 @ fau edu
History
2025-02-09: revised
2025-02-04: received
See all versions
Short URL
https://ia.cr/2025/166
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/166,
      author = {Abhraneel Dutta and Emrah Karagoz and Edoardo Persichetti and Pakize Sanal},
      title = {Polynomial Inversion Algorithms in Constant Time for Post-Quantum Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/166},
      year = {2025},
      url = {https://eprint.iacr.org/2025/166}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.