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:
- There is no proof of post-quantum security.
- 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?