nach oben

Cryptography and Communications

Erschienen in:

01.04.2010

Third-order nonlinearities of a subclass of Kasami functions

verfasst von: Ruchi Gode, Sugata Gangopadhyay

Erschienen in: Cryptography and Communications | Ausgabe 1/2010

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The rth-order nonlinearity, where r ≥ 1, of an n-variable Boolean function f, denoted by nl _r(f), is defined as the minimum Hamming distance of f from all n-variable Boolean functions of degrees at most r. In this paper we obtain a lower bound of the third-order nonlinearities of Kasami functions of the form \(Tr_{1}^{n}(\mu x^{57})\). It is demonstrated that for large values of n the lower bound of the third-order nonlinearities of the functions of this form is larger than the general lower bound obtained by Carlet (IEEE Trans Inf Theory 54(3):1262–1272, 2008) for Kasami functions. Further we show that our result along with the computational results obtained by Fourquet and Tavernier (Designs Codes Cryptogr 49:323–340, 2008) provide us an estimate of the nonlinearity profiles of these functions for n = 7, 8, 10.

Vorheriger Artikel Pseudorandom numbers and hash functions from iterations of multivariate polynomials

Nächster Artikel and related affine polynomials over GF (2 k )

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Berlekamp, E.R., Welch, L.R.: Weight distributions of the cosets of the (32, 6) Reed-Muller code. IEEE Trans. Inf. Theory 18(1), 203–207 (1972)MATHCrossRefMathSciNet

Canteaut, A., Charpin, P., Kyureghyan, G.M.: A new class of monomial bent functions. Finite Fields their Appl. 14, 221–241 (2008)MATHCrossRefMathSciNet

Carlet, C.: The complexity of Boolean functions from cryptographic viewpoint. In: Dagstuhl Seminar Complexity of Boolean Functions, 15 pp. (2006)

Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models. Cambridge Univ. Press, Cambridge. Available: http://www-roc.inria.fr/secret/Claude.Carlet/pubs.html (to be published)

Carlet, C.: Vectorial Boolean functions for cryptography. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models. Cambridge Univ. Press, Cambridge. Available: http://www-roc.inria.fr/secret/Claude.Carlet/pubs.html (to be published)

Carlet, C., Mesnager, S.: Improving the upper bounds on the covering radii of binary Reed-Muller codes. IEEE Trans. Inf. Theory 53(1), 162–173 (2007)CrossRefMathSciNet

Carlet, C.: Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications. IEEE Trans. Inf. Theory 54(3), 1262–1272 (2008)CrossRefMathSciNet

Courtois, N.: Higher order correlation attacks, XL algorithm and cryptanalysis of Toyocrypt. In: Proceedings of the ICISC’02. LNCS, vol. 2587, pp. 182–199. Springer (2002)

Dobbertin, H.: Another proof of Kasami’s theorem, Designs Codes Cryptogr. 17, 177–180 (1999)

10.

Dobbertin, H.: Almost perfect nonlinear power functions on GF(2)ⁿ: the Niho case. Inf. Comput. 151, 57–72 (1999)MATHCrossRefMathSciNet

11.

Dobbertin, H.: Kasami power functions, permutation polynomials and cyclic difference sets, in difference sets, sequences and their correlation properties. In: Proceedings of the NATO Advanced Study Institute on Difference Sets, Sequences and their Correlation Properties, Bad Windsheim, pp. 133–158, 2–14 August 1998. Kluwer, Dordrecht (1999)

12.

Dumer, I., Kabatiansky, G., Tavernier, C.: List decoding of second order Reed-Muller codes up to the Johnson bound with almost linear complexity. In: Proceedings of the IEEE International Symposium on Information Theory, pp. 138–142, Seattle, WA (2006)

13.

Fourquet, R., Tavernier, C.: An improved list decoding algorithm for the second order ReedMuller codes and its applications. Designs Codes Cryptogr. 49, 323–340 (2008)MATHCrossRefMathSciNet

14.

