A study of differences between bent functions constructed using Rothaus method and randomly generated bent functions
DOI:
https://doi.org/10.26636/jtit.2003.4.205Keywords:
block ciphers, S-boxes, bent functions, construction, random generation, nonlinearityAbstract
Bent functions, having the highest possible nonlinearity, are among the best candidates for construction of S-boxes. One problem with bent functions is the fact that they are hard to find among randomly generated set of Boolean functions already for 6 argument functions. There exist some algorithms that allow for easy generation of bent functions. The major drawback of these algorithms is the fact that they rely on deterministic dependencies and are only able to generate bent functions belonging to one specific class. In our paper we present an efficient generator of random bent functions of more than 4 arguments. Resulting functions are not bounded by constraints described above. The generator operates in algebraic normal form domain (ANF). We also present our result on comparing the performance of S-boxes build using our bent function generator versus a standard method of bent function construction. We also give some directions for further research.
Downloads
References
[1] L. J. O’Connor, "An analysis of a class of algorithms for S-box construction", J. Cryptol., vol. 7, no. 3, pp. 133-152, 1994.
View in Google Scholar
[2] C. E. Shannon, "Communication theory of secrecy systems", Bell Syst. Techn. J., vol. 28, pp. 656-715, 1949.
View in Google Scholar
[3] K. Nyberg, "Perfect nonlinear S-boxes", in Advances of Cryptology - EUROCRYPT’91, LNCS. Springer, 1991, vol. 547, pp. 378-386.
View in Google Scholar
[4] J. Seberry, X. M. Zhang, and Y. Zheng, "Systematic generation of cryptographically robust S-boxes", in Proc. 1st ACM Conf. Comput. Commun. Secur., 1993.
View in Google Scholar
[5] O. S. Rothaus, "On bent functions", J. Combinat. Theory, vol. 20, pp. 300-305, 1976.
View in Google Scholar
[6] B. Preneel, W. Van Leekwijck, L. Van Linden, R. Govaerts, and J. Vandewalle, "Propagation characteristics of Boolean functions", in Advances in Cryptology - EUROCRYPT’90, LNCS. Springer, 1991, vol. 473, pp. 161-173.
View in Google Scholar
[7] J. F. Dillon, "A survey of bent functions", NSA Techn. J., special issue, pp. 191-215, 1972.
View in Google Scholar
[8] 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
[9] J. A. Maiorana, "A class of bent functions", R41, 1971.
View in Google Scholar
[10] C. M. Adams, "A formal and practical design procedure for substitution permutation network cryptosystems". Ph.D. thesis, Department of Electrical Engineering, Queen’s University, 1990.
View in Google Scholar
[11] M. Dawson and S. E. Tavares, "An expanded set of S-box design criteria based on information theory and its relation to differential like attacks", in Advances in Cryptology - EUROCRYPT’91, LNCS. Springer, 1991, vol. 547, pp. 352-367.
View in Google Scholar
[12] 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
[13] L. O’Connor, "An analysis of product ciphers based on the properties of Boolean functions". Ph.D. thesis, Department of Computer Science, University of Waterloo, 1992.
View in Google Scholar
[14] A. F. Webster and S. E. Tavares, "On the design of S-boxes", in Advances in Cryptology - CRYPTO’85, LNCS. Springer, 1986, pp. 523-534.
View in Google Scholar
[15] R. Forré, "The strict avalanche criterion: spectral properties of Boolean functions with high nonlinearity", in Advances in Cryptology - CRYPTO’88, LNCS. Springer, 1990.
View in Google Scholar
[16] W. Meier and O. Staffelbach, "Nonlinearity criteria for cryptographic functions", in Advances in Cryptology - EUROCRYPT ’89, LNCS. Springer, 1990, vol. 434, pp. 549-562.
View in Google Scholar
[17] E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard. Springer, 1993.
View in Google Scholar
[18] M. Matsui, "Linear cryptanalysis method for DES cipher", in Proc. EUROCRYPT’93 (abstracts), 1993.
View in Google Scholar
[19] R. Yarlagadda and J. E. Hershey, "A note on the eigenvectors of Hadamard matrices of order 2n ", Linear Algebra & Appl., vol. 45, pp. 43-53, 1982.
View in Google Scholar
[20] R. Yarlagadda and J. E. Hershey, "Analysis and synthesis of bent sequences", Proc. IEE, vol. 136, pp. 112-123, 1989.
View in Google Scholar
[21] K. Nyberg, "Constructions of bent functions and difference sets", in Advances in Cryptology - EUROCRYPT’90, LNCS. Springer, 1991, vol. 473.
View in Google Scholar
[22] S. Mister and C. Adams, "Practical S-box design", in Workshop on Selected Areas in Cryptography (SAC ’96) Workshop Record, Queens University, 1996, pp. 61-76.
View in Google Scholar
[23] K. Chmiel, "Liniowa aproksymacja funkcji S-bloków". Raport nr 475. Politechnika Poznańska, Katedra Automatyki, Robotyki i Informatyki, Poznań, 2000 (in Polish).
View in Google Scholar
[24] R. Wicik, "Wykorzystanie szyfrów blokowych opartych o sieci podstawieniowo-przestawieniowe o dużych S-boksach w specjalnych sieciach telekomunikacyjnych". Rozprawa doktorska, Wojskowa Akademia Techniczna, Warszawa, 1999 (Ph.D. thesis in Polish).
View in Google Scholar
[25] A. Grocholewska-Czuryło and J. Stokłosa, "Generating bent functions", in Proc. ACS 2001.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2003 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
