Random generation of Boolean functions with high degree of correlation immunity
DOI:
https://doi.org/10.26636/jtit.2006.3.384Keywords:
cryptography, ciphers, Boolean functions, correlation immunity, reslilience, random generationAbstract
In recent years a cryptographic community is paying a lot of attention to the constructions of so called resilient functions for use mainly in stream cipher systems. Very little work however has been devoted to random generation of such functions. This paper tries to fill that gap and presents an algorithm that can generate at random highly nonlinear resilient functions. Generated functions are analyzed and compared to the results obtained from the best know constructions and some upper bounds on nonlinearity and resiliency. It is shown that randomly generated functions achieve in most cases results equal to the best known designs, while in other cases fall just behind such constructs. It is argued that the algorithm can perhaps be used to prove the existence of some resilient functions for which no mathematical prove has been given so far.
Downloads
References
[1] C. M. Adams and S. E. Tavares, "Generating and counting binary bent sequences", IEEE Trans. Inform. Theory, vol. IT-36, pp. 1170-1173, 1990.
View in Google Scholar
[2] P. Camion, C. Carlet, P. Charpin, and N. Sendrier, "On correlation immune functions", in Adv. Crypt. CRYPTO 1991, Santa Barbara, USA, 1991, pp. 86-100.
View in Google Scholar
[3] C. Carlet, "More correlation immune and resilient functions over Galois fields and Galois rings", in Adv. Crypt. EUROCRYPT 1997, Konstanz, Germany, 1997, pp. 422-433.
View in Google Scholar
[4] C. Carlet, "On the coset weight divisibility and nonlinearity of resilient and correlation immune functions", in SETA 2001, Bergen, Norway, 2001.
View in Google Scholar
[5] S. Chee, S. Lee, D. Lee, and S. H. Sung, "On the correlation immune functions and their nonlinearity", in Advances in Cryptology ASIACRYPT 1996, LNCS. Berlin: Springer, 1996, vol. 1163, pp. 232-243.
View in Google Scholar
[6] J. A. Clark and J. L. Jacob, "Two stage optimisation in the design of Boolean functions", in 5th Australasian Conference on Information Security and Privacy, ACISP 2000, E. Dawson, A. Clark, and C. Boyd, Eds., LNCS. Berlin: Springer, 2000, vol. 1841, pp. 242-254.
View in Google Scholar
[7] J. A. Clark, J. L. Jacob, and S. Stepney, "The design of S-boxes by simulated annealing", in Int. Conf. Evol. Comput. CEC 2004, Portland, USA, 2004.
View in Google Scholar
[8] J. A. Clark, J. L. Jacob, and S. Stepney, "Secret agents leave big footprints: how to plant a cryptographic trapdoor, and why you might not get away with it", in Genetic and Evolutionary Computation Conference GECCO 2003, LNCS. Berlin: Springer, 2003, vol. 2724, pp. 2022-2033.
View in Google Scholar
[9] J. A. Clark, J. L. Jacob, and S. Stepney, "Functions satisfying multiple criteria", in Progress in Cryptology INDOCRYPT 2002, LNCS. Berlin: Springer, 2002, vol. 2551, pp. 246-259.
View in Google Scholar
[10] J. A. Clark, J. L. Jacob, and S. Stepney, "Searching for cost functions", in Int. Conf. Evol. Comput. CEC 2004, Portland, USA, 2004, pp. 1517-1524.
View in Google Scholar
[11] H. Dobbertin, "Construction of bent functions and balanced functions with high nonlinearity", in Fast Software Encryption, 1994 Leuven Workshop, LNCS. Berlin: Springer, 1994, vol. 1008, pp. 61-74.
View in Google Scholar
[12] R. Forre, "The strict avalanche criterion: spectral properties of Boolean functions with high nonlinearity", in Advances in Cryptology: CRYPTO 1988, LNCS. Berlin: Springer, 1990, vol. 403, pp. 450-468.
View in Google Scholar
[13] X. Guo-Zhen and J. Massey, "A spectral characterization of correlation immune combining functions", IEEE Trans. Inform. Theory, vol. 34, no. 3, pp. 569-571, 1988.
View in Google Scholar
[14] X. D. Hou, "On the norm and covering radius of first-order Reed-Muller codes", IEEE Trans. Inform. Theory, vol. 43, no. 3, pp. 1025-1027, 1997.
View in Google Scholar
[15] J. B. Kam and G. Davida, "Structured design of substitution-permutation encryption networks", IEEE Trans. Comput., vol. C-28, pp. 747-753, 1979.
View in Google Scholar
[16] K. Kurosawa and T. Satoh, "Generalization of higher order SAC to vector output Boolean functions", IEICE Trans., vol. E90, no. 1, 1998.
View in Google Scholar
[17] J. A. Maiorana, "A class of bent functions", R41 Tech. Paper, 1971.
View in Google Scholar
[18] S. Maity and T. Johansson, "Construction of cryptographically important Boolean functions", in INDOCRYPT 2002, Hyderabad, India, 2002, pp. 234-245.
View in Google Scholar
[19] S. Maity and S. Maitra, "Minimum distance between bent and 1-resilient Boolean functions", in FSE 2004, New Delhi, India, 2004, pp. 143-160.
View in Google Scholar
[20] S. Maitra, "Highly nonlinear balanced Boolean functions with very good autocorrelation property", Tech. Rep. 2000/047, Indian Statistical Institute, Calcutta, 2000.
View in Google Scholar
[21] S. Maitra, "Autocorrelation properties of correlation immune Boolean functions", in INDOCRYPT 2001, Chennai, India, 2001, pp. 242-253.
View in Google Scholar
[22] S. Maitra and E. Pasalic, "Further constructions of resilient Boolean functions with very high nonlinearity", in SETA 2001, Bergen, Norway, 2001.
View in Google Scholar
[23] M. Matsui, "Linear cryptanalysis method for DES cipher (abstracts)", in EUROCRYPT 1993, Lofthus, Norway, 1993.
View in Google Scholar
[24] W. Meier and O. Staffelbach, "Nonlinearity criteria for cryptographic functions", in Advances in Cryptology: EUROCRYPT 1989, J. J. Quisquater and J. Vandewalle, Eds., LNCS. Berlin: Springer, 1989, vol. 434, pp. 549-562.
View in Google Scholar
[25] W. Millan, A. Clark, and E. Dawson, "Heuristic design of cryptographically strong balanced Boolean functions", in Advances in Cryptology: EUROCRYPT 1998, LNCS. Berlin: Springer, 1998, vol. 1403, pp. 489-499.
View in Google Scholar
[26] K. Nyberg, "Perfect nonlinear S-boxes", in Advances of Cryptology: EUROCRYPT 1991, LNCS. Berlin: Springer, 1991, vol. 547, pp. 378-386.
View in Google Scholar
[27] E. Pasalic, S. Maitra, T. Johansson, and P. Sarkar, "New constructions of resilient and correlation immune Boolean functions achieving upper bound on nonlinearity", in Workshop on Coding Theory, Electronic Notes in Discrete Mathematics, Elsevier, 2001.
View in Google Scholar
[28] B. Preneel, W. Van Leekwijck, L. Van Linden, R. Govaerts, and J. Vandewalle, "Propagation characteristics of Boolean functions", in Advances in Cryptology: EUROCRYPT 1990, LNCS. Berlin: Springer, 1991, vol. 473, pp. 161-173.
View in Google Scholar
[29] O. S. Rothaus, "On bent functions", J. Combin. Theory: Ser. A, vol. 20, pp. 300-305, 1976.
View in Google Scholar
[30] P. Sarkar and S. Maitra, "New directions in design of resilient Boolean functions", Tech. Rep. ASD/2000/04, Indian Statistical Institute, 2000.
View in Google Scholar
[31] J. Seberry, X. M. Zhang, and Y. Zheng, "On constructions and nonlinearity of correlation immune Boolean functions", in Advances in Cryptology: EUROCRYPT 1993, Lofthus, Norway, 1994, pp. 181-199.
View in Google Scholar
[32] T. Siegenthaler, "Correlation-immunity of nonlinear combining functions for cryptographic applications", IEEE Trans. Inform. Theory, vol. IT-30, no. 5, pp. 776-780, 1984.
View in Google Scholar
[33] J. J. Son, J. I. Lim, S. Chee, and S. H. Sung, "Global avalanche characteristics and nonlinearity of balanced Boolean functions", Inform. Proces. Lett., vol. 65, no. 3, pp. 139-144, 1998.
View in Google Scholar
[34] S. H. Sung, S. Chee, and C. Park, "Global avalanche characteristics and propagation criterion of balanced Boolean functions", Inform. Proces. Lett., vol. 69, no. 1, pp. 21-24, 1999.
View in Google Scholar
[35] Y. Tarannikov, "On resilient Boolean functions with maximal possible nonlinearity", Tech. Rep. 2000/005, Mech. & Math. Department, Moscow State University, 2000.
View in Google Scholar
[36] X. M. Zhang and Y. Zheng, "GAC - the criterion for global avalanche characteristics of cryptographic functions", J. Univ. Comput. Sci., vol. 1, no. 5, pp. 316-333, 1995.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2006 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
