×

Computing the number of affine equivalent classes on \(\mathcal{R}(s,n)/\mathcal{R}(k,n)\). (English) Zbl 1497.94226

Summary: Affine equivalent classes of Boolean functions have many applications in modern cryptography and circuit design. Previous publications have shown that affine equivalence on the entire space of Boolean functions can be computed up to 10 variables, but not on the quotient Boolean function space modulo functions of different degrees. Computing the number of equivalent classes of cosets of Reed-Muller code \(\mathcal{R}(1,n)\) is equivalent to classifying Boolean functions modulo linear functions, which can be computed only when \(n\leq 7\). Based on the linear representation of the affine group \(\mathcal{AGL}(n,2)\) on the quotient space \(\mathcal{R}(s,n)/\mathcal{R}(k,n)\), we obtain a useful counting formula to compute the number of equivalent classes. Instead of computing the conjugacy classes and representatives directly in \(\mathcal{AGL}(n,2)\), we reduce the computation complexity by introducing an isomorphic permutation group \(P_n\) and performing the computation in \(P_n \). With the proposed algorithm, the number of equivalent classes of cosets of \(R(1,n)\) can be computed up to 10 variables. Furthermore, the number of equivalent classes on \(\mathcal{R}(s,n)/\mathcal{R}(k,n)\) can also be computed when \(-1\leq k<s\leq n\leq 10\), which is a major improvement and advancement comparing to previous methods.

MSC:

94D10 Boolean functions
20G05 Representation theory for linear algebraic groups
68W30 Symbolic computation and algebraic computation

Software:

GAP

References:

