[3] A variety of refinements to the attack have been suggested, including using multiple linear approximations or incorporating non-linear expressions, leading to a generalized partitioning cryptanalysis.
The first is to construct linear equations relating plaintext, ciphertext and key bits that have a high bias; that is, whose probabilities of holding (over the space of all possible values of their variables) are as close as possible to 0 or 1.
The second is to use these linear equations in conjunction with known plaintext-ciphertext pairs to derive key bits.
In the most basic type of block cipher, a substitution–permutation network, analysis is concentrated primarily on the S-boxes, the only nonlinear part of the cipher (i.e. the operation of an S-box cannot be encoded in a linear equation).
This is because it is assumed that the correct partial key will cause the approximation to hold with a high bias.