Editing Boolean function (section)

== Analysis ==
{{see also|Analysis of Boolean functions}}

===Properties===

A Boolean function can have a variety of properties:<ref name=":0">{{Cite web|title=Boolean functions — Sage 9.2 Reference Manual: Cryptography|url=https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/boolean_function.html|access-date=2021-05-01|website=doc.sagemath.org}}</ref>

* [[Constant function|Constant]]: Is always true or always false regardless of its arguments.
* [[Monotonic function#In Boolean functions|Monotone]]: for every combination of argument values, changing an argument from false to true can only cause the output to switch from false to true and not from true to false. A function is said to be [[Unate function|unate]] in a certain variable if it is monotone with respect to changes in that variable. 
* [[Linearity#Boolean functions|Linear]]: for each variable, flipping the value of the variable either always makes a difference in the truth value or never makes a difference (a [[parity function]]).
* [[Symmetric Boolean function|Symmetric]]: the value does not depend on the order of its arguments.
* [[Read-once function|Read-once]]: Can be expressed with [[logical conjunction|conjunction]], [[logical disjunction|disjunction]], and [[negation]] with a single instance of each variable.
*[[Balanced Boolean function|Balanced]]: if its [[truth table]] contains an equal number of zeros and ones. The [[Hamming weight]] of the function is the number of ones in the truth table.
* [[Bent function|Bent]]: its derivatives are all balanced (the autocorrelation spectrum is zero)
* [[Correlation immunity|Correlation immune]] to ''m''th order: if the output is uncorrelated with all (linear) combinations of at most ''m'' arguments
*[[Evasive Boolean function|Evasive]]: if evaluation of the function always requires the value of all arguments
*A Boolean function is a ''Sheffer function'' if it can be used to create (by composition) any arbitrary Boolean function (see [[functional completeness]])
*The ''algebraic degree'' of a function is the order of the highest order monomial in its [[algebraic normal form]]
[[Circuit complexity]] attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them.

=== Derived functions ===
A Boolean function may be decomposed using [[Boole's expansion theorem]] in positive and negative ''Shannon'' ''cofactors'' ([[Shannon expansion]]), which are the (''k''−1)-ary functions resulting from fixing one of the arguments (to 0 or 1). The general ''k''-ary functions obtained by imposing a linear constraint on a set of inputs (a linear subspace) are known as ''subfunctions''.<ref name=":1">{{Cite book|last1=Tarannikov|first1=Yuriy|last2=Korolev|first2=Peter|last3=Botev|first3=Anton|title=Advances in Cryptology — ASIACRYPT 2001 |chapter=Autocorrelation Coefficients and Correlation Immunity of Boolean Functions |date=2001|editor-last=Boyd|editor-first=Colin|series=Lecture Notes in Computer Science|volume=2248|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=460–479|doi=10.1007/3-540-45682-1_27|isbn=978-3-540-45682-7|doi-access=free}}</ref>

The ''[[Boolean derivative]]'' of the function to one of the arguments is a (''k''−1)-ary function that is true when the output of the function is sensitive to the chosen input variable; it is the XOR of the two corresponding cofactors. A derivative and a cofactor are used in a [[Reed–Muller expansion]]. The concept can be generalized as a ''k''-ary derivative in the direction dx, obtained as the difference (XOR) of the function at x and x + dx.<ref name=":1" />

The ''[[Zhegalkin polynomial#Möbius transformation|Möbius transform]]'' (or ''Boole–Möbius transform'') of a Boolean function is the set of coefficients of its [[Zhegalkin polynomial|polynomial]] ([[algebraic normal form]]), as a function of the monomial exponent vectors. It is a [[Involution (mathematics)|self-inverse]] transform. It can be calculated efficiently using a [[Butterfly diagram|butterfly algorithm]] ("''Fast Möbius Transform''"), analogous to the [[Fast Fourier transform|Fast Fourier Transform]].<ref>{{Citation|last=Carlet|first=Claude|title=Boolean Functions for Cryptography and Error-Correcting Codes|date=2010|url=https://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf|work=Boolean Models and Methods in Mathematics, Computer Science, and Engineering|pages=257–397|editor-last=|editor-first=|series=Encyclopedia of Mathematics and its Applications|place=Cambridge|publisher=Cambridge University Press|isbn=978-0-521-84752-0|access-date=2021-05-17|editor2-last=|editor2-first=}}</ref> ''Coincident'' Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients.<ref>{{Cite journal|last1=Pieprzyk|first1=Josef|last2=Wang|first2=Huaxiong|last3=Zhang|first3=Xian-Mo|date=2011-05-01|title=Mobius transforms, coincident Boolean functions and non-coincidence property of Boolean functions|url=https://doi.org/10.1080/00207160.2010.509428|journal=International Journal of Computer Mathematics|volume=88|issue=7|pages=1398–1416|doi=10.1080/00207160.2010.509428|s2cid=9580510 |issn=0020-7160}}</ref> There are 2^2^(''k''−1) coincident functions of ''k'' arguments.<ref>{{Cite journal|last1=Nitaj|first1=Abderrahmane|last2=Susilo|first2=Willy|last3=Tonien|first3=Joseph|date=2017-10-01|title=Dirichlet product for boolean functions|url=https://doi.org/10.1007/s12190-016-1037-4|journal=Journal of Applied Mathematics and Computing|language=en|volume=55|issue=1|pages=293–312|doi=10.1007/s12190-016-1037-4|s2cid=16760125 |issn=1865-2085}}</ref>

=== Cryptographic analysis ===
The ''[[Walsh transform]]'' of a Boolean function is a k-ary integer-valued function giving the coefficients of a decomposition into [[Parity function|linear functions]] ([[Walsh function]]s), analogous to the decomposition of real-valued functions into [[harmonic]]s by the [[Fourier transform]]. Its square is the ''power spectrum'' or ''Walsh spectrum''. The Walsh coefficient of a single bit vector is a measure for the correlation of that bit with the output of the Boolean function. The maximum (in absolute value) Walsh coefficient is known as the ''linearity'' of the function.<ref name=":1" /> The highest number of bits (order) for which all Walsh coefficients are 0 (i.e. the subfunctions are balanced) is known as ''resiliency'', and the function is said to be [[Correlation immunity|correlation immune]] to that order.<ref name=":1" /> The Walsh coefficients play a key role in [[linear cryptanalysis]].

The ''[[autocorrelation]]'' of a Boolean function is a k-ary integer-valued function giving the correlation between a certain set of changes in the inputs and the function output. For a given bit vector it is related to the Hamming weight of the derivative in that direction. The maximal autocorrelation coefficient (in absolute value) is known as the ''absolute indicator''.<ref name=":0" /><ref name=":1" /> If all autocorrelation coefficients are 0 (i.e. the derivatives are balanced) for a certain number of bits then the function is said to satisfy the ''propagation criterion'' to that order; if they are all zero then the function is a [[bent function]].<ref>{{Cite journal|last1=Canteaut|first1=Anne|last2=Carlet|first2=Claude|last3=Charpin|first3=Pascale|last4=Fontaine|first4=Caroline|date=2000-05-14|title=Propagation characteristics and correlation-immunity of highly nonlinear boolean functions|url=https://dl.acm.org/doi/10.5555/1756169.1756219|journal=Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques|series=EUROCRYPT'00|location=Bruges, Belgium|publisher=Springer-Verlag|pages=507–522|isbn=978-3-540-67517-4}}</ref> The autocorrelation coefficients play a key role in [[differential cryptanalysis]].

The Walsh coefficients of a Boolean function and its autocorrelation coefficients are related by the equivalent of the [[Wiener–Khinchin theorem]], which states that the autocorrelation and the power spectrum are a Walsh transform pair.<ref name=":1" />

==== Linear approximation table ====
These concepts can be extended naturally to ''vectorial'' Boolean functions by considering their output bits (''coordinates'') individually, or more thoroughly, by looking at the set of all linear functions of output bits, known as its ''components''.<ref name=":2">{{Cite web|last=Carlet|first=Claude|title=Vectorial Boolean Functions for Cryptography|url=https://www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf|url-status=live|website=University of Paris|archive-url=https://web.archive.org/web/20160117102533/http://www.math.univ-paris13.fr:80/~carlet/chap-vectorial-fcts-corr.pdf |archive-date=2016-01-17 }}</ref> The set of Walsh transforms of the components is known as a '''Linear Approximation Table''' (LAT)<ref name=":3">{{Cite web|last=Heys|first=Howard M.|title=A Tutorial on Linear and Differential Cryptanalysis|url=http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf|url-status=live|archive-url=https://web.archive.org/web/20170517014157/http://www.cs.bc.edu:80/~straubin/crypto2017/heys.pdf |archive-date=2017-05-17 }}</ref><ref name=":4">{{Cite web|title=S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography|url=https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sbox.html|access-date=2021-05-04|website=doc.sagemath.org}}</ref> or ''correlation matrix'';<ref>{{cite conference | last1 = Daemen | first1 = Joan | last2 = Govaerts | first2 = René | last3 = Vandewalle | first3 = Joos | editor-last = Preneel | editor-first = Bart | title = Correlation matrices | doi = 10.1007/3-540-60590-8_21 | pages = 275–285 | publisher = Springer | series = Lecture Notes in Computer Science | book-title = Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14-16 December 1994, Proceedings | volume = 1008 | year = 1994| doi-access = free }}</ref><ref>{{Cite web|last=Daemen|first=Joan|date=10 June 1998|title=Chapter 5: Propagation and Correlation - Annex to AES Proposal Rijndael|url=https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf|url-status=live|website=NIST|archive-url=https://web.archive.org/web/20180723015757/https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf |archive-date=2018-07-23 }}</ref> it describes the correlation between different linear combinations of input and output bits. The set of autocorrelation coefficients of the components is the ''autocorrelation table'',<ref name=":4" /> related by a Walsh transform of the components<ref>{{Cite web|last=Nyberg|first=Kaisa|date=December 1, 2019|title=The Extended Autocorrelation and Boomerang Tables and Links Between Nonlinearity Properties of Vectorial Boolean Functions|url=https://eprint.iacr.org/2019/1381.pdf|url-status=live|archive-url=https://web.archive.org/web/20201102023321/https://eprint.iacr.org/2019/1381.pdf |archive-date=2020-11-02 }}</ref> to the more widely used ''Difference Distribution Table'' (DDT)<ref name=":3" /><ref name=":4" /> which lists the correlations between differences in input and output bits (see also: [[S-box]]).