Paper 2019/715

On Security of Fiat-Shamir Signatures over Lattice in the Presence of Randomness Leakage

Yuejun Liu and Yongbin Zhou and Shuo Sun and Tianyu Wang and Rui Zhang

Abstract

Leakage during the signing process, including partial key exposure and partial (or complete) randomness leakage, may be devastating for the security of digital signatures. In this work, we consider the security of lattice-based Fiat-Shamir signatures in the presence of randomness leakage. Based on a connection with the ILWE problem introduced by Bootle et al. at Asiacrypt 2018, we show that the key recovery attack with partial randomness leakage can be reduced to a variant of ILWE (We call it FS-ILWE in this work). The ILWE problem is the problem of recovering the secret vector ${\bf s}$ given polynomially many samples of the form $({\bf a}, \langle {\bf a}, {\bf s} \rangle + e)$ and is proven solvable if the error $e$ is not superpolynomially larger than the inner product $\langle {\bf a}, {\bf s} \rangle$, whereas in the FS-ILWE ${\bf a}$ is a sparse vector with a fixed number of non-zero elements, which is either $1$ or $-1$. With one nice probability property that the expectation and covariance of any two coefficients of ${\bf a}$ are zeros, we show that FS-ILWE can also be solved in polynomial time. Consequently, many lattice-based Fiat-Shamir signatures can be totally broken with only one bit leakage of randomness per signature. Our attack has been validated by conducting a series of experiments on two efficient NIST PQC submissions, Dilithium and qTESLA. The results indicate that the secret key of Dilithium and qTESLA can be recovered within seconds by running our method on an ordinary PC desktop.