I'm new to lattices. According to Lattice Signatures and Bimodal Gaussians in the Rejection Sampling section. In Schnorr, GQ you can simply commit to $y$, use it to hide a secret key $s$. But this doesn't work in lattices. You need to hide the secret key with a small $y$. Turns out, a lot of old lattice-based signatures leaked a part of the secret keys. Instead, we must choose y from a narrow distribution and then perform rejection sampling so that $s$ is not leaked when we add $y$ to it.


  1. What does there mean to be a narrow distribution?
  2. What does it mean for $y$ to be small?
  3. Why is this a problem in lattices specifically?

1 Answer 1

  1. Narrow means that, with high probability, the ouput of the distribution is is small.
  2. Small is meant in the sense of the Euclidean norm of a vector in the Euclidean space $\mathbb R^n$. More concretly, $v$ is informally said small to mean $\|v\| \leq B$ for some value $B > 0$ chosen large enough for a given scheme to work out, but small enough for the lattice problem SIS to remain hard.
  3. It is not a problem outside lattice based crypto because in a finite group $G$, if $x \in G$ is uniform, so is $x+c$. We can't simply do that over an unbounded space such as $\mathbb R^n$.

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.