Comparison of different FFT implementations in the encrypted domain
Tiziano Bianchi, Alessandro Piva, Mauro Barni · 2008
Signal processing modules working directly on the encrypted data could provide an elegant solution to application scenar-ios where valuable signals should be protected from a mali-cious processing device. In this paper, we compare different implementations of the discrete Fourier transform (DFT) in the encrypted domain. Both radix-2 and radix-4 fast Fourier transforms (FFTs) will be defined using the homomorphic properties of the underlying cryptosystem. We derive the maximum size of the sequence that can be transformed by using the different implementations and we provide compu-tational complexity analyses and comparisons. The results show that the radix-4 FFT is best suited for an encrypted domain implementation. 1.