COMPARATIVE ANALYSIS OF THE APPLICATION OF FAST FOURIER TRANS-FORM AND NUMBER-THEORETICAL TRANSFORM IN FULL HOMOMORPHOUS ENCRYPTION SCHEMES
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
Abstract This paper provides an in-depth analysis of two fundamental algorithms – the Fast Fourier Transform (FFT) and the Number Theoretic Transform (NTT) – in the context of their application in Fully Homomorphic Encryption (FHE) systems. It is shown that, despite sharing a common algorithmic basis (the divide-and-conquer strategy) and identical asymptotic complexity of , the choice between them is dictated by the error model of a specific cryptosystem. A detailed mathematical derivation of NTT for the ring , which underlies the BGV, BFV, and CKKS schemes, is presented. A comparative analysis of accuracy, performance, and hardware implementability is performed. It is established that for schemes with exact integer arithmetic (BGV, BFV), NTT is the only possible choice, while in the approximate computation scheme (CKKS), FFT is used at the data encoding stage, and NTT is used for cryptographic operations.
Fields of Study & Subjects
Cryptography and Data Security
Cryptography and Residue Arithmetic
Cryptographic Implementations and Security
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 12 March 2026
- Language
- EN