Fast Algorithms Equate Convolution, FIR Filters, Polynomial Multiplication, and Pointwise Multiplication in DFT/NTT Domains

The challenge of reducing computational complexity in signal processing and cryptography drives ongoing research into faster algorithms, and a new study demonstrates a surprising equivalence between several key computational problems. Keshab K. Parhi from the University of Minnesota and colleagues reveal that fast algorithms developed for convolution, a fundamental operation in signal processing, also underpin efficient solutions for parallel finite impulse response (FIR) filters, polynomial modular multiplication, and pointwise multiplication within the discrete Fourier transform and number theoretic transform domains. This research establishes that a fast structure designed for one of these areas can be readily adapted for use in others, significantly broadening the applicability of existing fast convolution techniques. The findings are particularly important for advancing cryptosystems, including post-quantum and homomorphic encryption, where efficient polynomial modular multiplication is critical, and offer a powerful new perspective on algorithm design across diverse fields.

The Bloom and Winograd algorithms are well understood, and short length fast convolutions can be iterated to obtain fast convolution structures for long lengths. This paper demonstrates that well-known fast convolution structures form the basis for the design of fast algorithms in four other problem domains: fast parallel filters, fast polynomial modular multiplication, and fast pointwise multiplication in the DFT and NTT domains. Fast polynomial modular multiplication and fast pointwise multiplication are important problems for cryptosystem applications, such as post-quantum cryptography and homomorphic encryption. By establishing the equivalence of these problems, the research shows that a fast structure from one domain can be applied to others, offering potential performance improvements across a range of computational tasks.

Fast Structures Across Signal and Cryptographic Domains

Scientists have revealed fundamental connections between algorithms used in signal processing and cryptography, demonstrating that fast convolution structures underpin efficient solutions for parallel filtering, polynomial modular multiplication, and pointwise multiplication in the Discrete Fourier Transform (DFT) and Number Theoretic Transform (NTT) domains. The research establishes that algorithms developed in one area can be adapted and reused in others, reducing redundant development and accelerating progress. This finding has significant implications for a range of applications, from high-speed signal processing to secure cryptographic systems. The team’s work builds upon existing fast algorithms, recognizing that many rely on decomposing a complex problem into smaller, more manageable subproblems and exploiting inherent symmetries.

They focused on five key domains, demonstrating shared structural similarities between them. Fast convolution algorithms, fundamental in signal processing, serve as a foundation for developing efficient solutions in the other areas. Fast FIR filtering, crucial for designing effective digital filters, benefits from techniques like polyphase decomposition and fast convolution. Polynomial modular multiplication, essential for modern cryptography, particularly post-quantum schemes, gains efficiency through parallel processing and decomposition. Pointwise multiplication in the DFT and NTT domains, used in frequency-domain analysis and modular arithmetic, also benefits from these shared principles.

The research highlights the importance of polyphase decomposition, a technique used in both FIR filtering and DFT/NTT-based algorithms, which breaks down a sequence into even and odd components, enabling parallel processing. Iterated short convolution, the idea of breaking down a long convolution into a series of shorter convolutions, further enhances efficiency. The team demonstrates that these domains share a common pattern: decomposition into even and odd components, parallel processing of these components, and combination of the results. By increasing the level of parallelism, such as moving from 2-parallel to 4-parallel structures, performance can be further improved.

The close relationship between FIR filtering and polynomial modular multiplication is particularly noteworthy, as algorithms developed for one domain can be readily adapted to the other. Similarly, the DFT and NTT are closely related, allowing algorithms developed for one domain to be applied to the other with minor modifications. The team’s analysis includes a detailed examination of the number of multiplications and additions required for different algorithms and structures, revealing trade-offs between performance, area, and power consumption. This work has direct applications in post-quantum cryptography, where efficient polynomial modular multiplication is crucial for schemes like CRYSTALS-Kyber, and in homomorphic encryption, where secure computation on encrypted data is paramount.

The team also envisions applications in high-speed signal processing, where parallel structures can achieve high sample rates. In conclusion, the research demonstrates that the fast structures for these five domains share underlying similarities, enabling algorithm reuse and reducing development time. The team’s findings provide a valuable framework for algorithm design and optimization across a range of signal processing and cryptographic applications, paving the way for more efficient and secure systems.

Fast Convolution Equivalence Across Signal Domains

Scientists have developed a suite of fast algorithms applicable to diverse signal processing and cryptosystem applications, demonstrating equivalence between fast convolution structures and algorithms for parallel filtering, polynomial modular multiplication, and pointwise multiplication in the Discrete Fourier Transform (DFT) and Number Theoretic Transform (NTT) domains. The research establishes that a fast algorithm originating in one domain can be adapted to efficiently solve problems in another, leveraging existing fast convolution techniques. This finding has the potential to significantly improve performance across a range of computational tasks. The team’s work demonstrates that a traditional 2-by-2 convolution, requiring four multiplications, can be performed with only three multiplications using a fast structure.

This fast 2-by-2 convolution serves as a building block, enabling the construction of a fast 4-by-4 convolution structure. Further analysis reveals that a delay element within a fast parallel filter can be directly replaced by multiplication by a factor in polynomial modular multiplication, or by multiplication with a specific DFT/NTT sequence, confirming the interconnectedness of these algorithms. The team’s work extends to fast parallel Finite Impulse Response (FIR) filtering, showing that an N-tap FIR filter can be decomposed into even and odd subfilters, processed in parallel to reduce computational complexity. Specifically, a 2-parallel FIR filter requires fewer multiplications than a traditional implementation.

This principle extends to L-parallel filters, where the addition of delayed outputs further optimizes performance. Measurements confirm that a 2-parallel fast polynomial modular multiplication, crucial for post- and homomorphic encryption, can be efficiently implemented using a structure analogous to the fast convolution and parallel filter. This research delivers a powerful toolkit for optimizing algorithms across a range of applications, leveraging the fundamental principles of fast convolution to achieve significant performance gains.

Unified Algorithms For Transform Computations

This research demonstrates fundamental connections between several computational problems, specifically convolution, fast parallel filters, polynomial modular multiplication, and pointwise multiplication within the discrete Fourier and number-theoretic transforms. The team established that these seemingly disparate areas share underlying structural similarities, allowing algorithms developed for one domain to be effectively adapted for use in others. This finding is significant because it eliminates the need for independent algorithm development in each area, potentially accelerating progress and reducing redundancy. The work has particular relevance for modern cryptography, as fast polynomial modular multiplication is crucial for post-quantum and homomorphic encryption schemes.

By leveraging existing fast convolution structures, the researchers designed low-complexity solutions for polynomial modular multiplication, with specific application to the CRYSTALS-Kyber key-encapsulation mechanism. The authors acknowledge that further work could explore higher-level parallelism based on fast parallel filters, potentially leading to even more efficient implementations. This research provides a valuable framework for algorithm design and optimization across a range of signal processing and cryptographic applications.