# Linear cryptanalysis and number of linear approximations

I try to understand the linear cryptanalysis. Now I am reading as a secondary reference the book "Cryptanalysis of Block Ciphers: A Survey" by Standaert , Piret and Quisquater. In the first step, the authors are saying that there are $(2^n-1)\times(2^m-1)$ linear approximations for a $n$-input vector and a $m$-output vector.

Since a linear approximation is a linear map between $\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m$, should the number of linear approximation not be $2^n\times 2^m$? Or do I miss a part?

I am grateful every help.

Sincerely, Hypertrooper

• Two thoughts. (Sorry not a good day for math) 1. The difference between $2^x-1$ and $2^x$ isn't much for most $x$. 2. If the coefficients of an input bit is zero for all output bits then your linear approximation is definitely not invertible, like a block cipher should be. A similar argument probably applies to the inverse. I'm thinking of an n by m matrix of zeros and ones as a representation of a linear XOR function. A row of all zeros or column of all zeros might correspond the $-\space1$s. There are more non-invertible matrices though, so I think it's just an upper bound. – Future Security May 13 '18 at 17:08

It most likely assumes both $a$ and $b$ are nonzero in $$a \cdot x + b\cdot y.$$ If either are zero, the overall inear approximation will be insensitive to changes in plaintext (respectively ciphertext) making the overal linear expresion useless to mount a linear attack on a multiround cipher, since the idea is to extract subkey bits by using enough known ciphertext plaintext pairs.