In CRYSTALS-Dilithium module lattice-based digital signatures, the secret key vectors $s_1, s_2$ with coefficients in $[-\eta, \eta]$ and the signature masking vector $y$ with coefficients in $(-\gamma_1, \gamma_1)$ are generated using rejection sampling on a stream of uniformly random bytes obtained from a cryptographically-secure pseudo-random number generator.

  • Since rejection sampling is inherently non-constant-time, why is this not a problem from a timing side-channel leakage point of view?

  • Protocols using discrete Gaussian distributions need to ensure constant-time sampling to prevent side-channel attacks. Why do similar attacks not work when using rejection sampling?

  • 7
    $\begingroup$ The term constant-time is a bit misleading (and I've heard people suggesting say isochronous instead). What is important is that the time and memory access pattern is independent of secret values manipulated. Them being constant is just one way of achieving independence. $\endgroup$
    – LeoDucas
    Apr 2, 2019 at 7:20
  • $\begingroup$ @LeoDucas, your comment seems to be a perfectly valid response to OP's question, perhaps you should post it as an answer instead? $\endgroup$ Apr 4, 2019 at 17:35
  • $\begingroup$ This is merely w warning about the notion at hand. A full fledge response would require me developing in more detail whether Dilithium does achieve this, and, this is not exactly my cup of tea. $\endgroup$
    – LeoDucas
    Apr 5, 2019 at 18:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.