8
$\begingroup$

Short version: how is it possible to round a continuous Gaussian into a true discrete Gaussian (usually denoted $\mathcal{D}_{\mathbb{Z},\alpha q}$)? The goal is to obtain a reduction from continuous LWE to a true-discrete LWE and combine it with the reduction from $\textsf{GapSVP}_\gamma$ to continuous LWE.

Longer version: in [Reg05], the discrete Gaussian they consider (denoted $\bar{\Psi}_\alpha$, or sometimes $\lfloor\mathcal{D}_{\alpha q}\rceil$) for the noise is a "strange Gaussian": it is obtainable from a continuous Gaussian of parameter $\alpha q$ that you just round to the nearest integer modulo $q$. They also prove that if you can solve continuous LWE, you can solve $\textsf{GapSVP}_\gamma$. In order to also prove the security of LWE with this strange discrete Gaussian, they explain a trivial reduction from continuous LWE to this "strange discrete" LWE: if you can solve the "strange discrete" LWE, you can solve the continuous LWE problem by just rounding your samples to the nearest integer, and call the discrete oracle on these samples. So the hardness goes like this:

$$\text{strange discrete LWE} \leftarrow \text{continuous LWE} \leftarrow \textsf{GapSVP}_\gamma$$

However, if I understand correctly, this Gaussian is not a "real Gaussian", and people prefer to use instead a "true discrete Gaussian" like [MP12] (I guess it has better mathematical properties when you want more involved properties, like bounds on singular values). But then, it is not possible to use in the same way the [Reg05] result to prove the hardness of "true-discrete" LWE, since we can't anymore turn a continuous distribution into a true-discrete one.

So what is the usual way to do this rounding to obtain the following reduction? $$\text{true discrete LWE} \leftarrow \text{continuous LWE}$$ This paper [GMPW20] suggests that [Pei10] solves this problem... but I can't find where.

Also, is there a reduction that directly does:

$$\text{true discrete LWE} \leftarrow \text{GapSVP}_\gamma$$

without transiting via the discrete case?

References

[MP12] Trapdoor for Lattices: Simpler, Tighter, Faster, Smaller, Micciancio, Peikert.

[GPV08] How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Construction, Gentry, Peikert, Vaikuntanathan.

[Pei10] An Efficient and Parallel Gaussian Sampler for Lattices, Peikert.

[MW17] Gaussian sampling over the integers: Efficient, generic,constant-time, Micciancio, Walter.

[HSL17] Rounded Gaussians, Hülsing, Lange, Smeets.

[GMPW20] Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography, Genise, Micciancio, Peikert, Walter.

Bonus: Additional unrelated information: Out of curiosity, what is the current state of the art on the sampling over $\mathcal{D}_{\mathbb{Z},\alpha q}$? Is there any exact sampling method? And what is the recommended method to program that kind of sampling, which is both simple to program and not too inefficient in practice? For now I saw that Section 4.1 of [GPV08] gives a simple rejection sampling method to approximate a sample of a true discrete Gaussian. It was later improved in [Pei10], which is a bit more complex. I just saw [MW17], I need to check what it actually does.

-- EDIT --

I'm also quite confused why people like "true discrete Gaussians" that much: people may say "the sum of two discrete Gaussians is a discrete Gaussian". Fair enough. But you could always say for "strange Gaussians" that rounding a continuous Gaussian makes the problem more complicated compared to the initial continuous Gaussian: so in the proof, you can always say "Let's replace the strange Gaussian with a continuous Gaussian", and now we analyse the attacks on this new protocol: and now, we do have this nice property that the sum of two continuous Gaussians is a continuous Gaussian. And strange discrete Gaussians also seem to be more efficient [HSL17] to sample than true discrete Gaussians, so what's the benefit? Would you have an example of application in which this true discrete Gausian is really required?

For instance, [MP12] uses these true Gaussian, but the search to decision reduction from [MP12] is formulated for continuous Gaussians. The only theorem I can see (I did not checked the last section "Applications") that could actually requires true Gaussian would be Lemma 2.9 which bounds singular values of $\mathbf{R}$ (required for correctness). However, the theorem is true for any $\delta$-subgaussian distribution, so I would expect the strange Gaussian to also be $\delta$-subgaussian for some reasonable $\delta$, and since for true discrete Gaussian they obtain a value for $C$ only empirically, I guess there is chances that this can also be done for strange Gaussians.

