A Method for Determining the Affine Equivalence of Boolean Functions

IEEE Access

Xiao Zeng¹  Guowu Yang¹  Ziyu Wang¹  Jinzhao Wu² 

[1] Big Data Research Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China;Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Guangxi University for Nationalities, Nanning, China;

关键词: Logic synthesis;    Boolean functions;    affine equivalence;    matrix group;    algorithm;   

DOI  :  10.1109/ACCESS.2019.2949310

来源: DOAJ

【 摘 要 】

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(r^2/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.

【 授权许可】

Unknown