We present a method to iteratively construct new bent functions of variables from a bent function of variables and its cyclic shift permutations using minterms of variables and minterms of 2 variables. In addition, we provide the number of bent functions of variables that we can obtain by applying the method here presented, and finally we compare this method with a previous one introduced by us in 2008 and with the Rothaus and Maiorana-McFarland constructions. 1. Introduction Boolean functions are widely used in different types of cryptographic applications, such as block ciphers, stream ciphers, and hash functions [1–3], and in coding theory [4, 5], among others. For example, the implementation of an S-box needs nonlinear Boolean functions to resist attacks such as the linear and differential cryptanalysis [6–9]. For an even number of variables, Boolean functions bearing maximum nonlinearity are called bent functions [10, 11]. The construction of one-to-one S-boxes so that any linear combination of the output functions is balanced has already been explained [12, 13] and also the issue of making such linear combination a bent function [14]. However, no conclusive approaches have been presented yet for the construction of all S-boxes so that they satisfy the property that any linear combination of the outputs is also bent. It is precisely for this reason that a thorough study of the properties of bent functions as well as of the methods to construct them has occupied the minds of many authors in the last decades (see, e.g., [9, 11, 15–35] and the references therein). Bent functions constitute a fascinating issue in cryptography but, unfortunately, there is a mist hovering over their properties, their classification, and their actual number. The origin of the concept of bent function takes us back to a theoretical article by McFarland [36] where he discussed difference sets in finite noncyclic groups. Dillon [24], a year later, systematized and further elaborated McFarland’s insights and provided proofs for a great number of properties; Dillon’s Ph.D. dissertation has been an excellent source in the field of bent functions up to the mid s. But it was Rothaus [37] who came up with the name for the concept. These functions are called perfect nonlinear Boolean functions by Meier and Staffelbach [30]. There are different ways to obtain bent functions; most of them are based on the algebraic normal form of a Boolean function and the Walsh transform. However, there are very few constructions of bent functions based on the truth table of Boolean functions, for
References
[1]
A. Braeken, V. Nikov, S. Nikova, and B. Preneel, “On Boolean functions with generalized cryptographic properties,” in Progress in Cryptology—INDOCRYPT 2004, A. Canteaut and K. Viswanathan, Eds., vol. 3348 of Lecture Notes in Computer Science, pp. 120–135, Springer, Berlin, Germany, 2004.
[2]
C. Carlet and Y. Tarannikov, “Covering sequences of Boolean functions and their cryptographic significance,” Designs, Codes and Cryptography, vol. 25, no. 3, pp. 263–279, 2002.
[3]
K. Kurosawa and R. Matsumoto, “Almost security of cryptographic boolean functions,” IEEE Transactions on Information Theory, vol. 50, no. 11, pp. 2752–2761, 2004.
[4]
Y. Borissov, A. Braeken, S. Nikova, and B. Preneel, “On the covering radii of binary Reed-Muller codes in the set of resilient boolean functions,” IEEE Transactions on Information Theory, vol. 51, no. 3, pp. 1182–1189, 2005.
[5]
K. Kurosawa, T. Iwata, and T. Yoshiwara, “New covering radius of Reed-Muller codes for t-resilient functions,” IEEE Transactions on Information Theory, vol. 50, no. 3, pp. 468–475, 2004.
[6]
C. M. Adams, “Constructing symmetric ciphers using the CAST design procedure,” Designs, Codes, and Cryptography, vol. 12, no. 3, pp. 283–316, 1997.
[7]
K. C. Gupta and P. Sarkar, “Improved construction of nonlinear resilient S-boxes,” IEEE Transactions on Information Theory, vol. 51, no. 1, pp. 339–348, 2005.
[8]
M. Matsui, “Linear cryptanalysis method for DES cipher,” in Advances in Cryptology—EUROCRYPT '93, T. Helleseth, Ed., vol. 765 of Lecture Notes in Computer Science, pp. 386–397, Springer, Berlin, Germany, 1994.
[9]
K. Nyberg, “Perfect nonlinear S-boxes,” in Advances in Cryptology—EUROCRYPT '91, D. W. Davies, Ed., vol. 547 of Lecture Notes in Computer Science, pp. 378–386, Springer, Berlin, Germany, 1991.
[10]
P. Sarkar and S. Maitra, “Construction of nonlinear Boolean functions with important cryptographic properties,” in Advances in Cryptology—EUROCRYPT 2000, B. Preneel, Ed., vol. 1807 of Lecture Notes in Computer Science, pp. 485–506, Springer, Berlin, Germany, 2000.
[11]
J. Seberry, X.-M. Zhang, and Y. L. Zheng, “Nonlinearity and propagation characteristics of balanced Boolean functions,” Information and Computation, vol. 119, no. 1, pp. 1–13, 1995.
[12]
W. Millan, “How to improve the nonlinearity of bijective S-boxes,” in Information Security and Privacy, C. Boyd and E. Dawson, Eds., vol. 1438 of Lecture Notes in Computer Science, pp. 181–192, Springer, Berlin, Germany, 1998.
[13]
W. Millan, L. Burnet, G. Carter, A. Clark, and E. Dawson, “Evolutionary heuristics for finding cryptographically strong S-boxes,” in Information and Communication Security, V. Varadharajan and Y. Mu, Eds., vol. 1726 of Lecture Notes in Computer Science, pp. 263–274, Springer, Berlin, Germany, 1999.
[14]
J. Detombe and S. Tavares, “Constructing large cryptographically strong S-boxes,” in Advances in Cryptology—AUSCRYPT '92, J. Seberry and Y. Zheng, Eds., vol. 718 of Lecture Notes in Computer Science, pp. 165–181, Springer, Berlin, Germany, 1993.
[15]
C. Carlet, “Two new classes of bent functions,” in Advances in Cryptology—EUROCRYPT '93, T. Helleseth, Ed., vol. 765 of Lecture Notes in Computer Science, pp. 77–101, Springer, Berlin, Germany, 1994.
[16]
C. Carlet, “On the secondary constructions of resilient and bent functions,” in Coding, Cryptography and Combinatorics, vol. 23 of Progress in Computer Science and Applied Logic, pp. 3–28, Birkh？user, Basel, Switzerland, 2004.
[17]
C. Carlet, “On bent and highly nonlinear balanced/resilient functions and their algebraic immunities,” in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, M. Fossorier, H. Imai, S. Lin, and A. Poli, Eds., vol. 3857 of Lecture Notes in Computer Science, pp. 1–28, Springer, Berlin, Germany, 2006.
[18]
C. Carlet, “Boolean functions for cryptography and error-correcting codes,” in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Y. Crama and P. Hammer, Eds., chapter 8, pp. 257–397, Cambridge University Press, New York, NY, USA, 2010.
[19]
C. Carlet and P. Guillot, “A characterization of binary bent functions,” Journal of Combinatorial Theory A, vol. 76, no. 2, pp. 328–335, 1996.
[20]
C. Carlet and J. L. Yucas, “Piecewise constructions of bent and almost optimal boolean functions,” Designs, Codes, and Cryptography, vol. 37, no. 3, pp. 449–464, 2005.
[21]
D. K. Chang, “Binary bent sequences of order 64,” Utilitas Mathematica, vol. 52, pp. 141–151, 1997.
[22]
J.-J. Climent, F. J. Gar？ia, and V. Requena, “On the construction of bent functions of variables from bent functions of n variables,” Advances in Mathematics of Communications, vol. 2, no. 4, pp. 421–431, 2008.
[23]
T. W. Cusick and P. St？nic？, Cryptographic Boolean Functions and Applications, Academic Press, San Diego, Calif, USA, 2009.
[24]
J. F. Dillon, Elementary hadamard difference sets [Ph.D. thesis], University of Maryland, College Park, Md, USA, 1974.
[25]
H. Dobbertin, “Construction of bent functions and balanced Boolean functions with high nonlinearity,” in Fast Sofware Encription, B. Preneel, Ed., vol. 1008 of Lecture Notes in Computer Science, pp. 61–74, Springer, Berlin, Germany, 1995.
[26]
H. Dobbertin and G. Leander, “Cryptographer's toolkit for construction of 8-bit bent functions,” Cryptology ePrint Archive 2005/089, 2005, http://eprint.iacr.org/.
[27]
J. Fuller, E. Dawson, and W. Millan, “Evolutionary generation of bent functions for cryptography,” in Proceedings of the IEEE Congress on Evolutionary Computation, vol. 2, pp. 1655–1661, December 2003.
[28]
X.-D. Hou and P. Langevin, “Results on bent functions,” Journal of Combinatorial Theory A, vol. 80, no. 2, pp. 232–246, 1997.
[29]
P. V. Kumar, R. A. Scholtz, and L. R. Welch, “Generalized bent functions and their properties,” Journal of Combinatorial Theory A, vol. 40, no. 1, pp. 90–107, 1985.
[30]
W. Meier and O. Staffelbach, “Nonlinearity criteria for cryptographic functions,” in Advances in Cryptology—EUROCRYPT '89, J. J. Quisquater and J. Vandewalle, Eds., vol. 434 of Lecture Notes in Computer Science, pp. 549–562, Springer, Berlin, Germany, 1990.
[31]
Q. Meng, H. Zhang, J. Cui, and M. Yang, “Almost enumeration of eight-variable bent functions,” Cryptology ePrint Archive 2005/100, 2005, http://eprint.iacr.org/.
[32]
B. Preneel, Analysis and design of cryptographic hash functions [Ph.D. thesis], Katholieke Universiteit Leuven, Leuven, Belgium, 1993.
[33]
J. Seberry and X. M. Zhang, “Constructions of bent functions from two known bent functions,” The Australasian Journal of Combinatorics, vol. 9, pp. 21–35, 1994.
[34]
N. Tokareva, “On the number of bent functions from iterative constructions: lower bounds and hypothesis,” Advances in Mathematics of Communications, vol. 5, no. 4, pp. 609–621, 2011.
[35]
N. Y. Yu and G. Gong, “Constructions of quadratic bent functions in polynomial forms,” IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 3291–3299, 2006.
[36]
R. L. McFarland, “A family of difference sets in noncyclic groups,” Journal of Combinatorial Theory A, vol. 15, no. 1, pp. 1–10, 1973.
[37]
O. S. Rothaus, “On “bent” functions,” Journal of Combinatorial Theory A, vol. 20, no. 3, pp. 300–305, 1976.
[38]
R. Yarlagadda and J. E. Hershey, “Analysis and synthesis of bent sequences,” IEE Proceedings E: Computers and Digital Techniques, vol. 136, no. 2, pp. 112–123, 1989.
[39]
C. Charnes, M. R？tteler, and T. Beth, “On homogeneous bent functions,” in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, S. Bozta？ and I. E. Shparlinski, Eds., vol. 2227 of Lecture Notes in Computer Science, pp. 249–259, Springer, Berlin, Germany, 2001.
[40]
C. Charnes, M. R？tteler, and T. Beth, “Homogeneous bent functions, invariants, and designs,” Designs, Codes and Cryptography, vol. 26, no. 1–3, pp. 139–154, 2002.
[41]
C. Qu, J. Seberry, and J. Pieprzyk, “On the symmetric property of homogeneous Boolean functions,” in Information Security and Privacy, J. Pieprzyk, R. Safavi-Naini, and J. Seberry, Eds., vol. 1587 of Lecture Notes in Computer Science, pp. 26–35, Springer, Berlin, Germany, 1999.
[42]
P. Langevin, “On generalized bent functions,” in Eurocode '92, vol. 339 of CISM Courses and Lectures, pp. 147–157, Springer, New York, NY, USA, 1992.
[43]
A. Canteaut and P. Charpin, “Decomposing bent functions,” IEEE Transactions on Information Theory, vol. 49, no. 8, pp. 2004–2019, 2003.
[44]
P. Langevin and G. Leander, “Counting all bent functions in dimension eight,” in Proceedings of the International Workshop on Coding and Cryptography, Ullensvang, Norway, May 2009.
[45]
G. D. Cohen, M. G. Karpovsky, H. F. Mattson Jr., and J. R. Schatz, “Covering radius—survey and recent results,” IEEE Transactions on Information Theory, vol. 31, no. 3, pp. 328–343, 1985.
[46]
J. Seberry, X.-M. Zhang, and Y. Zheng, “Systematic generation of cryptographically robust S-boxes (extended abstract),” in Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 171–182, Fairfax, Va, USA, November 1993.
[47]
A. Braeken, Y. Borissov, S. Nikova, and B. Preneel, “Classication of Boolean functions of 6 variables or less with respect to some cryptographic properties,” in Automata, Languages and Programming, L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, Eds., vol. 3580 of Lecture Notes in Computer Science, pp. 324–334, Springer, Berlin, Germany, 2005.
[48]
A. Canteaut, M. Daum, H. Dobbertin, and G. Leander, “Finding nonnormal bent functions,” Discrete Applied Mathematics, vol. 154, no. 2, pp. 202–218, 2006.
[49]
M. Daum, H. Dobbertin, and G. Leander, “An algorithm for checking normality of Boolean functions,” in Proceedings of the International Workshop on Coding and Cryptography (WCC '03), pp. 133–142, March 2003.
[50]
S. A. Vanstone and P. C. van Oorschot, An Introduction to Error Correcting Codes with Applications, Kluwer Academic, Boston, Mass, USA, 1989.
