Kyber PKE正确性证明，三角形不等式是如何使用的

Question

我正在读晶体基伯纸，被卡在第5页的PKE正确性证明上。我看不出三角形不等式会如何帮助得到结果|| \lceil q / 2 \rfloor \cdot (m - m') ||_\infty < 2 \cdot \lceil q / 4 \rfloor。

Answer 1

它们必须使用三角形不等式的\|a\|-\|b\| \le \|a+b\|变体(参见Wolfram MathWorld)。

对于那些跟随的人来说，这一切都在第5页的末尾，他们从以下事实开始：

\bigl\| w + \lceil q/2 \rfloor \cdot m - \lceil q/2 \rfloor \cdot m' \bigr\|_\infty \le \lceil q/4 \rfloor.

应用我上面写的三角形不等式(用b=w)，得到：

-\bigl\| w \bigr\|_\infty + \bigl\| \lceil q/2 \rfloor \cdot m - \lceil q/2 \rfloor \cdot m' \bigr\|_\infty \le \lceil q/4 \rfloor.

然后将\|w\|_\infty移到右侧，并使用\|w\|_\infty < \lceil q/4\rfloor最终获得：

\bigl\| \lceil q/2 \rfloor \cdot m - \lceil q/2 \rfloor \cdot m' \bigr\|_\infty < 2 \lceil q/4 \rfloor.