# The multiplicative complexity of 6-variable Boolean functions

• Çağdaş Çalık
• Meltem Sönmez Turan
• René Peralta
Article
Part of the following topical collections:
1. Special Issue on Boolean Functions and Their Applications

## 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.

## Keywords

Affine equivalence Boolean functions Circuit complexity Cryptography Multiplicative complexity

94A60 06E30

## Notes

### Acknowledgments

We thank Ray Perlner for his suggestions on enumerating the subspaces of a vector space. We also thank Luís Brandão and the anonymous reviewers for helpful comments and suggestions.

## References

1. 1.
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)Google Scholar
2. 2.
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)Google Scholar
3. 3.
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)Google Scholar
4. 4.
Boyar, J., Damgård, I., Peralta, R.: Short non-interactive cryptographic proofs. J Cryptol 13(4), 449–472 (2000)
5. 5.
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)Google Scholar
6. 6.
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)Google Scholar
7. 7.
Codish, M., Cruz-Filipe, L., Frank, M., Schneider-Kamp, P.: When six gates are not enough. CoRR arXiv:1508.05737 (2015)
8. 8.
Boyar, J., Peralta, R.: Tight bounds for the multiplicative complexity of symmetric functions. Theor. Comput. Sci. 396(1–3), 223–246 (2008)
9. 9.
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)
10. 10.
Fuller, J.E.: Analysis of affine equivalent boolean functions for cryptography. PhD thesis, Queensland University of Technology (2003)Google Scholar
11. 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)
12. 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)
13. 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)
14. 14.
Hou, X.-D.: AGL (m, 2) acting on R (r, m)/R (s, m). J. Algebra 171(3), 927–938 (1995)
15. 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)Google Scholar
16. 16.
Knuth, D.E.: Subspaces, subsets, and partitions. J. Comb. Theory, Ser. A 10(2), 178–180 (1971)
17. 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)
18. 18.
NIST Computer Security Division. SLP’s for 6-variable predicates, https://github.com/usnistgov/Circuits/tree/master/slp

© This is a U.S. Government work and not under copyright protection in the US; foreign copyright protection may apply 2018

## Authors and Affiliations

• Çağdaş Çalık
• 1
• Meltem Sönmez Turan
• 1
• 2
• René Peralta
• 1
1. 1.National Institute of Standards and TechnologyGaithersburgUSA
2. 2.Dakota Consulting Inc.Silver SpringUSA
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8562958240509033, "perplexity": 5585.27783303908}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-39/segments/1537267156311.20/warc/CC-MAIN-20180919220117-20180920000117-00311.warc.gz"}