Golic, J.: Fast low order approximation of cryptographic functions. In: Proceedings of the EUROCRYPT’96. LNCS, vol. 1996, pp. 268–282. Springer (1996)

15.

Iwata, T., Kurosawa, K.: Probabilistic higher order differential attack and higher order bent functions. In: Proceedings of the ASIACRYPT’99. LNCS, vol. 1716, pp. 62–74. Springer (1999)

16.

Kasami, T.: The weight enumerators for several classes of subcodes of the second order binary Reed Muller codes. Inf. Control 18, 369–394 (1971)MATHCrossRefMathSciNet

17.

Kabatiansky, G., Tavernier, C.: List decoding of second order Reed-Muller codes. In: Proceedings of the Eighth International Symposium of Communication Theory and Applications. Ambleside, UK (2005)

18.

Kavut, S., Maitra, S., Sarkar, S., Yücel, M.D.: Enumeration of 9-variable rotation symmetric Boolean functions having nonlinearity > 240. In: Proceedings of the INDOCRYPT’06. LNCS, vol. 4329, pp. 266–279. Springer (2006)

19.

Kavut, S., Yücel, M.D.: Generalized rotation symmetric and dihedral symmetric Boolean functions—9 variable Boolean functions with nonlinearity 242. In: Proceedings of the AAECC’07. LNCS, vol. 4851, pp. 266–279. Springer (2007)

20.

Knudsen, L.R., Robshaw, M.J.B.: Non-linear approximations in linear cryptanalysis. In: Proceedings of the EUROCRYPT’96. LNCS, vol. 1070, pp. 224–236. Springer (1996)

21.

Lidl, R., Niederreiter, H.: Introduction to finite fields and their applications. Cambridge University Press, Cambridge (1983)

22.

MacWilliams, F.J., Sloane, N.J.A.: The theory of error correcting codes. North-Holland, Amsterdam (1977)MATH

23.

Matsui, M.: Linear cryptanalysis method for DES cipher. In: Proceedings of the EUROCRYPT93. LNCS, vol. 765, pp. 386–397 (1994)

24.

Maurer, U.M.: New approaches to the design of self-synchronizing stream ciphers. In: Proceedings of the EUROCRYPT’91. LNCS, vol. 547, pp. 458-471 (1991)

25.

Millan, W.: Low order approximation of cipher functions, In: Cryptographic policy and algorithms. LNCS, vol. 1029, pp. 144–155 (1996)MathSciNet

26.

Mykkeltveit, J.J.: The covering radius of the (128, 8) Reed-Muller code is 56. IEEE Trans. Inf. Theory 26(3), 359–362 (1980)MATHCrossRefMathSciNet

27.

Patterson, N.J., Wiedemann, D.H.: The covering radius of the (2¹⁵, 16) Reed-Muller code is at least 16276. IEEE Trans. Inf. Theory 29(3), 354–356 (1983)MATHCrossRefMathSciNet

28.

Rothaus, O.S.: On bent functions. J. Comb. Theory, Ser. A 20, 300–305 (1976)MATHCrossRefMathSciNet

29.

Sarkar, P., Maitra, S.: Construction of nonlinear Boolean functions with important cyrptographic properties. In: Proceedings of the EUROCRYPT 2000. LNCS, vol. 1870, pp. 485–506 (2000)

30.

Sun, G., Wu, C.: The lower bounds on the second order nonlinearity of three classes of Boolean functions with high nonlinearity. Inf. Sci. 179(3), 267–278 (2009)MATHCrossRefMathSciNet

Titel: Third-order nonlinearities of a subclass of Kasami functions
verfasst von: Ruchi Gode
Sugata Gangopadhyay
Publikationsdatum: 01.04.2010
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 1/2010
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-009-0017-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2010

and related affine polynomials over GF (2 k )

On the structural weakness of the GGHN stream cipher

Asymptotic enumeration of correlation-immune boolean functions

New bounds for (r, ≤ 2)-identifying codes in the infinite king grid

The second weight of generalized Reed-Muller codes in most cases

Pseudorandom numbers and hash functions from iterations of multivariate polynomials

Premium Partner