[1] Stone, HS; Jackson, CL, Structures of the affine families of switching functions, IEEE Trans. Comput., 100, 3, 251-257 (1969) · Zbl 0176.28203 · doi:10.1109/T-C.1969.222638
[2] Maiorana, JA, A classification of the cosets of the Reed-Muller code R(1, 6), Math. Comput., 57, 195, 403-414 (1991) · Zbl 0724.94016
[3] Tsai, CC; Marek-Sadowska, M., Boolean functions classification via fixed polarity Reed-Muller forms, IEEE Trans. Comput., 46, 2, 173-186 (1997) · doi:10.1109/12.565592
[4] Kasami, T.; Tokura, N., On the weight structure of Reed-Muller codes, IEEE Trans. Inf. Theory, 16, 6, 752-759 (1970) · Zbl 0205.20604 · doi:10.1109/TIT.1970.1054545
[5] Dautovic, S.; Novak, L., A comment on“ Boolean functions classification via fixed polarity Reed-Muller form”, IEEE Trans. Comput., 55, 8, 1067-1069 (2006) · doi:10.1109/TC.2006.114
[6] Hou, XD, Classification of cosets of the Reed-Muller code R (m-3, m), Discret. Math., 128, 1, 203-224 (1994) · Zbl 0792.94007 · doi:10.1016/0012-365X(94)90113-9
[7] Hou, XD, AGL (M, 2) acting on R (r, m)/R (s, m), J. Algeb., 171, 3, 921-938 (1995) · Zbl 0824.94021 · doi:10.1006/jabr.1995.1043
[8] Braeken, A., Borissov, Y., Nikova, S., Preneel, B.: Classification of Boolean functions of 6 variables or less with respect to some cryptographic properties. In: International colloquium on automata, languages, and programming, vol. 3580, pp 324-334 (2005) · Zbl 1082.94011
[9] Biryukov, A., De Canniere, C., Braeken, A., Preneel, B.: A toolbox for cryptanalysis: Linear and affine equivalence algorithms. In: International conference on the theory and applications of cryptographic techniques, pp 33-50 (2003) · Zbl 1038.94521
[10] Canteaut, A., Roué, J.: On the behaviors of affine equivalent sboxes regarding differential and linear attacks. In: Annual international conference on the theory and applications of cryptographic techniques, pp 45-74 (2015) · Zbl 1365.94411
[11] Cui, L.; Cao, Y., A new S-box structure named Affine-Power-Affine, Int. J. Innov. Comput. Inf. Control., 3, 3, 751-759 (2007)
[12] Zhang, Y.; Yang, G.; Hung, WN; Zhang, J., Computing affine equivalence classes of Boolean functions by group isomorphism, IEEE Trans. Comput., 65, 12, 3606-3616 (2016) · Zbl 1360.94485 · doi:10.1109/TC.2016.2557329
[13] Colte, P.; Kranakis, E., Boolean functions, invariance groups, and parallel complexity, SIAM J. Comput., 20, 3, 553-590 (1991) · Zbl 0734.68038 · doi:10.1137/0220036
[14] Preneel, B.: Analysis and design of cryptographic hash functions. PhD diss., Katholieke Universiteit te Leuven (1993)
[15] Carlet, C., On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean functions, with developments on symmetric functions, IEEE Trans Inf Theory, 50, 9, 2178-2185 (2004) · Zbl 1192.94090 · doi:10.1109/TIT.2004.833361
[16] Hodžić, S.; Pasalic, E.; Wei, Y.; Zhang, F., Designing plateaued boolean functions in spectral domain and their classification, IEEE Trans. Inf. Theory, 65, 9, 5865-5879 (2019) · Zbl 1432.94227 · doi:10.1109/TIT.2019.2909910
[17] Zhang, F.; Wei, Y.; Pasalic, E.; Xia, S., Large sets of disjoint spectra plateaued functions inequivalent to partially linear functions, IEEE Trans. Inf. Theory, 64, 4, 2987-2999 (2018) · Zbl 1392.94970 · doi:10.1109/TIT.2018.2795608
[18] Zhang, WG; Pasalic, E., Generalized Maiorana-McFarland construction of resilient Boolean functions with high nonlinearity and good algebraic properties, IEEE Trans. Inf. Theory, 60, 10, 6681-6695 (2014) · Zbl 1360.94484 · doi:10.1109/TIT.2014.2345772
[19] Luccio, F.; Pagli, L., On a new Boolean function with applications, IEEE Trans. Comput., 48, 3, 296-310 (1999) · Zbl 1391.94917 · doi:10.1109/12.754996
[20] Berlekamp, E.; Welch, L., Weight distributions of the cosets of the (32, 6) Reed-Muller code, IEEE Trans. Inf. Theory, 18, 1, 203-207 (1972) · Zbl 0228.94003 · doi:10.1109/TIT.1972.1054732
[21] Wegener, I., The complexity of boolean functions (1987), Hoboken: Wiley, Hoboken · Zbl 0623.94018
[22] MacWilliams, FJ; Sloane, NJA, The theory of error-correcting codes, vol. 16 (1977), Amsterdam: Elsevier, Amsterdam · Zbl 0369.94008
[23] Gao, G.; Zhang, X.; Liu, W.; Carlet, C., Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Trans. Inf. Theory, 58, 7, 4908-4913 (2012) · Zbl 1365.94670 · doi:10.1109/TIT.2012.2193377
[24] Canright, D.; Chung, JH; Stănică, P., Circulant matrices and affine equivalence of monomial rotation symmetric Boolean functions, Discret. Math., 338, 12, 2197-2211 (2015) · Zbl 1318.05088 · doi:10.1016/j.disc.2015.05.017
[25] Cusick, TW; Lakshmy, KV; Sethumadhavan, M., Affine equivalence of monomial rotation symmetric Boolean functions: A pólya’s theorem approach, J. Math. Crypt., 10, 145-156 (2016) · Zbl 1384.94050
[26] Stănică, P., Affine equivalence of quartic monomial rotation symmetric Boolean functions in prime power dimension, Inform. Sci., 314, 212-224 (2015) · Zbl 1387.06011 · doi:10.1016/j.ins.2015.03.071
[27] Hulpke, A., Conjugacy classes in finite permutation groups via homomorphic images, Math. Comput., 69, 232, 1633-1651 (2000) · Zbl 0962.20001 · doi:10.1090/S0025-5718-99-01157-6
[28] GAP - Groups, Algorithms, Program., Version 4.10.2, The GAP Group, 2019. [Online]. Available: http://www.gap-system.org
[29] Yu, Y.; Feng, JE; Pan, J.; Cheng, D., Block decoupling of Boolean control networks, IEEE Trans. Autom. Control, 64, 4, 3129-3140 (2018) · Zbl 1482.93027
[30] Yu, Y.; Wang, B.; Feng, JE, Input observability of Boolean control networks, Neurocomputing, 333, 22-28 (2019) · doi:10.1016/j.neucom.2018.12.014
[31] Zhang, J.; Yang, G.; Hung, WN; Liu, T.; Song, X.; Perkowski, MA, A group algebraic approach to NPN classification of Boolean functions, Theory Comput. Sys., 63, 6, 1278-1297 (2019) · Zbl 1462.94074 · doi:10.1007/s00224-018-9903-0
[32] Artin, M., Algebra (2011), Upper Saddle River: Pearson Prentice Hall, Upper Saddle River · Zbl 0788.00001
[33] Zeng, X., Yang, G.: Computing the number of equivalent classes on R(s,n)/R(k,n). arXiv:https://arxiv.org/abs/1912.11189
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.