In this paper, we initiate the study of side-channel leakage in
hash-and-sign lattice-based signatures, with particular emphasis on the
two efficient implementations of the original GPV lattice-trapdoor
paradigm for signatures, namely NIST second-round candidate Falcon and
its simpler predecessor DLP. Both of these schemes implement the GPV
signature scheme over NTRU lattices, achieving great speed-ups over the
general lattice case. Our results are mainly threefold. First, we identify a specific source of side-channel leakage in most
implementations of those schemes. Signing in lattice-based hash-and-sign
schemes involves sampling a lattice point according to a Gaussian
distribution. This reduces to sampling several one-dimensional discrete
Gaussian distributions with standard deviations determined by the
Gram–Schmidt norms of the secret lattice basis. Our observation is that
those norms often leak through timing side-channels in the implementation
of the one-dimensional Gaussian samplers. Second, we elucidate the link between this leakage and the secret key, by
showing that the entire secret key can be efficiently reconstructed
solely from those Gram–Schmidt norms. The result makes heavy use of the algebraic structure
of the corresponding schemes, which work over a power-of-two cyclotomic
field. To establish it, we propose efficient algorithms of independent
interest which, given the leading principal minors of the matrix
associated to a totally positive field element (in the power basis for
DLP and the bit-reversed order basis for Falcon) recover the element up
to conjugation. In the case of those schemes, that element is $f\bar f +
g\bar g$, where $(f,g)$ is the NTRU-style secret key. We then show that this
element combined with the verification key suffices to recover the entire
secret efficiently. Third, we concretely demonstrate the side-channel attack against DLP. The
challenge is that timing information only provides an approximation of
the Gram–Schmidt norms (with an accuracy increasing with the number of
traces), and our algebraic recovery technique needs to be combined with
pruned tree search in order to apply it to approximated values.
Experimentally, we show that around $2^{35}$ DLP traces are enough to
reconstruct the entire key with good probability. Carrying out a similar
experiment against Falcon is left as an open problem, however, since the
recursive nature of our bit-reversed order recovery algorithm does not
accommodate approximate inputs easily. Nevertheless, our results do
underscore the importance of constant time implementations particularly
for schemes using Gaussian sampling.