$\endgroup$

2 Answers 2

4
$\begingroup$

To answer your first short question: this is a (very) special case of Theorem 3.1 of Peikert’10. Specifically, use the “$x_2$ is chosen from a continuous Gaussian” variant, let $\Lambda_1+c_1$ be the integer lattice $\mathbb{Z}$, and let $\Sigma, \Sigma_1, \Sigma_2$ be suitable positive reals.

Regarding why true discrete Gaussians are useful: it is often because they allow us to prove what we want, either for functionality (e.g., nice singular values) or security. For the latter it is not enough to just say that known attacks (seem to) become “more complicated” with rounded Gaussians; we have to prove that the rounding can’t be exploited in any way. For example, many proofs need to properly simulate a specific distribution that is used in the real system. Using true discrete Gaussians often makes this possible, whereas it’s not as clear how to do it with rounded ones.

$\endgroup$
15
  • 1
    $\begingroup$ Thank you very much, it was super useful! I was trying to see how the section "Randomized Rounding" could help me, but in fact it was the previous section on convolved discrete Gaussians! So I tried to redo the proof (at least for my use case, which is, for references, the marginal distribution of continuous $x_2$), and everything is much clearer now (in that case we even get a better statistical distance of $2 \varepsilon$ if I understood correctly). However, I still want to double check some things with you (see next comments): $\endgroup$ Mar 10, 2021 at 0:33
  • 1
    $\begingroup$ Your first two sentences look correct to me, from a brief glance. Is there a typo in your third (parenthetical) sentence?: $sI$ and $s$ are equivalent under this notation. I am not sure what you’re asking in the fourth sentence. (Also, for your first comment: yes, I think you can get a better statistical distance in this context of randomly rounding a continuous Gaussian.) $\endgroup$ Mar 10, 2021 at 0:48
  • 1
    $\begingroup$ The squared Gaussian parameter will indeed increase by $s_1^2$, which is lower bounded by the squared smoothing parameter of $\mathbb{Z}$. However, this extra amount will be significantly smaller than the error param of the LWE samples produced by the reduction from GapSVP, so it should not be much of a concern. As for a better way to reduce GapSVP to LWE-with-discrete-Gaussian-error, I think it is possible to replace the “continuous smoothing noise” in Regev’s reduction with this kind of Gaussian randomized rounding. I don’t have a proof written but it should go similarly to my Thm 3.1. $\endgroup$ Mar 10, 2021 at 0:58
  • 1
    $\begingroup$ The notations do indeed match. You can prove the statement you wrote (for any positive real $\alpha$) directly from the definition of smoothing parameter, and the fact that the dual lattice scales down by $\alpha$ when the primal lattice scales up by $\alpha$. $\endgroup$ Mar 10, 2021 at 1:03
  • 1
    $\begingroup$ The statement doesn’t concern computational complexity, it’s just about probability—in this case, the distribution of $x_2$ given $x_1$. This can indeed be useful for certain proofs. We use it in a separate paper about bi-deniable encryption, for example. However, the conditional distribution of $x_2$ given some $x_1$ may be easy to sample, depending on the lattice dimension and whether one has a suitable trapdoor for $\Lambda_2$. $\endgroup$ Mar 10, 2021 at 12:11
4
$\begingroup$

Out of curiosity, what is the current state of the art on the sampling over $D_{\mathbb{Z},\alpha q}$

This is a fairly involved question to answer. There are a number of competing ways to sample it, which you can roughly divide into:

  1. Techniques that work for any probability distribution
  2. Techniques that are specific to the discrete Gaussian

Table 1 of [MW17] discusses some sampling methods. Michael Walter's paper *Sampling the Integers with Low Relative Error surveys a few of the methods as well, so maybe a good resource. There are more though. In particular, I also know of:

  1. The polar sampler

  2. The Conditional Density Sampler

There are additionally many different things one can do to optimize things like rejection sampling. I remember this paper about the NIST PQC candidate Falcon, but I believe there have been more recent attempts to make rejection sampling "constant time" [1] that I do not recall offhand.

