Welcome to the resource topic for 2023/948
Title:
Compact Circuits for Efficient Mobius Transform
Authors: Subhadeep Banik, Francesco Regazzoni
Abstract:Möbius 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^{n-1} bit xors) for an n-variable Boolean function. As such the only known hardware circuit to efficiently compute the Möbius 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 Möbius Transform exist that requires only O(n^{d+1}) space in software. However converting the mathematical definition of this space-efficient algorithm into a hardware architecture is a non-trivial
task, primarily because the recursion calls notionally lead to a depth-first search in a transition graph that require context switches at each recursion call for which straightforward mapping in 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 Möbius 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 that 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 used the Möbius 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 physical time proportional to 2\cdot\log_2(n-d)\cdot 2^{n-d}.
ePrint: https://eprint.iacr.org/2023/948
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .