2
$\begingroup$

I am currently learning about lattice-based cryptography and, reading from A Decade of Lattice Cryptography by Peikert, specifically section 2.3, it emerges that

[...] if the parameter s is greater or equal than the smoothing parameter of a lattice, then the sum of independent discrete gaussians (over that lattice) is a discrete gaussian itself.

I am looking for the formal statement (and proof) of that fact without any success. Is anyone able to point me to the appropriate reference?

EDIT: added link to the paper

$\endgroup$
3
  • $\begingroup$ The sentence immediately preceding the claim in the same paragraph lists a bunch of references: "Several works, e.g., ... have shown ..." $\endgroup$
    – Myath
    Sep 28, 2022 at 18:50
  • $\begingroup$ @Myath Unfortunately each reference is very dense and carries a lot of highly non-trivial results. I'm sure that an exhaustive answer is to be found in one or more of the references, but from a first scan of them I did not find a clear statement of the result. I was just wondering if anyone more experienced could help narrowing down the research $\endgroup$
    – Jackmill
    Sep 28, 2022 at 19:23
  • $\begingroup$ This statement (in a more general form) was first proved in web.eecs.umich.edu/~cpeikert/pubs/pargauss.pdf . $\endgroup$ Oct 1, 2022 at 11:34

1 Answer 1

1
$\begingroup$

You mention

Unfortunately each reference is very dense and carries a lot of highly non-trivial results. I'm sure that an exhaustive answer is to be found in one or more of the references, but from a first scan of them I did not find a clear statement of the result.

This can be found in Theorem 4.6 of Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.

$\endgroup$

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.