nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

The Multiplicative Complexity of Boolean Functions on Four and Five Variables

verfasst von : Meltem Turan Sönmez, René Peralta

Erschienen in: Lightweight Cryptography for Security and Privacy

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A generic way to design lightweight cryptographic primitives is to construct simple rounds using small nonlinear components such as 4\(\,\times \,\)4 S-boxes and use these iteratively (e.g., PRESENT [1] and SPONGENT [2]). In order to efficiently implement the primitive, efficient implementations of its internal components are needed. Multiplicative complexity of a function is the minimum number of AND gates required to implement it by a circuit over the basis (AND, XOR, NOT). It is known that multiplicative complexity is exponential in the number of input bits \(n\). Thus it came as a surprise that circuits for all \(65 536\) functions on four bits were found which used at most three AND gates [3]. In this paper, we verify this result and extend it to five-variable Boolean functions. We show that the multiplicative complexity of a Boolean function with five variables is at most four.

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

Vorheriges Kapitel The Simon and Speck Block Ciphers on AVR 8-Bit Microcontrollers

Nächstes Kapitel A Flexible and Compact Hardware Architecture for the SIMON Block Cipher

Nur mit Berechtigung zugänglich

Lest the reader think this easy, he/she may attempt to compute the function \(f(x_1,x_2,x_3,x_4,x_5) = x_1 x_2 x_3 x_4 x_5+x_1 x_2 x_3+x_1 x_2 x_4+x_2 x_3 x_4+x_1 x_2+ x_1 x_3+x_1 x_4+x_2 x_4+x_3 x_4\) using only four AND gates.

Bogdanov, A.A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007) CrossRef

Bogdanov, A., Knezevic, M., Leander, G., Toz, D., Varici, K., Verbauwhede, I.: SPONGENT: the design space of lightweight cryptographic hashing. IEEE Trans. Comput. 62(10), 2041–2053 (2013)CrossRefMathSciNet

Peralta, R.: Circuit minimization work, January 2014. http://cs-www.cs.yale.edu/homes/peralta/circuitstuff/cmt.html

Feldhofer, M., Wolkerstorfer, J., Rijmen, V.: AES implementation on a grain of sand. IEE Proc. Inf. Secur. 152(1), 13–20 (2005)CrossRef

Hamalainen, P., Alho, T., Hannikainen, M., Hamalainen, T.D.: Design and implementation of low-area and low-power AES encryption hardware core. In: Proceedings of the 9th EUROMICRO Conference on Digital System Design, DSD ’06, pp. 577–583. IEEE Computer Society, Washington, DC (2006)

Moradi, A., Poschmann, A., Ling, S., Paar, C., Wang, H.: Pushing the limits: a very compact and a threshold implementation of AES. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 69–88. Springer, Heidelberg (2011) CrossRef

Boyar, J., Peralta, R.: A small depth-16 circuit for the AES S-box. In: Gritzalis, D., Furnell, S., Theoharidou, M. (eds.) SEC 2012. IFIP AICT, vol. 376, pp. 287–298. Springer, Heidelberg (2012) CrossRef

Saarinen, M.-J.O.: Chosen-IV statistical attacks on estream ciphers. In: Malek, M., Fernández-Medina, E., Hernando, J. (eds.) SECRYPT, pp. 260–266. INSTICC Press (2006)

Boyar, J., Peralta, R.: A new combinational logic minimization technique with applications to cryptology. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 178–189. Springer, Heidelberg (2010) CrossRef

10.

Courtois, N., Hulme, D., Mourouzis, T.: Solving circuit optimisation problems in cryptography and cryptanalysis (2011)

11.

Courtois, N., Hulme, D., Mourouzis, T.: Multiplicative complexity and solving generalized brent equations with SAT solvers. In: COMPUTATION TOOLS 2012, The Third International Conference on Computational Logics, Algebras, Programming, Tools, and Benchmarking, pp. 22–27 (2012)

12.

Boyar, J., Find, M., Peralta, R.: Four measures of nonlinearity. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 61–72. Springer, Heidelberg (2013) CrossRef

13.

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

14.

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

15.

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

16.

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

17.

Braeken, A., Borissov, Y., Nikova, S., Preneel, B.: Classification of Boolean functions of 6 variables or less with respect to some cryptographic properties. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 324–334. Springer, Heidelberg (2005) CrossRef

18.

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

19.

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)

20.

Uyan, E.: Analysis of Boolean Functions with respect to Walsh Spectrum. Ph.D. thesis, Middle East Technical University (2013)

21.

Schnorr, C.-P.: The multiplicative complexity of Boolean functions. In: AAECC, pp. 45–58 (1988)

22.

Mirwald, R., Schnorr, C.-P.: The multiplicative complexity of quadratic Boolean forms. Theor. Comput. Sci. 102(2), 307–328 (1992)CrossRefMATHMathSciNet

23.

Boyar, J., Matthews, P., Peralta, R.: Logic minimization techniques with applications to cryptology. J. Cryptology 26(2), 280–312 (2013)CrossRefMATHMathSciNet

Titel: The Multiplicative Complexity of Boolean Functions on Four and Five Variables
verfasst von: Meltem Turan Sönmez
René Peralta
Verlag: Springer International Publishing
Buch: Lightweight Cryptography for Security and Privacy
Print ISBN: 978-3-319-16362-8

Electronic ISBN: 978-3-319-16363-5

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-16363-5_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"