×
Cusick, Thomas W.; Lakshmy, K. V.; Sethumadhavan, M.

Affine equivalence of monomial rotation symmetric Boolean functions: a Pólya’s theorem approach. (English) Zbl 1384.94050

J. Math. Cryptol. 10, No. 3-4, 145-156 (2016).
Summary: Two Boolean functions are affine equivalent if one can be obtained from the other by applying an affine transformation to the input variables. For a long time, there have been efforts to investigate the affine equivalence of Boolean functions. Due to the complexity of the general problem, only affine equivalence under certain groups of permutations is usually considered. Boolean functions which are invariant under the action of cyclic rotation of the input variables are known as rotation symmetric (RS) Boolean functions. Due to their speed of computation and the prospect of being good cryptographic Boolean functions, this class of Boolean functions has received a lot of attention from cryptographic researchers. In this paper, we study affine equivalence for the simplest rotation symmetric Boolean functions, called MRS functions, which are generated by the cyclic permutations of a single monomial. Using Pólya’s enumeration theorem, we compute the number of equivalence classes, under certain large groups of permutations, for these MRS functions in any number \(n\) of variables. If \(n\) is prime, we obtain the number of equivalence classes under the group of all permutations of the variables.

Cited in 5 Documents

MSC:

94A60 Cryptography
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
06E30 Boolean functions

Keywords:

affine equivalence; rotation symmetry; Boolean functions; Pólya’s counting theorem
Cite Review PDF
Full Text: DOI

References:

