2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer, I will read more about the Rényi divergence. $\endgroup$
    – Gareth Ma
    Sep 27, 2023 at 20:29

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.