2
$\begingroup$

I am trying to understand the analysis of the complexity of Differential Cryptanalysis versus the complexity of linear cryptanalysis.

  • In differential cryptanalysis the number of required texts is $\mathcal{O} {\left( \frac{1}{p} \right)}$ where $p := Pr(\alpha \to \beta)$ for some differences $\alpha$ and $\beta$

  • In linear cryptanalysis the number of required texts is $\mathcal{O} {\left( \frac{1}{\epsilon ^ 2} \right)}$ where $\epsilon$ is the bias of some masks, i.e. $\epsilon = | Pr(\lambda \to \gamma) - 1/2|$

What I don’t get is why the complexity became quadratic in linear case? e.g. what if we used the probabilities in linear cryptanalysis instead of biases, why the complexity is not proportional to $\frac{1}{Pr(\lambda \to \gamma)}$.

I tried to read Ali Aydın Selçuk’s paper On Probability of Success in Linear and Differential Cryptanalysis but I still don’t have an intuition why.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

What I don’t get is why the complexity became quadratic in linear case?

Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that bias is $0.5 + \epsilon$ or whether it is $0.5 - \epsilon$

If we were to query a random bit (that is, one with no bias) $n$ times and sum the results, we're going to get a value $0.5n + \lambda \sqrt{n}$, for some distribution $\lambda$ with a standard deviation around 1 [1]; it'll take around $\epsilon^{-2}$ samples for the bias that we're trying to measure to be detectable over the $\lambda \sqrt{n}$ noise that's inherent in the system.

This 'we need to get over the noise within the system' effect doesn't occur with differential cryptanalysis, because in DC, we expect the differential to hold over a number of bits, and so we can essentially ignore the case that the differential didn't hold internally, but the differential just happened to hold on the output.

Actually, if we're working with a truncated differential, this may not be quite as true, and in that case, we may need to worry about false positives, giving us an analysis that's closer to the linear cryptanalysis case...

[1]: Actually, the standard deviation is $0.5$; the slightly smaller expected amount of noise doesn't change the analysis.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This intuitionally is clear, thank you! Would you please give a pointer to how do I reproduce the analysis more rigorously? E.g. The presence of $\sqrt{n}$ in $0.5n + \lambda \sqrt{n}$. Also, would you please explain the point where you mentioned “and so we can essentially ignore the case that the differential didn't hold internally” don’t we always ignore the inner states and focus on the output? $\endgroup$
    – sbox
    Mar 24, 2021 at 15:32
  • $\begingroup$ @sbox: as for the $\sqrt{n}$, see the Central Limit Theorem en.wikipedia.org/wiki/Central_limit_theorem $\endgroup$
    – poncho
    Mar 24, 2021 at 16:30
  • $\begingroup$ @sbox: as for differential cryptanalysis, well, when we find an input/output pair that is consistent with the differential, we assume that the differential models exactly what happened within the cipher (e.g. if the differential would hold only if a specific subkey bit was a 1, well, we just learned that specific subkey bit); if the differential didn't work internally (and so the outputs were independent and just happen to come up with expected differential), such an assumption wouldn't be true; however that's such a low probability event that we ignore that $\endgroup$
    – poncho
    Mar 24, 2021 at 16:34

Your Answer

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