# $\epsilon$ parameter choice in lattice-based schemes

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.

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.