A Method for Determining the Affine Equivalence of Boolean Functions

Abstract

Determining the affine equivalence of Boolean functions has significant applications in circuit and cryptography. Previous methods for determining this require a large amount of computation when Boolean functions are bent functions or when the truth table is sparse. This paper presents a new method to determine the affine equivalence based on matrix algebra. By transforming Boolean function to the corresponding matrix representation, we first propose and prove the congruent standard form of Boolean function. It lays the foundation for the determination of equivalence because affine Boolean functions must have the same standard form. Then we find the generators of orthogonal matrix group and symplectic matrix group, which greatly reduce the search space. The computation complexity of our method is o(2(r2/2+n*(n-r))), where n is the number of bit operations, and r is the rank of the matrix, which is the product of Boolean-1 matrix of the test Boolean function and its transposition. The experimental results show that our method is useful when the test Boolean function is no more than 7 bits and r is greater than 2.

Keywords

• Logic synthesis
• Boolean functions
• affine equivalence
• matrix group
• algorithm