1
$\begingroup$

I want to concretely understand how exactly choice of error distribution effect the security of KEM in the context of Lattice Based Cryptography.

For example, I would like to know the concrete analysis of CBD used in Kyber. How Kyber justiify the use of CBD from the security point of view.

Could someone please suggest some resources for these kind of analysis?

Thanks

$\endgroup$

1 Answer 1

1
$\begingroup$

As far as I know the idea of using centred binomial distributions within (ring/module) learning with errors problems first arose in the paper Post-quantum key exchange – a new hope. The ur-form of LWE is to consider systems with real error vectors drawn from a continuous Gaussian distribution. One can convert such a set of samples to a discrete Gaussian by rounding and if the discretised Gaussian were attackable, then the attck would transfer to the ur-system.

Error vectors drawn from a centralised binomial could also be sampled from a discrete Gaussian, but with a different probability. If an attack were able to recover an error drawn a centred binomial, the same attack would recover the same instance of a Gaussian, leading to an attack on a large number of cases. The argument can be quantified and the similarity/distinction between errors drawn from CBD vice discretised Gaussian is best measured with Renyi divergence which generalise Kullback-Liebler divergence in the same way that Renyi entropy generalises Shannon entropy. The formal argument can be found in Appendxi B of the New Hope paper.

$\endgroup$
2
  • $\begingroup$ I don't have enough reputation to upvote this. Thank you very much for providing the detailed answer. $\endgroup$ Jan 16 at 14:02
  • $\begingroup$ Note that there are other (more direct) justifications for discrete Gaussians, namely that they are the maximal entropy distribution on $\mathbb{Z}$ of fixed mean and standard deviation. Also, discritizing a continuous Gaussian doesn't really lead to a discrete Gaussian iirc (and instead rounded Gaussians). $\endgroup$
    – Mark Schultz-Wu
    Jan 17 at 18:57

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.