Content deleted Content added
→Linear approximation table: correlation matrix doesn't redirect here |
m task, replaced: Advances in Cryptology — → Advances in Cryptology – |
||
Line 1:
{{Short description|Function returning one of only two values}}
{{distinguish|Binary function}}
[[File:BinaryDecisionTree.svg|thumb|A [[binary decision diagram]] and [[truth table]] of a ternary Boolean function]]
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" />
There are <math>2^{2^k}</math> different Boolean functions with <math>k</math> arguments; equal to the number of different [[
Every <math>k</math>-ary Boolean function can be expressed as a [[propositional formula]] in <math>k</math> variables <math>x_1,...,x_k</math>, and two propositional formulas are [[logical equivalence|logically equivalent]] if and only if they express the same Boolean function.
Line 12 ⟶ 13:
[[File:Logical connectives Hasse diagram.svg|alt=Diagram displaying the sixteen binary Boolean functions|thumb|The sixteen binary Boolean functions]]
{{See also|Truth table}}
The rudimentary symmetric Boolean functions ([[
* [[Inverter (logic gate)|NOT]], [[negation]] or [[Logical complement|complement]] - which receives one input and returns true when that input is false ("not")
* [[AND gate|AND]] or [[Logical conjunction|conjunction]] - true when all inputs are true ("both")
* [[OR gate|OR]] or [[Logical disjunction|disjunction]] - true when any input is true ("either")
* [[XOR gate|XOR]] or [[Exclusive or|exclusive disjunction]] - true when one of its inputs is true and the other is false ("not equal")
* [[NAND gate|NAND]] or [[Sheffer stroke]] - true when it is not the case that all inputs are true ("not both")
*[[NOR gate|NOR]] or [[Logical NOR|logical nor]] - true when none of the inputs are true ("neither")
Line 44 ⟶ 41:
**''Full'' (canonical) [[disjunctive normal form]], an OR of ANDs each containing every argument or complement ([[minterms]])
**''Full'' (canonical) [[conjunctive normal form]], an AND of ORs each containing every argument or complement ([[maxterms]])
**[[Blake canonical form]], the OR of all the [[
Boolean formulas can also be displayed as a graph:
* [[Propositional directed acyclic graph]]
**[[Circuit (computer science)|Digital circuit]] diagram of [[
**[[And-inverter graph]], using only AND and NOT
In order to optimize electronic circuits, Boolean formulas can be [[Minimization of Boolean functions|minimized]] using the [[Quine–McCluskey algorithm]] or [[Karnaugh map]].
Line 72 ⟶ 69:
=== 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 zero or one). 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 journal|last1=Tarannikov|first1=Yuriy|last2=Korolev|first2=Peter|last3=Botev|first3=Anton|date=2001|editor-last=Boyd|editor-first=Colin|title=Autocorrelation Coefficients and Correlation Immunity of Boolean Functions|journal=Advances in Cryptology
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" />
Line 79 ⟶ 76:
=== 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
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]].
Line 98 ⟶ 95:
\end{array}</math>this generalizes as the [[Möbius transform|Möbius inversion]] of the [[partially ordered set]] of bit vectors:<math display="block">f^*(m) = \sum_{a \subseteq m} (-1)^{|a|+|m|} f(a)</math>where <math>|a|</math> denotes the weight of the bit vector <math>a</math>. Taken modulo 2, this is the [[Zhegalkin polynomial|Boolean ''Möbius transform'']], giving the [[algebraic normal form]] coefficients:<math display="block">\hat f(m) = \bigoplus_{a \subseteq m} f(a)</math>In both cases, the sum is taken over all bit-vectors ''a'' covered by ''m'', i.e. the "one" bits of ''a'' form a subset of the one bits of ''m''.
When the ___domain is restricted to the n-dimensional [[hypercube]] <math>[0,1]^n</math>, the polynomial <math>f^*(x): [0,1]^n \rightarrow [0,1]</math> gives the probability of a positive outcome when the Boolean function ''f'' is applied to ''n'' independent random ([[Bernoulli distribution|Bernoulli]]) variables, with individual probabilities ''x''. A special case of this fact is the [[piling-up lemma]] for [[
=== 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 (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 and [[Parity function|linear functions]] are [[
==Applications==
Boolean functions play a basic role in questions of [[Computational complexity theory|complexity theory]] as well as the design of processors for [[digital computer]]s, where they are implemented in electronic circuits using [[
The properties of Boolean functions are critical in [[cryptography]], particularly in the design of [[symmetric key algorithm]]s (see [[substitution box]]).
| |||