Higher Order Nonlinearity of Niho Functions

• Autorzy: Sun G. , Wu C.

Identyfikatory

DOI

10.3233/FI-2015-1187

• Języki publikacji: EN

Abstrakty

EN

The r-th order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. In this paper we investigate the lower bound of the higher-order nonlinearity of Niho Boolean functions f(x) = tr(λx^d) over F_2n, where... [formula]

Słowa kluczowe

EN

Boolean function; cryptography; nonlinearity; derivation; Walsh spectrum; Reed Muller code

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 137, nr 3
• Strony: 403--412
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Sun G.

• College of Sciences, Hohai University Nanjing, 210098, China

autor

Wu C.

• State Key Laboratory of Information Security Institute of Information Engineering, Chinese Academy of Sciences Beijing, 100095, China

Bibliografia

• [1] Bracken, C., Leander, G.: A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree, Available at http://arxiv.org/abs/0901.1824.
• [2] Canteaut, A., Charpin, P., Kyureghyan, G. M.: A new class of monomial bent functions, Finite Fields and Their Applications, 14, 2008, 221–241.
• [3] Canteaut, A., Trabbia, M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5, Advances in Cryptology-Eurocrypt 2000, LNCS 1807, Springer-Verlag, 2000, 573–588.
• [4] Carlet, C.: On the higher order nonlinearities of algebraic immune functions, Advances in Cryptology-CRYPTO 2006, LNCS 4117, Springer-Verlag, 2006, 584–601.
• [5] Carlet, C.: Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications, IEEE Trans. Inform. Theory, 54(3), 2008, 1262–1272.
• [6] Carlet, C., Dalai, D., Gupta, K., Maitra, S.: Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction, IEEE Trans. Inform. Theory, 52(7), 2006, 3105–3121.
• [7] Carlet, C., Mesnager, S.: Improving the upper bounds on the covering radii of binary Reed-Muller codes, IEEE Trans. Inform. Theory, 53(1), 2007, 162–173.
• [8] Chabaud, F., Vaudenay, S.: Links between differential and linear cryptanalysis, Advances in Cryptology-EUROCRYPT’94, LNCS 950, Springer-Verlag, 1995, 356–365.
• [9] Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering codes, Amsterdam, The Netherlands: North-Holland, 1977.
• [10] Ding, C., Xiao, G., Shan,W.: The stability theory of stream ciphers, LNCS 561, Springer-Verlag, 1991.
• [11] Dobbertin, H.: One-to-one highly nonlinear power functions on GF(2n), Appl. Algebra Eng. Commum. Comput., 9, 1998, 139–152.
• [12] Dobbertin, H.: Uniformly representable permutation polynomials, In: Helleseth, P.V. Kumar, K. Yang(Eds.), Proc. of Sequences and Their Applications-SETA 01, Springer, London, 2002, 1–22.
• [13] Dumer, I., Kabatiansky, G., Tavernier, C.: List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity, Proc. IEEE Int. Symp. Information Theory, Seattle, WA, Jul. 2006, 138–142.
• [14] Fourquet, R., Tavernier, C.: List decoding of second order Reed-Muller and its covering radius implications, Proc. WCC 2007, Versailles, France, Apr. 2007, 147–156.
• [15] Gangopadhyay, S., Sarkar, S., Telang, R.: On the lower bounds of the second-order nonlinearity of some Boolean functions, Information Sciences, 180(2), 2010, 266–273.
• [16] Garg, M.: Good second-order nonlinearity of a subclass of Kasami function on five, seven and nine variables, Proc. of IEEE, International Conference on Communication Systems and Network Technologies (CSNT-2011), 3rd to 5th June, 2011, SMVDU, Katra, Jammu(India), 2011, 624–628.
• [17] Garg, M., Gangopadhyay, S.: A lower bound of the second-order nonlinearities of Boolean bent functions, Fundamenta Informaticae, European Association for Theoretical Computer Science (EATCS), 111(4), 2011, 413–422.
• [18] Garg, M., Khalyavin, A.: Higher order-nonlinearity of Kasami function, International Journal of Computer Mathematics, Taylor Francis, 89(10), 2012, 1311–1318.
• [19] Gode, R., Gangopadhyay, S.: Third-order nonlinearities of a subclass of Kasami functions, Cryptography Commun., 2, 2010, 69–83.
• [20] Iwata, T., Kurosawa, K.: Probabilistic higher order differential attack and higher order bent functions, Proc. ASIACRYPT’99, LNCS 1716, Berlin, Germany: Springer-Verlag, 1999, 62–74.
• [21] Kabatiansky, G., Tavernier, C.: List decoding of second-order Reed-Muller codes, Proc. 8th Int. Symp. Communication Theory and Applications, Ambelside, U.K., Jul. 2005.
• [22] Kolokotronis, N., Limniotis, K.: Maiorana-MacFarland functions with high second-order nonlinearity, Available at http://eprint.iacr.org/2011/212.pdf.
• [23] Kolokotronis, N., Limniotis, K., Kalouptsidis, N.: Best affine and quadratic approximations of particular classes of Boolean functions, IEEE Trans. Inform. Theory, 55(11), 2009, 5211–5222.
• [24] Li, X., Hu, Y., Gao, J.: Lower bounds on the second order nonlinearity of Boolean functions, Int. J. Found. Comput. Sci., 22(6), 2011, 1331–1349.
• [25] Lidl, R., Niederreiter, H.: Finite fields, Addison-Wesley, 1983.
• [26] Singh, D.: Second-order nonlinearities of some classes of cubic Boolean functions based on secondary constructions, Int. J. of Comput. Sci. Inform. Technol, 2(2), 2011, 786–791.
• [27] Sun, G., Wu, C.: The lower bounds on the second-order nonlinearity of three classes of Boolean functions with high nonlinearity, Information Sciences, 179(3), 2009, 267–278.
• [28] Sun, G., Wu, C.: The lower bound on the second-order nonlinearity of a class of Boolean function with high nonlinearity, Appl. Algebra Engrg. Comm. Comput., 22, 2011, 37–45.