4
$\begingroup$

I have known that the vector is sampled from Gaussian distribution in lattice-based cryptography because the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ approximates to uniform distribution.

It is proved by below lemma.

For any $s > 0$, $\mathbf{c} \in \mathbb{R}^n$, and lattice $\Lambda(\mathbf{B})$, the statistical distance between $\mathcal{D}_{s,\mathbf{c}} \mod{\mathcal{P}(\mathbf{B})}$ and the uniform distribution over $\mathcal{P}(\mathbf{B})$ is at most $\frac{1}{2} \rho_{1/s}(\Lambda(\mathbf{B})^*\backslash\{\mathbf{0}\})$. In particular, for any $\epsilon >0$ and any $s \geq \eta_{\epsilon}(\mathbf{B})$, the statistical distance is at most $\Delta(\mathcal{D}_{s,\mathbf{c}} \mod{\mathcal{P}(\mathbf{B})},\mathcal{U}(\mathcal{P}(\mathbf{B}))) \leq \epsilon/2$.

But if the vector is sampled from uniform distribution at first, the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ is uniform. So, I thought that Gaussian sampling is not needed for above reason, because Gaussian sampling requires large costs.

Another reason I think is that the smaller vector is preferred because almost lattice problem is about finding short vector and Gaussian variable has higher probability as closer to the center. Is it right?

If my thought is not correct, let me know the reason using Gaussian distribution in lattice-based cryptography.

Improve this question
$\endgroup$
1
  • $\begingroup$ I think it's because one of the original paper written by Regev, the cryptosystem is linked to the LWE problem with a gaussian noise. $\endgroup$
    – Ievgeni
    Commented Aug 13, 2019 at 13:26

1 Answer 1

Reset to default
-2
$\begingroup$

You can't directly sample uniformly modulo a lattice unless you know what the lattice is. The Gaussian distribution can be sampled independently of knowledge of the lattice. This distinction is important in situations where the lattice is part of a cryptographic secret.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Typically, the lattice (at least, one expression of the lattice) is public knowledge. It'd be rather hard for an encryptor to select something near a lattice point if he had no idea where the lattice points were... $\endgroup$
    – poncho
    Commented Aug 12, 2019 at 15:27
  • $\begingroup$ You typically get only a bad basis of the lattice as public knowledge. The resulting vectors get very large, and choosing a uniform distribution mod very large vectors is no easier than using a Gaussian. The vectors also change if the public key varies, whereas there is no need to change the Gaussian depending on the key. $\endgroup$
    – djao
    Commented Aug 12, 2019 at 16:58
  • $\begingroup$ But the algorithms i see use a good basis when they sample vector. In detail, they use the nearest plane algorithm that output the nearest lattice vector from target vector and they output the nearest vector with higher probability than other. (e.g target vector $\mathbf{c}$ is closer lattice vecotr $\mathbf{v}$ than $\mathbf{0}$, the probability outputting $\mathbf{v}$ is larger than $\mathbf{0}$. Can they sample the vector from Gaussian without the basis? Or is the algorithm an exception? Then, why does the algorithm i see sample from Gaussian? $\endgroup$
    – 전소현
    Commented Aug 13, 2019 at 6:26
  • $\begingroup$ Are you talking about decryption algorithms or encryption algorithms? Decryption algorithms typically do not require a Gaussian. $\endgroup$
    – djao
    Commented Aug 13, 2019 at 14:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.