为什么差分密码分析的复杂度是线性的，概率的倒数是线性的，而线性密码分析是二次型的，而偏置的是逆的？

Question

我试图理解差分密码分析的复杂性和线性密码分析的复杂性。

• 在差分密码分析中，所需文本的数量为\mathcal{O} {\left( \frac{1}{p} \right)}，其中p := Pr(\alpha \to \beta)由于某些差异，\alpha和\beta
• 在线性密码分析中，所需文本的数量为\mathcal{O} {\left( \frac{1}{\epsilon ^ 2} \right)}，其中\epsilon是某些掩码的偏差，即\epsilon = | Pr(\lambda \to \gamma) - 1/2|。

我不明白的是为什么在线性情况下复杂性变成二次型？如果我们将概率用于线性密码分析而不是偏倚，那么为什么复杂度与\frac{1}{Pr(\lambda \to \gamma)}不成比例呢？

我试着阅读Ali Aydın Sel uk关于线性和差分密码分析中成功概率的论文，但我仍然没有直觉。

Answer 1

我不明白的是为什么在线性情况下复杂性变成二次型？

在线性密码分析中，对于每一个输入，我们得到一个0.5 \pm \epsilon的偏差，我们需要确定这个偏差是0.5 + \epsilon还是0.5 - \epsilon。

如果我们要查询一个随机比特(即一个没有偏差的) n时间并对结果进行求和，我们将得到一个值0.5n + \lambda \sqrt{n}，对于一些标准差在11左右的分布\lambda；它将围绕\epsilon^{-2}样本来测量我们试图测量的偏差，以便对系统中固有的\lambda \sqrt{n}噪声进行检测。

这种“我们需要克服系统内部的噪声”的效果在差分密码分析中不会出现，因为在DC中，我们期望差分能保持多个比特，所以我们基本上可以忽略差分在内部不保持的情况，但是差分恰好保持了输出。

实际上，如果我们使用截断微分，这可能不完全正确，在这种情况下，我们可能需要担心假阳性，给我们一个更接近线性密码分析的分析.

1：实际上，标准偏差是0.5；稍微小一点的预期噪声不会改变分析结果。