Join Log in
Score:1
Eeme avatar Crypto

Kyber PKE correctness proof, how is triangle inequality used

cn flag
Eeme

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

54
1 + 0
Score:5
avatar Crypto
us flag
Mikero

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

0 + 0
P_Gate avatar
mq flag
P_Gate
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"?
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.