[1] Berlekamp E. R. and Welch L. R., Weight distributions of the cosets of the \({(32,6)}\) Reed-Muller code, IEEE Trans. Inform. Theory 18 (1972), 203-207.; Berlekamp, E. R.; Welch, L. R., Weight distributions of the cosets of the \({(32,6)}\) Reed-Muller code, IEEE Trans. Inform. Theory, 18, 203-207 (1972) · Zbl 0228.94003
[2] de Bruijn N. G., Pólya’s theory of counting, Applied Combinatorial Mathematics, John Wiley and Sons, New York (1964), 144-164.; de Bruijn, N. G., Pólya’s theory of counting, Applied Combinatorial Mathematics, 144-164 (1964) · Zbl 0144.00601
[3] Carlet C., Gao G. and Liu W., A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions, J. Combin. Theory Ser. A 127 (2014), 161-175.; Carlet, C.; Gao, G.; Liu, W., A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions, J. Combin. Theory Ser. A, 127, 161-175 (2014) · Zbl 1297.05239
[4] Cusick T. W., Affine equivalence of cubic homogeneous rotation symmetric functions, Inform. Sci. 181 (2011), 5067-5083.; Cusick, T. W., Affine equivalence of cubic homogeneous rotation symmetric functions, Inform. Sci., 181, 5067-5083 (2011) · Zbl 1272.94026
[5] Cusick T. W., Permutation equivalence of cubic rotation symmetric functions, Int. J. Comput. Math. 92 (2015), 1568-1573.; Cusick, T. W., Permutation equivalence of cubic rotation symmetric functions, Int. J. Comput. Math., 92, 1568-1573 (2015) · Zbl 1372.94485
[6] Cusick T. W. and Cheon Y., Affine equivalence of quartic homogeneous rotation symmetric Boolean functions, Inform. Sci. 259 (2014), 192-211.; Cusick, T. W.; Cheon, Y., Affine equivalence of quartic homogeneous rotation symmetric Boolean functions, Inform. Sci., 259, 192-211 (2014) · Zbl 1384.94048
[7] Cusick T. W. and Stănică P., Cryptographic Boolean Functions and Applications, Elsevier Academic Press, Amsterdam, 2009.; Cusick, T. W.; Stănică, P., Cryptographic Boolean Functions and Applications (2009) · Zbl 1173.94002
[8] Cusick T. W. and Stănică P., Counting equivalence classes for monomial rotation symmetric Boolean functions with prime dimension, Cryptogr. Commun. 8 (2016), 1-15.; Cusick, T. W.; Stănică, P., Counting equivalence classes for monomial rotation symmetric Boolean functions with prime dimension, Cryptogr. Commun., 8, 1-15 (2016) · Zbl 1344.94105
[9] Gao G., Cusick T. W. and Liu W., Families of rotation symmetric functions with useful cryptographic properties, IET Inform. Secur. 8 (2014), 297-302.; Gao, G.; Cusick, T. W.; Liu, W., Families of rotation symmetric functions with useful cryptographic properties, IET Inform. Secur., 8, 297-302 (2014)
[10] Gao G., Zhang X., Liu W. and Carlet C., Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Trans. Inform. Theory 58 (2012), 4908-4913.; Gao, G.; Zhang, X.; Liu, W.; Carlet, C., Constructions of quadratic and cubic rotation symmetric bent functions, IEEE Trans. Inform. Theory, 58, 4908-4913 (2012) · Zbl 1365.94670
[11] Harary F., On the number of bi-colored graphs, Pacific J. Math. 8 (1958), 743-755.; Harary, F., On the number of bi-colored graphs, Pacific J. Math., 8, 743-755 (1958) · Zbl 0084.19402
[12] Harrison M. A., On the classification of Boolean functions by the general linear and affine groups, J. Soc. Industrial Appl. Math. 12 (1964), 285-299.; Harrison, M. A., On the classification of Boolean functions by the general linear and affine groups, J. Soc. Industrial Appl. Math., 12, 285-299 (1964) · Zbl 0134.25802
[13] Harrison M. A. and High R. G., On the cycle index of a product of permutation groups, J. Combin. Theory 4 (1968), 277-299.; Harrison, M. A.; High, R. G., On the cycle index of a product of permutation groups, J. Combin. Theory, 4, 277-299 (1968) · Zbl 0246.20002
[14] Kavut S., Results on rotation symmetric S-boxes, Inform. Sci. 201 (2012), 93-113.; Kavut, S., Results on rotation symmetric S-boxes, Inform. Sci., 201, 93-113 (2012) · Zbl 1276.94017
[15] Kim H., Park S.-M. and Hahn S.-G., On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2, Discrete Appl. Math. 157 (2009), 428-432.; Kim, H.; Park, S.-M.; Hahn, S.-G., On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2, Discrete Appl. Math., 157, 428-432 (2009) · Zbl 1157.94005
[16] Lakshmy K. V., Sethumadhavan M. and Cusick T. W., Counting rotation symmetric functions using Pólya’s theorem, Discrete Appl. Math. 169 (2014), 162-167.; Lakshmy, K. V.; Sethumadhavan, M.; Cusick, T. W., Counting rotation symmetric functions using Pólya’s theorem, Discrete Appl. Math., 169, 162-167 (2014) · Zbl 1288.05293
[17] Maiorana J. A., A classification of the cosets of the Reed-Muller code \({\mathscr{R}(1,6)} \), Math. Comp. 57 (1991), 403-414.; Maiorana, J. A., A classification of the cosets of the Reed-Muller code \({\mathscr{R}(1,6)} \), Math. Comp., 57, 403-414 (1991) · Zbl 0724.94016
[18] Miller G. A., On the holomorph of a cyclic group, Trans. Amer. Math. Soc. 4 (1903), 153-160.; Miller, G. A., On the holomorph of a cyclic group, Trans. Amer. Math. Soc., 4, 153-160 (1903) · JFM 34.0174.01
[19] Pieprzyk J. and Qu C. X., Fast hashing and rotation-symmetric functions, J. UCS 5 (1999), 20-31.; Pieprzyk, J.; Qu, C. X., Fast hashing and rotation-symmetric functions, J. UCS, 5, 20-31 (1999) · Zbl 1097.94514
[20] Pólya G., Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145-254.; Pólya, G., Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math., 68, 145-254 (1937) · JFM 63.0547.04
[21] Redfield J. H., The theory of group-reduced distributions, Amer. J. Math. 49 (1927), 433-455.; Redfield, J. H., The theory of group-reduced distributions, Amer. J. Math., 49, 433-455 (1927) · JFM 53.0106.03
[22] Rijmen V., Barreto P. and Filho D., Rotation symmetry in algebraically generated cryptographic substitution tables, Inform. Process. Lett. 106 (2008), 246-250.; Rijmen, V.; Barreto, P.; Filho, D., Rotation symmetry in algebraically generated cryptographic substitution tables, Inform. Process. Lett., 106, 246-250 (2008) · Zbl 1188.94043
[23] Stănică P., Affine equivalence of quartic monomial rotation symmetric Boolean functions in prime power dimension, Inform. Sci. 314 (2015), 212-224.; 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
[24] Wei W.-D. and Xu J.-Y., Cycle index of direct product of permutation groups and number of equivalence classes of subsets of \({\mathscr{Z}_v} \), Discrete Math. 123 (1993), 179-188.; Wei, W.-D.; Xu, J.-Y., Cycle index of direct product of permutation groups and number of equivalence classes of subsets of \({\mathscr{Z}_v} \), Discrete Math., 123, 179-188 (1993) · Zbl 0792.05029
[25] Wiedemann D. and Zieve M., Equivalence of sparse circulants: The bipartite Ádám problem, preprint 2007, .; Wiedemann, D.; Zieve, M., Equivalence of sparse circulants: The bipartite Ádám problem (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.