Skip to main content
Erschienen in: Cryptography and Communications 6/2019

17.08.2019

Upper bounds on the multiplicative complexity of symmetric Boolean functions

verfasst von: Luís T. A. N. Brandão, Çağdaş Çalık, Meltem Sönmez Turan, René Peralta

Erschienen in: Cryptography and Communications | Ausgabe 6/2019

Einloggen

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

search-config
loading …

Abstract

A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a Boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (J. ACM 22(2), 195–201, 1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. (Theor. Comput. Sci. 235(1), 43–57, 2000) and by Boyar and Peralta (Theor. Comput. Sci. 396(1–3), 223–246, 2008). We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions \({{\Sigma }^{n}_{k}}\) and counting functions \({E^{n}_{k}}\) with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric \({{\Sigma }^{8}_{4}}\) and the counting \({E^{8}_{4}}\) functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132.

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!

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
4.
Zurück zum Zitat Kerntopf, P., Szyprowski, M.: Symmetry in reversible functions and circuits. In: Proceedings of 20th ICCC/ACM international workshop on logic and synthesis — IWLS 2011, pp 67–73 (2011) Kerntopf, P., Szyprowski, M.: Symmetry in reversible functions and circuits. In: Proceedings of 20th ICCC/ACM international workshop on logic and synthesis — IWLS 2011, pp 67–73 (2011)
6.
Zurück zum Zitat Kolesnikov, V., Schneider, T.: Improved garbled circuit: Free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, LA, Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) 35th international colloquium — ICALP 2008 automata, languages and programming, vol. 5126 of LNCS, vol. 5126, pp 486–498. Springer (2008). https://doi.org/10.1007/978-3-540-70583-3_40 Kolesnikov, V., Schneider, T.: Improved garbled circuit: Free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, LA, Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) 35th international colloquium — ICALP 2008 automata, languages and programming, vol. 5126 of LNCS, vol. 5126, pp 486–498. Springer (2008). https://​doi.​org/​10.​1007/​978-3-540-70583-3_​40
7.
Zurück zum Zitat Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) Proceedings of 3rd innovations in theoretical computer science conference — ITCS ’12, pp 309–325. ACM (2012). https://doi.org/10.1145/2090236.2090262 Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) Proceedings of 3rd innovations in theoretical computer science conference — ITCS ’12, pp 309–325. ACM (2012). https://​doi.​org/​10.​1145/​2090236.​2090262
9.
11.
Zurück zum Zitat Find, M.G.: On the complexity of computing two nonlinearity measures. In: Hirsch, E.A., Kuznetsov, S.O., Pin, J.-É., Vereshchagin, N.K. (eds.) Proceedings of CSR 2014: Computer science — theory and applications, vol. 8476 of LNCS, vol. 8476, pp 167–175. Springer International Publishing (2014). https://doi.org/10.1007/978-3-319-06686-8_13 Find, M.G.: On the complexity of computing two nonlinearity measures. In: Hirsch, E.A., Kuznetsov, S.O., Pin, J.-É., Vereshchagin, N.K. (eds.) Proceedings of CSR 2014: Computer science — theory and applications, vol. 8476 of LNCS, vol. 8476, pp 167–175. Springer International Publishing (2014). https://​doi.​org/​10.​1007/​978-3-319-06686-8_​13
13.
Zurück zum Zitat Sönmez Turan, M., Peralta, R.: The multiplicative complexity of Boolean functions on four and five variables. In: Eisenbarth, T., Öztürk, E. (eds.) Proceedings of 3rd international workshop on lightweight cryptography for security and privacy — LightSec 2014, vol. 8898 of LNCS, pp 21–33. Springer (2015). https://doi.org/10.1007/978-3-319-16363-5_2 Sönmez Turan, M., Peralta, R.: The multiplicative complexity of Boolean functions on four and five variables. In: Eisenbarth, T., Öztürk, E. (eds.) Proceedings of 3rd international workshop on lightweight cryptography for security and privacy — LightSec 2014, vol. 8898 of LNCS, pp 21–33. Springer (2015). https://​doi.​org/​10.​1007/​978-3-319-16363-5_​2
17.
Zurück zum Zitat Komamiya, Y.: Theory of computing networks, Bulletin of the Electrotechnical Laboratory. In Japanese (1959) Komamiya, Y.: Theory of computing networks, Bulletin of the Electrotechnical Laboratory. In Japanese (1959)
Metadaten
Titel
Upper bounds on the multiplicative complexity of symmetric Boolean functions
verfasst von
Luís T. A. N. Brandão
Çağdaş Çalık
Meltem Sönmez Turan
René Peralta
Publikationsdatum
17.08.2019
Verlag
Springer US
Erschienen in
Cryptography and Communications / Ausgabe 6/2019
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI
https://doi.org/10.1007/s12095-019-00377-3

Weitere Artikel der Ausgabe 6/2019

Cryptography and Communications 6/2019 Zur Ausgabe