Walsh-Hadamard-transformatie
Een snelle transformatie die de correlatie met alle lineaire functies tegelijk berekent, en het werkpaard achter een groot deel van de lineaire cryptanalyse.
Een booleaanse functie van n invoeren wordt gegeven als een vector van 2n waarden, en de transformatie levert een vector van dezelfde grootte op waarin elke waarde aangeeft hoe sterk de functie met één bepaalde lineaire functie correleert. Naïef kost dat 22n bewerkingen. De snelle variant, die op een FFT lijkt, doet het in n·2n.
De naam komt van Jacques Hadamard en Joseph Walsh, die tussen eind 19e en begin 20e eeuw beiden aan orthogonale stelsels werkten. Bij S-box-analyse is het het dagelijkse gereedschap om de sterkste lineaire benaderingen te vinden. Wie de berekening ooit zonder heeft gedaan, weet precies waarom het bestaat.