Paper 2023/948
Compact Circuits for Efficient Mobius Transform
Abstract
The Mobius transform is a linear circuit used to compute the evaluations of a Boolean function over all points on its input domain. The operation is very useful in finding the solution of a system of polynomial equations over GF(2) for obvious reasons. However the operation, although linear, needs exponential number of logic operations (around $n\cdot 2^{n1}$ bit xors) for an $n$variable Boolean function. As such, the only known hardware circuit to efficiently compute the Mobius transform requires silicon area that is exponential in $n$. For Boolean functions whose algebraic degree is bound by some parameter $d$, recursive definitions of the Mobius transform exist that requires only $O(n^{d+1})$ space in software. However converting the mathematical definition of this spaceefficient algorithm into a hardware architecture is a nontrivial task, primarily because the recursion calls notionally lead to a depthfirst search in a transition graph that requires context switches at each recursion call for which straightforward mapping to hardware is difficult. In this paper we look to overcome these very challenges in an engineering sense. We propose a space efficient sequential hardware circuit for the Mobius transform that requires only polynomial circuit area (i.e. $O(n^{d+1})$) provided the algebraic degree of the Boolean function is limited to $d$. We show how this circuit can be used as a component to efficiently solve polynomial equations of degree at most $d$ by using fast exhaustive search. We propose three different circuit architectures for this, each of which uses the Mobius transform circuit as a core component. We show that asymptotically, all the solutions of a system of $m$ polynomials in $n$ unknowns and algebraic degree $d$ over GF(2) can be found using a circuit of silicon area proportional to $m\cdot n^{d+1}$ and circuit depth proportional to $2\cdot\log_2(nd)$. In the second part of the paper we introduce a fourth hardware solver that additionally aims to achieve energy efficiency. The main idea is to reduce the solution space to a small enough value by parallel application of Mobius transform circuits over the first few equations of the system. This is done so that one can check individually whether the vectors of this reduced solution space satisfy each of the remaining equations of the system using lower power consumption. The new circuit has area also bound by $m\cdot n^{d+1}$ and has circuit depth proportional to $d\cdot \log_2 n$. We also show that further optimizations with respect to energy consumption may be obtained by using depthbound Mobius circuits that exponentially decrease run time at the cost of additional logic area and depth.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Published by the IACR in TCHES 2024
 Keywords
 Boolean FunctionsMobius transformSolution of Equation System
 Contact author(s)

subhadeep banik @ usi ch
f regazzoni @ uva nl  History
 20240112: revised
 20230616: received
 See all versions
 Short URL
 https://ia.cr/2023/948
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/948, author = {Subhadeep Banik and Francesco Regazzoni}, title = {Compact Circuits for Efficient Mobius Transform}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/948}, year = {2023}, url = {https://eprint.iacr.org/2023/948} }