The Equivalence of Fast Algorithms for Convolution, Parallel FIR Filters, Polynomial Modular Multiplication, and Pointwise Multiplication in DFT/NTT Domain
For researchers in signal processing and cryptography, this paper provides a unified framework that allows transferring fast algorithms between domains, potentially reducing computational complexity in cryptosystems.
This paper establishes the equivalence between fast convolution algorithms and fast algorithms for parallel FIR filters, polynomial modular multiplication, and pointwise multiplication in DFT/NTT domains, showing that fast structures from one domain can be applied to another. This enables the reuse of well-known fast convolution solutions in signal processing and cryptosystem applications like post-quantum cryptography and homomorphic encryption.
Fast time-domain algorithms have been developed in signal processing applications to reduce the multiplication complexity. For example, fast convolution structures using Cook-Toom and Winograd algorithms are well understood. Short length fast convolutions can be iterated to obtain fast convolution structures for long lengths. In this paper, we show that well known fast convolution structures form the basis for 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 problems are important for cryptosystem applications such as post-quantum cryptography and homomorphic encryption. By establishing the equivalence of these problems, we show that a fast structure from one domain can be used to design a fast structure for another domain. This understanding is important as there are many well known solutions for fast convolution that can be used in other signal processing and cryptosystem applications.