There are also quite simple things one can do depending on the particular application. I have seen people mention that for encryption, $\mathcal{D}_{\sigma,\mathbb{Z}}$ is the wrong distribution to look at, and one can instead sample from distributions such as $\mathsf{Binom}(n, p)$ for suitable $p$. This is vaguely like a discrete gaussian (light-tailed, centered, etc), but much easier to sample from. This optimization only works for encryption and not signatures though [2].

Is there any exact sampling method?

There are many. Karney's method is probably the closest to what one means by "an exact sampling method", although things like Knuth-Yao sampling also fit into that description. One cannot exactly sample from a distribution of infinite support in worst-case constant time, so exact sampling methods are not particularly useful in practice. The particulars of Karney's method mean that in spite of this it is "almost" an exact sampling method even in that model. Karney's paper explains this fairly well, for example here is the abstract:

An algorithm for sampling exactly from the normal distribution is given. The algorithm reads some number of uniformly distributed random digits in a given base and generates an initial portion of the representation of a normal deviate in the same base. Thereafter, uniform random digits are copied directly into the representation of the normal deviate. Thus, in contrast to existing methods, it is possible to generate normal deviates exactly rounded to any precision with a mean cost that scales linearly in the precision. The method performs no extended precision arithmetic, calls no transcendental functions, and, indeed, uses no floating point arithmetic whatsoever; it uses only simple integer operations. It can easily be adapted to sample exactly from the discrete normal distribution whose parameters are rational numbers.

I think the cost of the initial portion is not constant (so the algorithm is not "a constant-time algorithm + pasting uniformly random bits at the end of the output), but this is still a suitably different result than other "exact" samplers that it is worth pointing out.

[1] Constant-time is a misnomer, what one really wants is that the timing distribution is independent of any secrets. I believe the linked Falcon paper (or a different falcon paper) attempts to formalize this through a notion called isochronos algorithms or something along those lines, but this (formal) notion does not yet appear to be widespread.

[2] See this for more details.

$\endgroup$
7
  • $\begingroup$ Thanks a lot for the detailed answer. Thanks for Karnsey's method, it's a bit longer than GPV08 but it's nice that it is exact. I'll also check the other methods, thanks. By any chance do you also have an answer to the first part of my question? $\endgroup$ Mar 7, 2021 at 2:13
  • $\begingroup$ @LéoColisson no, as I have not personally looked that deeply into the underlying reductions. The only thought I have reading the first part is this paper on rounded gaussians, which argues that in certain cases one can use $\lfloor \mathcal{N}_{0,\sigma}\rceil$ instead of $\mathcal{D}_{\sigma,\mathbb{Z}}$ in constructions. $\lfloor \mathcal{N}_{0,\sigma}\rceil$ looks quite similar to your "continuous LWE distribution". I imagine it is different from the distribution in Regev2005, but am not familiar enough with the details to point out differences ... $\endgroup$
    – Mark Schultz-Wu
    Mar 7, 2021 at 2:20
  • $\begingroup$ (does Regev2005 use randomized rounding, or did that come later?) Also note that Regev has recent work defining a continuous LWE problem, where one does not round at all. I doubt this is relevant to your question, but I thought it was worth mentioning as there is a name collision. $\endgroup$
    – Mark Schultz-Wu
    Mar 7, 2021 at 2:22
  • $\begingroup$ Well my problem is not with using $\lfloor\mathcal{D}_{\sigma}\rceil$ (that one is secure for me due to the trivial reduction from continuous LWE that is itself a reduction from GapSVP, which is done in the Regev05), but rather I don't see why $\mathcal{D}_{\mathbb{Z},\sigma}$ is as secure as GapSVP. I checked the CLWE, and indeed it's a different version, where the $s$ and $a$ are continuous, which is basically the oppositve quesiton (I ask can we discretize $e$ with true Gaussian). $\endgroup$ Mar 7, 2021 at 10:44
  • $\begingroup$ I'm not sure exactly what is the randomized rounding you mention, but it could be exactly what I need (I don't think it's used in Regev05): according to [GMPW20] page 3 "If desired, these [continuous] samples can then be randomly rounded to have discrete Gaussian error [Pei10]". However, I don't understand how/where [Pei10] is useful with that respect. $\endgroup$ Mar 7, 2021 at 10: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.