A study of differences between bent functions constructed using Rothaus method and randomly generated bent functions

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

Abstrakty

EN

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 somealgorithms 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

Słowa kluczowe

EN

block ciphers; S-boxes; bent functions; construction; random generation; nonlinearity

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2003
• Tom: nr 4
• Strony: 19--24
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Grocholewska-Czuryło A.

• Laboratory of Information Technology Security, Poznań University of Technology,

Bibliografia

• [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.
• [2] C. E. Shannon, “Communication theory of secrecy systems”, Bell Syst. Techn. J., vol. 28, pp. 656–715, 1949.
• [3] K. Nyberg, “Perfect nonlinear S-boxes”, in Advances of Cryptology –EUROCRYPT’91, LNCS. Springer, 1991, vol. 547, pp. 378–386.
• [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.
• [5] O. S. Rothaus, “On bent functions”, J. Combinat. Theory, vol. 20, pp. 300–305, 1976.
• [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.
• [7] J. F. Dillon, “A survey of bent functions”, NSA Techn. J., special issue, pp. 191–215, 1972.
• [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.
• [9] J. A. Maiorana, “A class of bent functions”, R41, 1971.
• [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.
• [11] M. Dawson and S. E. Tavares, “An expanded set of S-box design criteria based on information theory and its relation to differentia like attacks”, in Advances in Cryptology – EUROCRYPT’91, LNCS. Springer, 1991, vol. 547, pp. 352–367.
• [12] J. B. Kam and G. Davida, “Structured design of substitution-permutation encryption networks”, IEEE Trans. Comput., vol. C-28, pp. 747–753, 1979.
• [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.
• [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.
• [15] R. Forré, “The strict avalanche criterion: spectral properties of Boolean functions with high nonlinearity”, in Advances in Cryptology – CRYPTO’88, LNCS. Springer, 1990.
• [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.
• [17] E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard. Springer, 1993.
• [18] M. Matsui, “Linear cryptanalysis method for DES cipher”, in Proc. EUROCRYPT’93 (abstracts), 1993.
• [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.
• [20] R. Yarlagadda and J. E. Hershey, “Analysis and synthesis of bent sequences”, Proc. IEE, vol. 136, pp. 112–123, 1989.
• [21] K. Nyberg, “Constructions of bent functions and difference sets”, in Advances in Cryptology – EUROCRYPT’90, LNCS. Springer, 1991, vol. 473.
• [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.
• [23] K. Chmiel, “Liniowa aproksymacja funkcji S-bloków”. Raport nr 475. Politechnika Poznańska, Katedra Automatyki, Robotyki i Informatyki, Poznań, 2000 (in Polish).
• [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).
• [25] A. Grocholewska-Czuryło and J. Stokłosa, “Generating bent functions”, in Proc. ACS 2001