On the capacity of secure distributed fast fourier transform

Discrete Fourier transform (DFT) is a fundamental building block for various signal processing applications, and speeding up large-scale DFT/FFT using distributed processing is often desirable. In this paper, we consider the problem of distributed DFT computation from untrustworthy servers. In particular, we study the scenario where the goal is to compute the DFT of an s-length signal from N distributed and untrustworthy servers, where any ℓ out of N servers can collude. The signal must be kept information-theoretically secure from any ℓ out of N servers. The goal of this paper is to characterize the minimum communication overhead while maintaining security in an information-theoretic sense. The capacity of the secure distributed FFT is defined as the maximum possible ratio of the desired information (signal length s) and the total information received from all N distributed servers. We present lower and upper bounds on capacity of secure distributed FFT, and show that these bounds match exactly when N ℓ is a power of 2, and the bounds match asymptotically when-N becomes large.