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$.


1 Answer 1


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. $$

  • $\begingroup$ 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"? $\endgroup$
    – P_Gate
    Nov 9, 2022 at 17:47

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.