$\epsilon$ parameter choice in lattice-based schemes

Question

I am trying to implement Pei10 and BB13, but I am confused about what concrete parameters to use.

In Pei10, Algorithm 1 takes a rounding parameter $r = \omega(\sqrt{\log n})$ as parameter, but it does not specify how to choose it concretely. As in, would $r = \sqrt{\log n}$ or $r = 2\sqrt{\log n}$ work, as long as they satisfy the other conditions such as $\Sigma > \Sigma_1 = r^2 \cdot \mathbf{B}_1 \mathbf{B}_1^T$? If someone could explain the intuition behind it it'll be great.

In BB13, looking at the suggested parameter choices in Appendix A.1, they specify that $c = \alpha q > \sqrt{n}$ and $r \geq 2 \cdot \sqrt{\ln \left(2n \left(1 + \frac{1}{\varepsilon^{-1}}\right)\right) / \pi}$, but also does not specify what $\varepsilon$ should be. Even worse(?), in Definition 1 all they say is "For any ... positive real $\varepsilon > 0$, the smoothing parameter $\eta_{\varepsilon}(\Lambda)$ is ..." This definition makes sense but surely doesn't help with implementation. The paper claims to have implemented the scheme but provide no code too :(

Any help with the questions above would be great. If possible, a high level intuition of the signature schemes would be appreciated! These questions might be answered in even earlier papers but I don't know where to look.

Answer 1

The standard results relate $\varepsilon$ with the statistical distance between certain distributions (say, the output of a sampling algorithm and a perfect discrete Gaussian), so a first possible choice is to pick $\varepsilon=2^{-\lambda}$ for $\lambda$ the security parameter (the bit security we are aiming for). This is usually fairly overkill.

Efficient implementations typically rely on finer-grained analysis using Rényi divergence arguments in order to get away with larger $\varepsilon$. Falcon for example uses $\varepsilon\approx 1/\sqrt{Q_s \cdot \lambda} \approx 2^{-36}$ (see just above equation 2.13) where $Q_s = 2^{64}$ is the maximal number of signatures generated with a given key. This is probably the correct order of magnitude for most applications.