4
$\begingroup$

The paper “CRYSTALS – Dilithium: Digital Signatures from Module Lattices” (by Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé) introduces a digital signature scheme based on lattices.

However, it worries me for two reasons:

  1. There is no proof of post-quantum security.
  2. There is no proof that the running time does not depend on the secret key.

The first appears to be a technical limitation of the proof technique and unlikely to lead to a practical attack, but the second one is definitely exploitable if my fear is real.

Does the running time actually depend on the secret key?

$\endgroup$
2
$\begingroup$

The running time does not depend on the secret key. All multiplications, additions, and modular reductions can be implemented to be constant-time.

Diving in to the details:

  • The probability of the goto in line 11 of the signing algorithm is independent of $s_1$, $s_2$ (the probability is in equation (4)).
  • The goto in line 13 is also independent of $s_1$, $s_2$ because the use of $s_2$ in line 12 can be replaced with an expression that does not use $s_2$ (as in equation (1) ) in which all variables have distributions independent of $s_1$, $s_2$.
$\endgroup$
  • 1
    $\begingroup$ This is a very interesting point. Could you please elaborate further? Basically, if the rejection probability is independent from the secret key, then does this count as a constant-time implementation? On one hand, for a same signing key, the signing time varies due to rejection sampling. OTOH, for all possible signing keys, this variation stays constant - it's hard to see what useful information is leaked. $\endgroup$ – zhenfei zhang Jul 31 '17 at 14:05
  • 2
    $\begingroup$ @zhenfeizhang Please don't get me wrong, but you've got a perfectly new question there… which I think is worth being asked on its own. You'll most probably earn some reputation via upvotes by asking it too. ;) $\endgroup$ – e-sushi Jul 31 '17 at 14:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.