Log24

Received September 29, 2019, accepted October 15, 2019,
date of publication October 24, 2019, date of current version
November 7, 2019.

Digital Object Identifier 10.1109/ACCESS.2019.2949310

A Method for Determining
the Affine Equivalence of Boolean Functions

ZIYU WANG¹ , XIAO ZENG¹ , JINZHAO WU^2,3, AND
GUOWU YANG¹

¹Big Data Research Center, School of Computer Science
and Engineering, University of Electronic Science and Technology
of China, Chengdu 611731, China

²Guangxi Key Laboratory of Hybrid Computation and
IC Design Analysis, Guangxi University for Nationalities,
Nanning 530006, China

³School of Computer and Electronic Information,
Guangxi University, Nanning 530004, China

Corresponding authors:
Jinzhao Wu (gxmdwjzh@aliyun.com) and
Guowu Yang (ygwuestc@163.com)

This work was supported in part by the National Natural Science Foundation
of China under Grant 61772006 and Grant 61572109, in part by the
State Key Laboratory of Information Security, Institute of Information Engineering, 
Chinese Academy of Sciences, Beijing, in part by the Science and Technology
Program of Guangxi  under Grant AB17129012, in part by the Science and
Technology Major Project of Guangxi under Grant AA17204096, in part by 
the Special Fund for Scientific and Technological Bases and Talents
of Guangxi under Grant 2016AD05050, and in part by the Special Fund for
Bagui Scholars of Guangxi, in part by the Open fund of State Key Laboratory 
of Information Security.

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.

INDEX TERMS  Logic synthesis, Boolean functions,
affine equivalence, matrix group, algorithm.