Lower bounds on the performance of hardware circuits computing the Möbius transform

The Möbius transform converts the truth table of a Boolean function to its algebraic normal form. It can be implemented efficiently by algorithms that operate similarly to the Fast Fourier Transform (FFT). It plays a useful role in cryptology, either to study properties of concrete Boolean functions, or in the implementation of cryptographic attacks that require building the truth table of Boolean functions given as low-degree polynomials. Because of this last application, Banik and Regazzoni presented hardware designs to implement the Möbius transform operation in TCHES, 2024(2). The proposed hardware implementations are claimed to compute the Möbius transform of n -bit Boolean functions with area-time product A T = 𝒪 ( n 2 n ) , where A is the area of the logic gates of the circuit and T is the runtime measured in clock cycles.

We study the communication complexity of the Möbius transform, using a slightly non-standard notion of “best-case” communication complexity for functions with large inputs. This directly leads to an A T 2 lower bound for hardware circuits, and using standard arguments from one-way communication complexity, to an area lower bound. We conclude that A T = Ω ( 2 1.5 n / n 1.5 ) for any circuit that computes the Möbius transform, where A is the area of the circuit including wires. Thus, a circuit implementing the Möbius transform can be asymptotically larger than the area of just its logic cells.

We also derive concrete version of these asymptotic statements, in which the constants are made explicit, based on physical properties of the circuit production process.