Secure Convolution in the Frequency Domain

This direction is merged into another direction: homomorphic encryption overhead. Its last version stays readable and citable here.

Version 1 of 111 papers19 conceptsfrozen 2026-10-04

Privacy-preserving machine learning allows a server to process a client's data without ever "seeing" the raw input. This is typically achieved through Homomorphic Encryption (HE) or Secure Multi-party Computation (MPC). However, these cryptographic tools come with a massive performance tax. In standard spatial-domain convolutions, the sliding-window operation requires a series of expensive "rotate-and-accumulate" steps on encrypted ciphertexts, leading to significant computational overhead and data expansion.

A growing body of research suggests that the key to making private inference practical is to stop convolving in the spatial domain and instead move the entire operation into the frequency domain.

The Convolution Theorem Shortcut

The core intuition behind this shift is the Convolution Theorem. In classical signal processing, a convolution in the spatial domain (sliding a filter over an image) is mathematically equivalent to a point-wise multiplication in the frequency domain.

By transforming both the input data and the model weights into the frequency domain using tools like the Fast Fourier Transform (FFT) or the Discrete Cosine Transform (DCT), researchers can replace thousands of complex spatial operations with simple, element-wise multiplications. For encrypted data, this is a game-changer: point-wise multiplication is one of the few operations that lattice-based homomorphic encryption handles efficiently.

Accelerating Linear Layers with FFT and NTT

The FALCON framework, developed by Feng Wu 0001, Shaohua Li 0002, and their colleagues, demonstrates the power of this approach. In FALCON: A Fourier Transform Based Approach for Fast and Secure Convolutional Neural Network Predictions, the authors show that performing convolutions in the frequency domain via FFT can speed up predictions by up to 27x compared to previous spatial-domain methods. By avoiding the "ciphertext expansion" that occurs during standard encrypted convolutions, FALCON significantly reduces the communication bandwidth required between the client and the server.

Building on this, Song Bian and Yiyu Shi introduced ENSEI in ENSEI: Efficient Secure Inference via Frequency-Domain Homomorphic Convolution for Privacy-Preserving Visual Recognition. ENSEI utilizes the Number-Theoretic Transform (NTT)—a version of the Fourier transform that operates over finite fields—to achieve a 10x speedup. The NTT is particularly well-suited for cryptography because it avoids the floating-point errors associated with standard FFTs, ensuring that the decrypted results remain perfectly accurate.

Scaling to High Resolution with DCT

While FFT and NTT focus on accelerating the linear math of convolution, the frequency domain also offers opportunities for data compression. In DCT-CryptoNets: Scaling Private Inference in the Frequency Domain, Arjun Roy and Kaushik Roy leverage the Discrete Cosine Transform (DCT)—the same technology behind JPEG compression.

By processing images in the DCT domain, the network can "see" the most important frequency components of an image immediately. This allows the framework to:

  1. Compress spatial dimensions early, reducing the number of encrypted pixels that need to be processed.
  2. Prune non-linear activations, such as ReLUs, in the initial layers. Since non-linear functions are the most "expensive" part of a private network, removing them leads to a 5.3x speedup on complex tasks like ImageNet.

Why It Works

The shift to the frequency domain works because it aligns the mathematical structure of the neural network with the strengths of the underlying cryptography.

  • Spatial Domain: Requires complex rotations and data movement to align filters with image patches.
  • Frequency Domain: Requires only element-wise operations.

By treating images as a collection of frequencies rather than a grid of pixels, these frameworks transform the heavy lifting of deep learning into a format that homomorphic encryption can process with minimal friction. This transition is moving private inference from a theoretical curiosity toward a practical tool for high-resolution, real-world applications.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_secure_convolution_in_the_frequency_doma_dc6bead4,
  title = {Secure Convolution in the Frequency Domain},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/secure-convolution-in-the-frequency-domain/rdr_dc6bead43b7647569a9122cd7b7042db},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_secure_convolution_in_the_frequency_doma_dc6bead4_v1,
  title = {Secure Convolution in the Frequency Domain},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/secure-convolution-in-the-frequency-domain/rdr_dc6bead43b7647569a9122cd7b7042db/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}