Boolean function: Difference between revisions

Revision as of 00:11, 14 November 2024

Latest revision as of 10:25, 25 August 2025

(9 intermediate revisions by 5 users not shown)

Line 4:

{{Logical connectives sidebar}}

In [[mathematics]], a '''Boolean function''' is a [[function (mathematics)|function]] whose [[Argument of a function|arguments]] and result assume values from a two-element set (usually {true, false}, {0,1} or {-1−1,1}).<ref>{{Cite web|title=Boolean function - Encyclopedia of Mathematics|url=https://encyclopediaofmath.org/wiki/Boolean_function|access-date=2021-05-03|website=encyclopediaofmath.org}}</ref><ref>{{Cite web|last=Weisstein|first=Eric W.|title=Boolean Function|url=https://mathworld.wolfram.com/BooleanFunction.html|access-date=2021-05-03|website=mathworld.wolfram.com|language=en}}</ref> Alternative names are '''switching function''', used especially in older [[computer science]] literature,<ref>{{Cite web|title=switching function|url=https://encyclopedia2.thefreedictionary.com/switching+function|access-date=2021-05-03|website=TheFreeDictionary.com}}</ref><ref>{{Cite journal|last=Davies|first=D. W.|date=December 1957|title=Switching Functions of Three Variables|url=https://ieeexplore.ieee.org/document/5222038|journal=IRE Transactions on Electronic Computers|volume=EC-6|issue=4|pages=265–275|doi=10.1109/TEC.1957.5222038|issn=0367-9950}}</ref> and '''[[truth function]]''' (or '''logical function)''', used in [[logic]]. Boolean functions are the subject of [[Boolean algebra]] and [[switching theory]].<ref>{{Citation|last=McCluskey|first=Edward J.|title=Switching theory|date=2003-01-01|url=https://dl.acm.org/doi/10.5555/1074100.1074844|encyclopedia=Encyclopedia of Computer Science|pages=1727–1731|place=GBR|publisher=John Wiley and Sons Ltd.|doi=|isbn=978-0-470-86412-8|access-date=2021-05-03}}</ref>

A Boolean function takes the form <math>f:\{0,1\}^k \to \{0,1\}</math>, where <math>\{0,1\}</math> is known as the [[Boolean ___domain]] and <math>k</math> is a non-negative integer called the [[arity]] of the function. In the case where <math>k=0</math>, the function is a constant element of <math>\{0,1\}</math>. A Boolean function with multiple outputs, <math>f:\{0,1\}^k \to \{0,1\}^m</math> with <math>m>1</math> is a '''vectorial''' or ''vector-valued'' Boolean function (an [[S-box]] in symmetric [[cryptography]]).<ref name=":2" />

Line 27:

== Representation ==

[[File:Three input Booleanboolean circuit.jpgsvg|thumb|A Boolean function represented as a [[Boolean circuit]]]]

A Boolean function may be specified in a variety of ways:

Line 71:

=== 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''−1)-ary functions resulting from fixing one of the arguments (to zero0 or one1). 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''−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öbiusBoole–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 [[Fastfast 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|url-access=subscription}}</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 ===

Line 85:

==== 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 '''Linearlinear Approximationapproximation Tabletable''' (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 ''Differencedifference Distributiondistribution Tabletable'' (DDT)<ref name=":3" /><ref name=":4" /> which lists the correlations between differences in input and output bits (see also: [[S-box]]).

== Real polynomial form ==

Line 100:

=== On the symmetric hypercube ===

Often, the Boolean ___domain is taken as <math>\{-1, 1\}</math>, with false ("0") mapping to 1 and true ("1") to -1−1 (see [[Analysis of Boolean functions]]). The polynomial corresponding to <math>g(x): \{-1,1\}^n \rightarrow \{-1,1\}</math> is then given by:<math display="block">g^*(x) = \sum_{a \in {\{-1,1\}}^n} g(a) \prod_{i:a_i=-1} \frac{1-x_i}{2} \prod_{i:a_i=1} \frac{1+x_i}{2}</math>Using the symmetric Boolean ___domain simplifies certain aspects of the [[Analysis of Boolean functions|analysis]], since negation corresponds to multiplying by -1−1 and [[Parity function|linear functions]] are [[monomial]]s (XOR is multiplication). This polynomial form thus corresponds to the ''Walsh transform'' (in this context also known as ''Fourier transform'') of the function (see above). The polynomial also has the same statistical interpretation as the one in the standard Boolean ___domain, except that it now deals with the expected values <math>E(X) = P(X=1) - P(X=-1) \in [-1, 1]</math> (see [[piling-up lemma]] for an example).

==Applications==