3
$\begingroup$

How does he end up with this result in his article ?

lemma2

$\endgroup$

1 Answer 1

4
$\begingroup$

This is a type of "Gaussian approximation", assuming the wrong key randomization hypothesis, and given the bias $|p-1/2|$, the success probability depends on the order statistics of the "sample bias" of the various subkey bit guesses.

Let $T_i$ be the number of times the linear approximation is satisfied by subkey guess $k_i,$ and $$Y_i=|(T_i/N)-1/2|,$$ is the sample bias corresponding to this subkey guess ($N$ is the number of plaintext/ciphertext-pairs). Let $k_0$ be the right key guess and let there be $2^m$ subkey values possible, say from $0$ to $2^m-1$.

Then linear cryptanalysis is successful if and only if $$Y_0>Y_i,\quad 1\leq i\leq 2^m-1.$$

This probability is then estimated via a gaussian approximation.

The paper "On Probability of Success in Linear and Differential Cryptanalysis", from the Journal of Cryptology, by A. A. Selcuk available here goes over this in detail.

$\endgroup$

Your Answer

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

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