Circulant matrices and affine equivalence of monomial rotation symmetric Boolean functions. (English) Zbl 1318.05088
Summary: The goal of this paper is two-fold. We first focus on the problem of deciding whether two monomial rotation symmetric (MRS) Boolean functions are affine equivalent via a permutation. Using a correspondence between such functions and circulant matrices, we give a simple necessary and sufficient condition. We connect this problem with the well known Ádám’s conjecture from graph theory. As applications, we reprove easily several main results of Cusick et al. on the number of equivalence classes under permutations for MRS in prime power dimensions, as well as give a count for the number of classes in \(p q\) number of variables, where \(p\), \(q\) are prime numbers with \(p < q < p^2\). Also, we find a connection between the generalized inverse of a circulant matrix and the invertibility of its generating polynomial over \(\mathbb{F}_2\), modulo a product of cyclotomic polynomials, thus generalizing a known result on nonsingular circulant matrices.
MSC:
| 05E05 | Symmetric functions and generalizations |
| 06E30 | Boolean functions |
| 05A05 | Permutations, words, matrices |
References:
| [1] | Adi, B.-I.; Greville, T. N.E., Generalized inverses, (2003), Springer-Verlag · Zbl 1026.15004 |
| [2] | Berlekamp, E. R.; Welch, L. R., Weight distribution of cosets of the \((32, 6)\) Reed-muller code, IEEE Trans. Inform. Theory, 18, 203-207, (1972) · Zbl 0228.94003 |
| [3] | Bileschi, M. L.; Cusick, T. W.; Padgett, D., Weights of Boolean cubic monomial rotation symmetric functions, Cryptography Commun., 4, 2, 105-130, (2012) · Zbl 1282.94109 |
| [4] | Bini, D.; Del Corso, G. M.; Manzini, G.; Margara, L., Inversion of circulant matrices over \(\mathbb{Z}_m\), Math. Comp., 70, 1169-1182, (2001) · Zbl 0977.65022 |
| [5] | Biryukov, A.; De Cannière, C.; Braeken, A.; Preneel, B., A toolbox for cryptanalysis: linear and affine equivalence algorithms, (Biham, E., Advances in Cryptology-Eurocrypt, LNCS, vol. 2656, (2003), Springer-Verlag), 33-50 · Zbl 1038.94521 |
| [6] | Braeken, A.; Borissov, Y.; Nikova, S.; Preneel, B., Classification of Boolean functions of 6 variables or less with respect to some cryptographic properties, (Automata, Languages and Programming, LNCS, vol. 3580, (2005), Springer Berlin), 324-334, Longer version at http://eprint.iacr.org/2004/248 · Zbl 1082.94011 |
| [7] | Brown, A.; Cusick, T. W., Equivalence classes for cubic rotation symmetric functions, Cryptogr. Commun., 5, 2, 85-118, (2013) · Zbl 1335.94112 |
| [8] | Carlet, C., Correlation-immune Boolean functions for leakage squeezing and rotating \(s\)-box masking against side channel attacks, (Security, Privacy, and Applied Cryptography Engineering, LNCS, vol. 8204, (2013)), 70-74 · Zbl 1355.94050 |
| [9] | Clark, J.; Jacob, J.; Maitra, S.; Stănică, P., Almost Boolean functions: the design of Boolean functions by spectral inversion, Comput. Intell., 20, 450-462, (2004) |
| [10] | Cusick, T. W., Affine equivalence of cubic homogeneous rotation symmetric functions, Inform. Sci., 181, 22, 5067-5083, (2011) · Zbl 1272.94026 |
| [11] | Cusick, T. W.; Brown, A., Affine equivalence for rotation symmetric Boolean functions with \(p^k\) variables, Finite Fields Appl., 18, 3, 547-562, (2012) · Zbl 1275.94026 |
| [12] | Cusick, T. W.; Cheon, Y., Affine equivalence of quartic homogeneous rotation symmetric Boolean functions, Inform. Sci., 259, 192-211, (2014) · Zbl 1384.94048 |
| [13] | Cusick, T. W.; Cheon, Y., Affine equivalence for rotation symmetric Boolean functions with \(2^k\) variables, Des. Codes Cryptogr., 63, 273-294, (2012) · Zbl 1254.06009 |
| [14] | Cusick, T. W.; Cheon, Y., Affine equivalence for cubic rotation symmetric Boolean functions with \(n = p q\) variables, Discrete Math., 327, 51-61, (2014) · Zbl 1308.94067 |
| [15] | Cusick, T. W.; Stănică, P., Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Math., 258, 289-301, (2002) · Zbl 1013.94042 |
| [16] | Dalai, D. K.; Gupta, K. C.; Maitra, S., Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity, (Gilbert, H.; Handschuh, H., Fast Software Encryption, LNCS, vol. 3557, (2005)), 98-111 · Zbl 1140.94334 |
| [17] | Dalai, D. K.; Gupta, K. C.; Maitra, S., Results on algebraic immunity for cryptographically significant Boolean functions, (Proceedings of Indocrypt 2004, LNCS, vol. 3348, (2004)), 92-106 · Zbl 1115.94007 |
| [18] | Davis, P. J., Circulant matrices, (1979), John Wiley and Sons New York · Zbl 0418.15017 |
| [19] | Filiol, E.; Fontaine, C., Highly nonlinear balanced Boolean functions with a good correlation-immunity, (Adv. in Crypt. - EUROCRYPT’98, LNCS, vol. 1403, (1998), Springer-Verlag), 475-488 · Zbl 0919.94014 |
| [20] | Fuller, J. E., Analysis of affine equivalent Boolean functions for cryptography, (2003), Information Security Research Centre, Queensland Univ. Tech, (Ph.D. thesis) |
| [21] | Fuller, J. E.; Millan, W., Linear redundancy in \(S\)-boxes, (Fast Software Encryption 2003, LNCS, vol. 2887, (2003), Springer Berlin), 74-86 · Zbl 1242.94025 |
| [22] | Harrison, M. A., On the classification of Boolean functions by the general linear and affine groups, J. Soc. Indust. Appl. Math., 285-299, (1964) · Zbl 0134.25802 |
| [23] | M. Hell, A. Maximov, S. Maitra, On efficient implementation of search strategy for rotation symmetric Boolean functions, in: Ninth International Workshop on Algebraic and Combinatoral Coding Theory, ACCT 2004, June 19-25, 2004, Black Sea Coast, Bulgaria. |
| [24] | Ingleton, A. W., The rank of circulant matrices, J. Lond. Math. Soc., s1-31, 4, 445-460, (1956) · Zbl 0072.00802 |
| [25] | Kavut, S.; Maitra, S.; Yücel, M. D., Enumeration of 9-variable rotation symmetric Boolean functions having nonlinearity >240, (Adv. in Crypt.-Indocrypt 2006, LNCS, vol. 4329, (2006), Springer Berlin), 266-279 · Zbl 1175.94085 |
| [26] | Kavut, S.; Maitra, S.; Yücel, M. D., Search for Boolean functions with excellent profiles in the rotation symmetric class, IEEE Trans. Inform. Theory, 53, 1743-1751, (2007) · Zbl 1287.94130 |
| [27] | Kavut, S.; Yücel, M. D., Generalized rotation symmetric and dihedral symmetric Boolean functions - 9 variable Boolean functions with nonlinearity 242, (Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC 2007, LNCS, vol. 4851, (2007)), 321-329 · Zbl 1195.94062 |
| [28] | Lakshmy, K. V.; Sethumadhavan, M.; Cusick, T. W., Counting rotation symmetric functions using polya’s theorem, Discrete Appl. Math., 169, 162-167, (2014) · Zbl 1288.05293 |
| [29] | Maiorana, J. A., A classification of cosets of the Reed-muller code \(R(1, 6)\), Math. Comp., 57, 403-414, (1991) · Zbl 0724.94016 |
| [30] | Maximov, A., Classes of plateaued rotation symmetric Boolean functions under transformation of Walsh spectra, (Ytrehus, O., Workshop on Coding and Cryptology 2005, LNCS, vol. 3969, (2006)), 325-334 |
| [31] | Maximov, A.; Hell, M.; Maitra, S., Plateaued rotation symmetric Boolean functions on odd number of variables, (International Workshop on Boolean Functions: Cryptography and Applications, BFCA 2005, (2005), University of Rouen France), available at eprint.iacr.org no. 2004/144, 2004 |
| [32] | Muzychuk, M., On ádám’s conjecture for circulant graphs, Discrete Math., 176, 1-3, 285-298, (1997) · Zbl 0885.05090 |
| [33] | Patterson, N. J.; Wiedemann, D. H., The covering radius of the \((2^{15}, 16)\) Reed-muller code is at least 16276, IEEE Trans. Inform. Theory, IEEE Trans. Inform. Theory, 36, 443-356, (1990), See also the correction in · Zbl 0505.94021 |
| [34] | Pearl, M. H., Generalized inverses of matrices with entries taken from an arbitrary field, Linear Algebra Appl., 1, 571-587, (1968) · Zbl 0186.33602 |
| [35] | Pieprzyk, J.; Qu, C. X., Fast hashing and rotation-symmetric functions, J. UCS, 5, 20-31, (1999) |
| [36] | Rijmen, V.; Barreto, P. S.L. M.; Filho, D. L.G., Rotation symmetry in algebraically generated cryptographic substitution tables, Inform. Process. Lett., 106, 246-250, (2008) · Zbl 1188.94043 |
| [37] | Stănică, P.; Maitra, S., Rotation symmetric Boolean functions-count and cryptographic properties, Discrete Appl. Math., 156, 1567-1580, (2008) · Zbl 1142.94016 |
| [38] | Stănică, P.; Maitra, S.; Clark, J., Results on rotation symmetric bent and correlation immune Boolean functions, (Fast Software Encryption Workshop, FSE 2004, LNCS, vol. 3017, (2004), Springer Verlag New Delhi, India), 161-177 · Zbl 1079.68562 |
| [39] | Wang, J.-Q.; Dong, C.-Z., Inverse matrix of symmetric circulant matrix on skew field, Int. J. Algebra, 1, 11, 541-546, (2007) · Zbl 1141.05312 |
| [40] | Wiedemann, D.; Zieve, M. E., Equivalence of sparse circulants: the bipartite ádám problem, (IACR Cryptology ePrint Archive, (2007)) |
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.
