COMPARATIVE ANALYSIS OF THE APPLICATION OF FAST FOURIER TRANS-FORM AND NUMBER-THEORETICAL TRANSFORM IN FULL HOMOMORPHOUS ENCRYPTION SCHEMES

Read full text Summarise with VIRAT
Authors: Retivykh A., Retivykh V., Marinov A.
Cited by: 0

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