Random generation of Boolean functions with high degree of correlation immunity

• Autorzy: Grocholewska-Czuryło A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cryptography; ciphers; Boolean functions; correlation immunity; resilience; random generation

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2006
• Tom: nr 3
• Strony: 14--18
• Opis fizyczny: Bibliogr. 36 poz., tab.

Twórcy

autor

Grocholewska-Czuryło A.

• Institute of Control and Information Engineering, Poznań University of Technology, Marii Skłodowskiej-Curie Sq. 5, 60-965 Poznań, Poland,

Bibliografia

• [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.
• [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.
• [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.
• [4] C. Carlet, “On the coset weight divisibility and nonlinearity of resilient and correlation immune functions”, in SETA 2001, Bergen, Norway, 2001.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [12] R. Forr´e, “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.
• [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.
• [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.
• [15] J. B. Kam and G. Davida, “Structured design of substitution permutation encryption networks”, IEEE Trans. Comput., vol. C-28, pp. 747–753, 1979.
• [16] K. Kurosawa and T. Satoh, “Generalization of higher order SAC to vector output Boolean functions”, IEICE Trans., vol. E90, no. 1, 1998.
• [17] J. A. Maiorana, “A class of bent functions”, R41 Tech. Paper, 1971.
• [18] S. Maity and T. Johansson, “Construction of cryptographically important Boolean functions”, in INDOCRYPT 2002, Hyderabad, India, 2002, pp. 234–245.
• [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.
• [20] S. Maitra, “Highly nonlinear balanced Boolean functions with very good autocorrelation property”, Tech. Rep. 2000/047, Indian Statistical Institute, Calcutta, 2000.
• [21] S. Maitra, “Autocorrelation properties of correlation immune Boolean functions”, in INDOCRYPT 2001, Chennai, India, 2001, pp. 242–253.
• [22] S. Maitra and E. Pasalic, “Further constructions of resilient Boolean functions with very high nonlinearity”, in SETA 2001, Bergen, Norway, 2001.
• [23] M. Matsui, “Linear cryptanalysis method for DES cipher (abstracts)”, in EUROCRYPT 1993, Lofthus, Norway, 1993.
• [24] W. Meier and O. Staffelbach, “Nonlinearity criteria for cryptographic functions”, in Advances in Cryptology: EUROCRYPT 1989, J. J. Quisquater, J. Vandewalle, Eds., LNCS. Berlin: Springer, 1989, vol. 434, pp. 549–562.
• [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.
• [26] K. Nyberg, “Perfect nonlinear S-boxes”, in Advances of Cryptology: EUROCRYPT 1991, LNCS. Berlin: Springer, 1991, vol. 547, pp. 378–386.
• [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.
• [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.
• [29] O. S. Rothaus, “On bent functions”, J. Combin. Theory: Ser. A, vol. 20, pp. 300–305, 1976.
• [30] P. Sarkar and S. Maitra, “New directions in design of resilient Boolean functions”, Tech. Rep. ASD/2000/04, Indian Statistical Institute, 2000.
• [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.
• [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.
• [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.
• [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.
• [35] Y. Tarannikov, “On resilient Boolean functions with maximal possible nonlinearity”, Tech. Rep. 2000/005, Mech. & Math. Department, Moscow State University, 2000.
• [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.