On the capacity of secure distributed fast fourier transform

Wei Ting Chang, Ravi Tandon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages653-657
Number of pages5
ISBN (Electronic)9781728112954
DOIs
StatePublished - Feb 20 2019
Externally publishedYes
Event2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Anaheim, United States
Duration: Nov 26 2018Nov 29 2018

Publication series

Name2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018 - Proceedings

Conference

Conference2018 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2018
Country/TerritoryUnited States
CityAnaheim
Period11/26/1811/29/18

Keywords

  • Distributed FFT
  • Information-theoretic Security

ASJC Scopus subject areas

  • Information Systems
  • Signal Processing

Fingerprint

Dive into the research topics of 'On the capacity of secure distributed fast fourier transform'. Together they form a unique fingerprint.

Cite this