Content deleted Content added
No edit summary |
Described some cryptanlytical properties |
||
Line 28:
==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.
Line 35:
* [[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 amount 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
Line 65:
== 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|last=Tarannikov|first=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|url=https://link.springer.com/chapter/10.1007/3-540-45682-1_27|journal=Advances in Cryptology — ASIACRYPT 2001|series=Lecture Notes in Computer Science|language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=460–479|doi=10.1007/3-540-45682-1_27|isbn=978-3-540-45682-7}}</ref>
The [[Boolean derivative|''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 [[Walsh transform|''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|Walsh functions]]), analogous to the decomposition of real-valued functions into [[Harmonic|harmonics]] 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; it is related to the Hamming weight of the corresponding subfunction. 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 ouput. 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.<ref>{{Cite journal|last=Canteaut|first=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|doi=10.5555/1756169.1756219|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" />
==Applications==
| |||