nach oben

Cryptography and Communications

Erschienen in:

03.04.2018

The multiplicative complexity of 6-variable Boolean functions

verfasst von: Çağdaş Çalık, Meltem Sönmez Turan, René Peralta

Erschienen in: Cryptography and Communications | Ausgabe 1/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The multiplicative complexity of a Boolean function is the minimum number of two-input AND gates that are necessary and sufficient to implement the function over the basis (AND, XOR, NOT). Finding the multiplicative complexity of a given function is computationally intractable, even for functions with small number of inputs. Turan et al. [1] showed that n-variable Boolean functions can be implemented with at most \(n-1\) AND gates for \(n\leq 5\). A counting argument can be used to show that, for n ≥ 7, there exist n-variable Boolean functions with multiplicative complexity of at least n. In this work, we propose a method to find the multiplicative complexity of Boolean functions by analyzing circuits with a particular number of AND gates and utilizing the affine equivalence of functions. We use this method to study the multiplicative complexity of 6-variable Boolean functions, and calculate the multiplicative complexities of all 150 357 affine equivalence classes. We show that any 6-variable Boolean function can be implemented using at most 6 AND gates. Additionally, we exhibit specific 6-variable Boolean functions which have multiplicative complexity 6.

Vorheriger Artikel New classes of p-ary bent functions

Nächster Artikel Small low-depth circuits for cryptographic applications

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

We abuse notation here, identifying a node with the function it computes.

The Gaussian binomial coefficient \(\binom {m}{r}_{q}\) is defined to be \(\frac {(1-q^{m})(1-q^{m-1}){\cdots } (1-q^{m-r + 1})}{(1-q)(1-q^{2})\cdots (1-q^{r})}\) for \(r\leq m\), and zero otherwise.

Commercial equipment and software referred to in this paper are identified for informational purposes only, and does not imply recommendation of or endorsement by the National Institute of Standards and Technology, nor does it imply that the products so identified are necessarily the best available for the purpose.

Sönmez, M.T., Peralta, R.: The Multiplicative Complexity of Boolean Functions on Four and Five Variables, pp. 21–33. Springer International Publishing, Cham (2015)MATH

Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewic, I. (eds.) Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, volume 5126 of Lecture Notes in Computer Science, pp 486–498. Springer (2008)

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S (ed.) Innovations in Theoretical Computer Science 2012, January 8–10, 2012, pp. 309–325. ACM, Cambridge (2012)

Boyar, J., Damgård, I., Peralta, R.: Short non-interactive cryptographic proofs. J Cryptol 13(4), 449–472 (2000)MathSciNetCrossRef

Carlet, C., Goubin, L., Prouff, E., Quisquater, M., Rivain, M.: Higher-order masking schemes for s-boxes. In: Canteaut, A. (ed.) Fast Software Encryption—19th International Workshop, FSE 2012, Washington, DC, USA, March 19–21, 2012. Revised Selected Papers, volume 7549 of Lecture Notes in Computer Science, pages 366–384. Springer (2012)CrossRef

Gausdal Find, M.: On the complexity of computing two nonlinearity measures. In: Computer Science—Theory and Applications—9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7–11, 2014. Proceedings, pp. 167–175 (2014)

Codish, M., Cruz-Filipe, L., Frank, M., Schneider-Kamp, P.: When six gates are not enough. CoRR arXiv:1508.05737 (2015)

Boyar, J., Peralta, R.: Tight bounds for the multiplicative complexity of symmetric functions. Theor. Comput. Sci. 396(1–3), 223–246 (2008)MathSciNetCrossRef

Boyar, J., Peralta, R., Pochuev, D.: On the multiplicative complexity of Boolean functions over the basis (∧, \(\oplus \), 1). Theor. Comput. Sci. 235(1), 43–57 (2000)MathSciNetCrossRef

10.

Fuller, J.E.: Analysis of affine equivalent boolean functions for cryptography. PhD thesis, Queensland University of Technology (2003)

11.

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)MathSciNetCrossRef

12.

Maiorana, J.A.: A classification of the cosets of the Reed-Muller code \(\mathcal {R}\)(1,6). Math. Comput. 57(195), 403–414 (1991)MathSciNetMATH

13.

Braeken, A., Borissov, Y., Nikova, S., Preneel, B.: Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties, pp. 324–334. Berlin, Heidelberg (2005)MATH

14.

Hou, X.-D.: AGL (m, 2) acting on R (r, m)/R (s, m). J. Algebra 171(3), 927–938 (1995)MathSciNetCrossRef

15.

Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science and Engineering, chapter 8. Cambridge University Press, Cambridge (2010)

16.

Knuth, D.E.: Subspaces, subsets, and partitions. J. Comb. Theory, Ser. A 10(2), 178–180 (1971)MathSciNetCrossRef

17.

Goldman, J., Rota, G.-C.: On the foundations of combinatorial theory iv finite vector spaces and eulerian generating functions. Stud. Appl. Math. 49(3), 239–258 (1970)MathSciNetCrossRef

18.

NIST Computer Security Division. SLP’s for 6-variable predicates, https://github.com/usnistgov/Circuits/tree/master/slp

Titel: The multiplicative complexity of 6-variable Boolean functions
verfasst von: Çağdaş Çalık
Meltem Sönmez Turan
René Peralta
Publikationsdatum: 03.04.2018
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 1/2019
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-018-0297-2

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/2019

On APN functions L1(x3) + L2(x9) with linear L1 and L2

Cellular automata based S-boxes

On the nonlinearity of Boolean functions with restricted input

Editorial: Special Issue on Boolean functions and their applications

New permutation trinomials from Niho exponents over finite fields with even characteristic

On an algorithm generating 2-to-1 APN functions and its applications to “the big APN problem”