nach oben

Cryptography and Communications

Erschienen in:

24.10.2017

On the nonlinearity of monotone Boolean functions

verfasst von: Claude Carlet

Erschienen in: Cryptography and Communications | Ausgabe 6/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We prove a conjecture on the nonlinearity of monotone Boolean functions in even dimension, proposed in the recent paper “Cryptographic properties of monotone Boolean functions”, by Carlet et al. (J. Math. Cryptol. 10(1), 1–14, 2016). We also prove an upper bound on such nonlinearity, which is asymptotically much stronger than the conjectured upper bound and than the upper bound proved for odd dimension in this same paper. Contrary to these two previous bounds, which were not tight enough for allowing to clarify if monotone functions can have good nonlinearity, this new bound shows that the nonlinearity of monotone functions is always very bad, which represents a fatal cryptographic weakness of monotone Boolean functions; they are too closely approximated by affine functions for being usable as nonlinear components in cryptographic applications. We deduce a necessary criterion to be satisfied by a Boolean (resp. vectorial) function for being nonlinear.

Vorheriger Artikel On the normality of p-ary bent functions

Nächster Artikel Correlation immune functions with respect to the q-transform

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

Nur mit Berechtigung zugänglich

Which states that for every Boolean function f over \(\mathbb {F}_{2}^{n}\), for every vector subspace E of \(\mathbb {F}_{2}^{n}\), and every elements a and b of \(\Bbb {F}_{2}^{n}\), we have \({\sum }_{\mathbf {u}\in \mathbf {a}+E}(-1)^{\mathbf {b}\cdot \mathbf {u}}\, W_{f}(\mathbf {u})= |E|\,(-1)^{\mathbf {a}\cdot \mathbf {b}}\, {\sum }_{\mathbf {x}\in \mathbf {b}+E^{\perp }}(-1)^{f(\mathbf {x})+\mathbf {a}\cdot \mathbf {x}}\), where E ^⊥ denotes the orthogonal of E, see e.g. in [6].

It is rare that this formula needs to be used for Boolean functions rather than the simpler Poisson formula; it is interesting to find such situation (here and in the next section as well).

Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley-VCH, New York (2000)CrossRef

Blum, A., Burch, C., Langford, J.: On learning monotone Boolean functions. In: Proceedings of the 39th FOCS, pp. 408–415. IEEE Computer Society Press (1998)

Blum, A., Furst, M., Kearns, M., Lipton, R.: Cryptographic primitives based on hard learning problems. In: Proceedings of Advances in Cryptology—CRYPTO’93, number 773 in LNCS, pp. 278–291. Springer, Berlin (1993)

Bshouty, N., Tamon, C.: On the Fourier spectrum of monotone functions. J. ACM 43(4), 747–770 (1996)MathSciNetCrossRefMATH

Canteaut, A., Carlet, C., Charpin, P., Fontaine, C.: On cryptographic properties of the cosets of R(1,m). IEEE Trans. Inf. Theory 47(4), 1494–1513 (2001)MathSciNetCrossRefMATH

Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models, pp. 257–397. Cambridge University Press, Cambridge (2010). Available at: www.math.univ-paris13.fr/~carlet/pubs.html

Carlet, C.: Vectorial Boolean functions for cryptography. In: Crama, Y., Hammer, P. (eds.) Boolean Methods and Models, pp. 398–469. Cambridge University Press, Cambridge (2010). Available at: www.math.univ-paris13.fr/~carlet/pubs.html

Carlet, C., Joyner, D., Stănică, P., Tang, D.: Cryptographic properties of monotone Boolean functions. J. Math. Cryptol. 10(1), 1–14 (2016)MathSciNetCrossRefMATH

Crama, Y., Hammer, P.L.: Boolean Functions. Theory, Algorithms, and Applications. Cambridge University Press, Cambridge (2011)CrossRefMATH

10.

Dalai, D.K., Maitra, S., Sarkar, S.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr. 40(1), 41–58 (2006)MathSciNetCrossRefMATH

11.

Dachman-Soled, D., Lee, H.K., Malkin, T., Servedio, R.A., Wan, A., Wee, H.: Optimal cryptographic hardness of learning monotone functions. Theory Comput. 5, 257–282 (2009)MathSciNetCrossRefMATH

12.

Mossel, E., O’Donnell, R.: On the noise sensitivity of monotone functions. Random Struct. Algorithms 23(3), 333–350 (2003)MathSciNetCrossRefMATH

Titel: On the nonlinearity of monotone Boolean functions
verfasst von: Claude Carlet
Publikationsdatum: 24.10.2017
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 6/2018
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-017-0262-5

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 6/2018

The cycle structure of LFSR with arbitrary characteristic polynomial over finite fields

Correction to: Good integers and some applications in coding theory

Complete weight enumerators of three classes of linear codes

Cyclic codes over

On the normality of p-ary bent functions

A new class of permutation trinomials constructed from Niho exponents