# Kyber PKE correctness proof, how is triangle inequality used

Im reading the CRYSTALS kyber paper and am stuck on the PKE correctness proof on page 5. I can't see how the triangle inequality would help to get to the result $$|| \lceil q / 2 \rfloor \cdot (m - m') ||_\infty < 2 \cdot \lceil q / 4 \rfloor$$.

They must be using the $$\|a\|-\|b\| \le \|a+b\|$$ variant of the triangle inequality (see Wolfram MathWorld).

For those of you following along, this is all at the end of page 5. They start with the following fact:

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

Apply the triangle inequality that I wrote above (with $$b=w$$), to get:

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

Then move $$\|w\|_\infty$$ to the right hand side, and use the fact that $$\|w\|_\infty < \lceil q/4\rfloor$$ to finally get:

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

• The authors then go on to write that for all odd $q$ it implies that $m = m'$. Why is this the case? Does this follow from a "coefficient comparison"? Nov 9, 2022 at 17:47