Score:1

Why predicting an error in Crystal Kyber is considered to be hard?

om flag

Hi I have started studying on crystal kyber recently. Gained some knowledge regarding its algorithm and how it works. My doubt is why it is tough for attacker to extract secret vector from pk itself by predicting error vector since from pk we know mat_A,t. (B=As+e)

How can the attacker predict error from Gaussian distribution model. And how the error is randomly chosen from the region of high to low probability region of a Gaussian curve.

Score:1
ru flag

The entries in error vectors for Kyber are drawn from a centred binomial distribution based on the difference of two sets of two coin flips. In code this likely means generating two random bits and then another two random bits and subtracting the Hamming weight of the former from the Hamming weight of the latter. This means that errors $\pm 2$ are produced with probability 1/16 each; errors $\pm 1$ are produced with probability 1/4 each and error 0 is produced with probability 3/8.

The most likely error vector for, say, Kyber512 is the all zeros vector which is chosen with probability $0.375^{512}$.

After this the most likely error vectors are the 1024 vectors that have a single $\pm 1$ entry and 511 zeros each of which occur with probability $(0.25)(0.375)^{511}$.

After this the most likely After this the most likely error vectors are the $4\times\binom{512}2$ vectors that have a two $\pm 1$ entries and 510 zeros each of which occur with probability $(0.25)(0.375)^{510}$. And so forth.

Note that even if we only consider error vectors with only 20 $\pm 1$ entries, this is over $2^{128}$ possibilities. Further we expect the typical error vector to have 320 non-zero entries.

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.