Boolean function: Difference between revisions

Revision as of 03:18, 12 February 2023

Revision as of 00:06, 20 February 2023

Line 81:

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|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. 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 ouputoutput. 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" />