4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 6
    $\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 '19 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$ – Geoffroy Couteau Apr 4 '19 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 '19 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.