3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\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
    Commented May 13, 2018 at 17:08

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.