Construction and count of 1-resilient rotation symmetric Boolean functions. (English) Zbl 1440.94074
Summary: Finding and constructing Boolean functions with many cryptographic properties to resist a variety of existing attacks are challenging tasks in current cryptography and information security. The key idea in this paper consists of finding a general formula for computing the number of orbits with the same length and Hamming weight by utilizing prime factorization for any integer \(n\) greater than 1. Using the property of an orthogonal array to turn the construction of 1-resilient rotation symmetric Boolean functions (RSBFs) on \(n\) variables into the solution of a linear system of equations, a complete characterization and a general construction method of this class of functions are also presented. Moreover, a formula for counting the number of functions of this class is found. Not only are the structures of all 1-resilient RSBFs that are obtained more clear, such problems regarding their construction and count are completely and exhaustively solved. In addition, our methods are simpler than existing methods. We provide the exact numbers of 1-resilient RSBFs having ten and 11 variables, which are 162091449508441568747323063140 and 403305984734393392122612918710214418571734777982178890, respectively. Finally, we use three examples to illustrate the application of our methods.
Keywords:
1-resilient rotation symmetric Boolean function; orthogonal array; orbit matrix; cryptographyReferences:
| [1] | Bars, J. L.; Viola, A., Equivalence classes of boolean functions for first-order correlation, IEEE Trans. Inf. Theory, 56, 3, 1247-1261 (2010) · Zbl 1366.94778 |
| [2] | Bennett, C. H.; Brassard, G.; Robert, J. M., Privacy amplication by public discussion, SIAM J. Comput., 17, 2, 210-229 (1988) · Zbl 0644.94010 |
| [3] | Camion, P.; Carlet, C.; Charpin, P.; Sendrier, N., On correlation-immune functions, Advances in Cryptology-CRYPTO’91. Advances in Cryptology-CRYPTO’91, LNCS, vol. 576, 86-100 (1992), Springer · Zbl 0763.94006 |
| [4] | Chor, B.; Goldreich, O.; Hastad, J.; Freidmann, J., The bit extraction problem or t-resilient functions, Foundations of Computer Science Annual Symposium on, 396-407 (1985) |
| [5] | Cusick, T. W.; Li, Y.; Stǎnicǎ, P., Balanced symmetric functions over GF(p), IEEE Trans. Inf. Theory, 54, 3, 1304-1307 (2008) · Zbl 1306.94041 |
| [6] | Dalai, D.; Gupta, K.; Maitra, S., Results on algebraic immunity for cryptographically significant boolean functions, Progress in Cryptology - Indocrypt 2004, International Conference on Cryptology in India, December 20-22, 2004, Proceedings, 92-106 (2004) · Zbl 1115.94007 |
| [7] | Du, J.; Fu, S.; Qu, L.; Pang, S., New constructions of \(q\)-variable 1-resilient rotation symmetric functions over \(f_p\), Sci. China, Inf. Sci., 59, 7, 1-3 (2016) |
| [8] | Du, J.; Pang, S.; Wen, Q.; Liao, X., Construction and count of 1-resilient rotation symmetric boolean functions on \(p^r\) variables, Chin. J. Electron., 23, 4, 816-820 (2014) |
| [9] | Du, J.; Wen, Q.; Zhang, J.; Pang, S., Construction and count of resilient rotation symmetric boolean functions with prime number variables, J. Communs., 34, 3, 6-13 (2013) |
| [10] | Du, J.; Wen, Q.; Zhang, J.; Pang, S., Construction and counting of 1-resilient rotation symmetric boolean functions on pq variables, IEICE Trans. Fundamentals E96-A, 7, 1653-1656 (2013) |
| [11] | Du, J.; Wen, Q.; Zhang, J.; Pang, S., Constructions of resilient rotation symmetric boolean functions on given number of variables, IET Inf. Secur., 8, 5, 265-272 (2014) |
| [12] | Fu, S.; Li, C.; Matsuura, K.; Qu, L., Balanced 2p-variable rotation symmetric boolean functions with maximum algebraic immunity, Appl. Math. Lett., 24, 12, 2093-2096 (2011) · Zbl 1231.65014 |
| [13] | Fu, S.; Li, C.; Matsuura, K.; Qu, L., Construction of rotation symmetric boolean functions with maximum algebraic immunity, CANS’09, 402-412 (2009) · Zbl 1287.94067 |
| [14] | Fu, S.; Li, C.; Qu, L., On the number of rotation symmetric boolean functions, Sci. China, Inf. Sci., 53, 3, 537-545 (2010) · Zbl 1497.94219 |
| [15] | Gong, G.; Ronjom, S.; Helleseth, T.; Hu, H., Fast discrete fourier spectra attacks on stream ciphers, IEEE Trans. Inf. Theory, 57, 8, 5555-5565 (2011) · Zbl 1365.94379 |
| [16] | Kavut, S.; Maitra, S.; Sarkar, S.; Yücel, M. D., Enumeration of 9-variable rotation symmetric boolean functions having nonlinearity > 240, Proceedings in Cryptology-INDOCRYPT 2006. Proceedings in Cryptology-INDOCRYPT 2006, Lecture Notes in Computer Science, Vol. 4329, 266-279 (2006) · Zbl 1175.94085 |
| [17] | Kavut, S.; Yücel, M. D., 9-variable boolean functions with nonlinearity 242 in the generalized rotation symmetric class, Inf. Comput., 208, 4, 341-350 (2010) · Zbl 1183.94039 |
| [18] | Ke, P.; Huang, L.; Zhang, S., Improved lower bound on the number of balanced symmetric functions over GF(p), Inf. Sci., 179, 5, 682-687 (2009) · Zbl 1170.94012 |
| [19] | Khan, M.; Özbudak, F., Hybrid classes of balanced boolean functions with good cryptographic properties, Inf. Sci., 273, 319-328 (2014) · Zbl 1341.94014 |
| [20] | Li, X.; Zhou, Q.; Qian, H.; Yu, Y.; Tang, S., Balanced 2p-variable rotation symmetric boolean functions with optimal algebraic immunity, good nonlinearity, and good algebraic degree, J. Math. Anal. Appl., 403, 1, 63-71 (2013) · Zbl 1292.94187 |
| [21] | Liu, W.; Youssef, A., On the existence of (10,2,7,488) resilient functions, IEEE Trans. Inf. Theory, 55, 1, 411-412 (2009) · Zbl 1367.94328 |
| [22] | Pang, S.; Xu, W.; Du, J.; Wang, Y., Construction and count of 1-resilient rotation symmetric boolean functions on 4p variables, Chin. J. Electron., 26, 6, 1276-1283 (2017) |
| [23] | Pieprzyk, J.; Qu, C., Fast hashing and rotation-symmetric functions, J. UCS., 5, 1, 20-31 (1999) |
| [24] | Sarkar, S.; Maitra, S., Construction of rotation symmetric boolean functions with maximum algebraic immunity on odd number of variables, AAECC’07, 271-280 (2007) · Zbl 1193.94063 |
| [25] | Siegenthaler, T., Correlation-immunity of nonlinear combining functions for cryptographic applications (corresp.), IEEE Trans. Inf. Theory, 30, 5, 776-780 (1984) · Zbl 0554.94010 |
| [26] | Stǎnicǎ, P.; Maitra, S., Rotation symmetric boolean functions-count and cryptographic properties, Discrete Appl. Math., 156, 10, 1567-1580 (2008) · Zbl 1142.94016 |
| [27] | Stǎnicǎ, P.; Maitra, S.; Clark, J., Results on rotation symmetric bent and correlation immune boolean functions, FSE’04, 161-177 (2004) · Zbl 1079.68562 |
| [28] | Stinson, D., Resilient functions and large sets of orthogonal arrays, Congr. Numer. (1993) |
| [29] | Wen, Q.; Niu, X.; Yang, Y., The Boolean Functions in Modern Cryptology (2000), Science Press: Science Press Beijing |
| [30] | Zhang, F.; Carlet, C.; Hu, Y.; Cao, T., Secondary constructions of highly nonlinear boolean functions and disjoint spectra plateaued functions, Inf. Sci., 283, 94-106 (2014) · Zbl 1360.94340 |
| [31] | Zhang, F.; Hu, Y.; Xie, M.; Wei, Y., Constructions of 1-resilient boolean functions on odd number of variables with a high nonlinearity, Secur. Comm. Netw., 5, 6, 614-624 (2012) |
| [32] | Zhang, J.; You, Z.; Li, Z., Enumeration of binary orthogonal arrays of strength 1, Discrete Math., 239, 1-3, 191-198 (2001) · Zbl 0983.05007 |
| [33] | Zhang, P.; Fu, S.; Qu, L., Enumeration of balanced rotation-symmetric boolean functions, J. Appl. Sci. Electron. Inf. Eng., 30, 45-51 (2012) |
| [34] | Zhang, W. G.; Pasalic, E., Constructions of resilient s-boxes with strictly almost optimal nonlinearity through disjoint linear codes, IEEE Trans. Inf. Theory, 60, 3, 1638-1651 (2014) · Zbl 1360.94396 |
| [35] | Zhang, W. G.; 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 |
| [36] | Zhang, W. G.; Pasalic, E., Improving the lower bound on the maximum nonlinearity of 1-resilient boolean functions and designing functions satisfying all cryptographic criteria, Inf. Sci., 376, 21-30 (2017) · Zbl 1428.94100 |
| [37] | Zhang, W. G.; Xiao, G. Z., Constructions of almost optimal resilient boolean functions on large even number of variables, IEEE Trans. Inf. Theory, 55, 12, 5822-5831 (2009) · Zbl 1367.94478 |
| [38] | Zhang, Y.; Pang, S.; Jiao, Z.; Zhang, W., Group partition and systems of orthogonal idempotents, Linear Algebra Appl., 278, 249-262 (1998) · Zbl 0943.20008 |
| [39] | Zhang, Y.; Pang, S.; Wang, Y., Orthogonal arrays obtained by generalized hadamard product, Discrete Math., 238, 151-170 (2001) · Zbl 0981.62066 |
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.
