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

  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.