Multiplicative complexity of vector valued Boolean functions

DOI10.1016/J.TCS.2018.02.023zbMATH Open1391.94909OpenAlexW2962749896WikidataQ130190369 ScholiaQ130190369MaRDI QIDQ1704580FDOQ1704580

Authors Magnus Find, Joan Boyar 

Publication date 12 March 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.6169

zbMATH Keywords

nonlinearityerror correcting codesmultiplicative complexitycircuits

Mathematics Subject Classification ID

Abstract: We consider the multiplicative complexity of Boolean functions with multiple bits of output, studying how large a multiplicative complexity is necessary and sufficient to provide a desired nonlinearity. For so-called $SigmaPiSigma$ circuits, we show that there is a tight connection between error correcting codes and circuits computing functions with high nonlinearity. Combining this with known coding theory results, we show that functions with $n$ inputs and $n$ outputs with the highest possible nonlinearity must have at least $2.32n$ AND gates. We further show that one cannot prove stronger lower bounds by only appealing to the nonlinearity of a function; we show a bilinear circuit computing a function with almost optimal nonlinearity with the number of AND gates being exactly the length of such a shortest code. Additionally we provide a function which, for general circuits, has multiplicative complexity at least $2n-3$. Finally we study the multiplicative complexity of "almost all" functions. We show that every function with $n$ bits of input and $m$ bits of output can be computed using at most $2.5(1+o(1))sqrtm{2}^n$ AND gates.

Recommendations

• The relationship between multiplicative complexity and nonlinearity
• On the multiplicative complexity of Boolean functions
• Multiplicative complexity of some Boolean functions
• On the Complexity of Computing Two Nonlinearity Measures
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).

Cites work

• scientific article; zbMATH DE number 1682693 (Why is no real title available?)
• scientific article; zbMATH DE number 5862915 (Why is no real title available?)
• scientific article; zbMATH DE number 4108153 (Why is no real title available?)
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1088929 (Why is no real title available?)
• scientific article; zbMATH DE number 1866861 (Why is no real title available?)
• scientific article; zbMATH DE number 3319974 (Why is no real title available?)
• An Improved Lower Bound on Polynomial Multiplication
• Boolean function complexity. Advances and frontiers.
• Ciphers for MPC and FHE
• Computing Blindfolded: New Developments in Fully Homomorphic Encryption
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Extremal combinatorics. With applications in computer science
• Financial cryptography and data security. FC 2013 workshops, USEC and WAHC 2013, Okinawa, Japan, April 1, 2013. Revised selected papers
• Financial cryptography and data security. FC 2014 workshops, BITCOIN and WAHC 2014, Christ Church, Barbados, March 7, 2014. Revised selected papers
• Improved Garbled Circuit: Free XOR Gates and Applications
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Multiplicative complexity of polynomial multiplication over finite fields
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
• On the complexity of multiplication in finite fields
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• On various nonlinearity measures for Boolean functions
• Polynomial multiplication over finite fields: from quadratic to straight-line complexity
• Restriction, terms and nonlinearity of Boolean functions
• The multiplicative complexity of quadratic boolean forms
• Tight bounds for the multiplicative complexity of symmetric functions
• Vectorial Boolean functions for cryptography

Cited in

(6)

• Improved upper bounds for the expected circuit complexity of dense systems of linear equations over \(\mathrm{GF}(2)\)
• The relationship between multiplicative complexity and nonlinearity
• A lower bound for differential uniformity by multiplicative complexity \& bijective functions of multiplicative complexity 1 over finite fields
• Multiplicative complexity of some Boolean functions
• Differential uniformity and linearity of S-boxes by multiplicative complexity
• Complexity of fixed-size bit-vector logics

This page was built for publication: Multiplicative complexity of vector valued Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704580)