The th-order nonlinearity of Boolean function plays a central role against several known attacks on stream and block ciphers. Because of the fact that its maximum equals the covering radius of the th-order Reed-Muller code, it also plays an important role in coding theory. The computation of exact value or high lower bound on the th-order nonlinearity of a Boolean function is very complicated problem, especially when . This paper is concerned with the computation of the lower bounds for third-order nonlinearities of two classes of Boolean functions of the form for all , , where , where , , and are integers such that and , and , where is a positive integer such that and . 1. Introduction Boolean functions are the building blocks for the design and the security of symmetric cryptographic systems and for the definition of some kinds of error correcting codes, sequences, and designs. The th-order nonlinearity, , of a Boolean function is defined by the minimum Hamming distance of to -Reed-Muller code of length and order . The nonlinearity of is given by and is related to the immunity of against best affine approximation attacks [1] and fast correlation attacks [2], when is used as a combiner function or a filter function in a stream cipher. The th-order nonlinearity is an important parameter, which measures the resistance of the function against various low-order approximation attacks [1, 3, 4]. In cryptographic framework, within a trade-off with the other important criteria, the th-order nonlinearity must be as large as possible; see [5–9]. Since, the maximal th-order nonlinearity of all Boolean functions equals the covering radius of , it also has an application in coding theory. Besides these applications, an interesting connection between the th-order nonlinearity and the fast algebraic attacks has been introduced, recently in [9], which claims that a cryptographic Boolean function should have high th-order nonlinearity to resist the fast algebraic attack. Unlike nonlinearity there is no efficient algorithm to compute second-order nonlinearities for . The most efficient algorithm is introduced by Fourquet and Tavernier [10] which works for and up to for some special functions. Thus, to identify a class of Boolean function with high th-order nonlinearity, even for , is a very relevant area of research. In 2008, Carlet has devolved a technique to compute th-order nonlinearity recursively in [11], and using this technique he has obtained the lower bounds of nonlinearity profiles for functions belonging to several classes of functions: Kasami functions,
References
[1]
J. Golic, “Fast low order approximation of cryptographic functions,” in Advances in Cryptology—EUROCRYPT '96, vol. 1070 of Lecture Notes in Computer Science, pp. 268–282, Springer, 1996.
[2]
W. Meier and O. Staffelbach, “Nonlinearity criteria for cryptographic functions,” in Advanced in Cryptology—EUROCRYPT '89, vol. 434 of Lecture Notes in Computer Science, pp. 549–562, Springer, 1990.
[3]
N. Courtois, “Higher order correlation attacks, XL algorithm and cryptanalysis of Toyocrypt,” in Information Security and Cryptology—ICISC, 2002, vol. 2587 of Lecture Notes in Computer Science, pp. 182–199, Springer, 2002.
[4]
T. Iwata and K. Kurosawa, “Probabilistic higher order differential attack and higher order bent functions,” in Advances in Cryptology—ASIACRYPT '99, vol. 1716 of Lecture Notes in Computer Science, pp. 62–74, Springer, 1999.
[5]
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 of the monograph, pp. 257–397, Cambridge University Press, 2010.
[6]
C. Ding, G. Xiao, and W. Shan, The Stability Theory of Stream Ciphers, vol. 561 of Lecture Notes in Computer Science, Springer, 1991.
[7]
L. Knudsen and M. Robshaw, “Non-linear approximations in linear cryptanalysis,” in Advances in Cryptology—EUROCRYPT '96, vol. 1070 of Lecture Notes in Computer Science, pp. 224–236, Springer, 1996.
[8]
T. Shimoyama and T. Kaneko, “Quadratic relation of S-box and its application to the linear attack of full round DES,” in Advanced in Cryptology—CRYPTO '98, vol. 1462 of Lecture Notes in Computer Science, pp. 200–211, Springer, 1998.
[9]
Q. Wang and T. Johansson, “A note on fast algebraic attacks and higher order nonlinearities,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6584, pp. 404–414, 2011.
[10]
R. Fourquet and C. Tavernier, “An improved list decoding algorithm for the second order Reed-Muller codes and its applications,” Designs, Codes, and Cryptography, vol. 49, no. 1–3, pp. 323–340, 2008.
[11]
C. Carlet, “Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications,” IEEE Transactions on Information Theory, vol. 54, no. 3, pp. 1262–1272, 2008.
[12]
R. Gode and S. Gangopadhyay, “Third-order nonlinearities of a subclass of Kasami functions,” Cryptography and Communications, vol. 2, no. 1, pp. 69–83, 2010.
[13]
S. Gangopadhyay and B. K. Singh, “On second-order nonlinearities of some type bent functions,” Fundamenta Informaticae, vol. 114, no. 3-4, pp. 271–285, 2012.
[14]
B. K. Singh, “On second-order nonlinearity and maximum algebraic immunity of some bent functions in ,” Journal of Applied Mathematics and Computing, 2014.
[15]
C. Carlet and S. Mesnager, “Improving the upper bounds on the covering radii of binary Reed-Muller codes,” IEEE Transactions on Information Theory, vol. 53, no. 1, pp. 162–173, 2007.
[16]
C. Carlet, “More vectorial Boolean functions with unbounded nonlinearity profile,” International Journal of Foundations of Computer Science, vol. 22, no. 6, pp. 1259–1269, 2011.
[17]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, North-Holland, Amsterdam, The Netherlands, 1977.
[18]
S. W. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communication, Cryptography and Radar, Cambridge University Press, 2005.
[19]
O. S. Rothaus, “On “bent” functions,” Journal of Combinatorial Theory A, vol. 20, no. 3, pp. 300–305, 1976.
[20]
C. Bracken, E. Byrne, N. Markin, and G. McGuire, “Determining the nonlinearity of a new family of APN functions,” Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, vol. 4851, pp. 72–79, 2007.
[21]
A. Canteaut, P. Charpin, and G. M. Kyureghyan, “A new class of monomial bent functions,” Finite Fields and Their Applications, vol. 14, no. 1, pp. 221–241, 2008.
[22]
J. Seberry, X. M. Zhang, and Y. Zheng, “Relationships among nonlinearity criteria,” in Advanced in Cryptology—EUROCRYPT '94, vol. 950 of Lecture Notes in Computer Science, pp. 376–388, Springer, 1995.
