Detecting Affine Equivalence Of Boolean Functions And Circuit Transformation.

The article focuses on developing improved algorithms for detecting affine equivalence of Boolean functions and synthesizing affine equivalent circuits. Affine equivalence, defined by an invertible matrix and vectors over the binary field, is important in cryptography and circuit design but challenging to detect efficiently, especially for Boolean functions with sparse truth tables. The authors propose a novel method that transforms Boolean functions so their values at the orthonormal basis are all 0 or 1, significantly reducing the search space for affine transformations compared to previous approaches. Additionally, they introduce a greedy algorithm to synthesize reversible circuits representing the affine transformation matrix using CNOT gates, enabling automatic construction of affine equivalent circuits by combining reversible and classical logic gates. Experimental results demonstrate exponential reductions in complexity for sparse functions and improved circuit synthesis efficiency.