Paper 2019/715

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

Yuejun Liu, Yongbin Zhou, Shuo Sun, Tianyu Wang, Rui Zhang, and Jingdian Ming

Abstract

Leakages during the signing process, including partial key exposure and partial (or complete) randomness exposure, may be devastating for the security of digital signatures. In this work, we investigate the security of lattice-based Fiat-Shamir signatures in the presence of randomness leakage. To this end, we present a generic key recovery attack that relies on minimum leakage of randomness, and then theoretically connect it to a variant of Integer-LWE (ILWE) problem. The ILWE problem, introduced by Bootle et al. at Asiacrypt 2018, is to recover the secret vector ${\bf s}$ given polynomially many samples of the form $({\bf a}, \langle {\bf a}, {\bf s} \rangle + e) {\color{black}\in \mathbb{Z}^{n+1}}$, and it is solvable if the error $e {\color{black}\in \mathbb{Z}}$ is not superpolynomially larger than the inner product $\langle {\bf a}, {\bf s} \rangle$. However, in our variant (we call the variant FS-ILWE problem in this paper), ${\bf a}{\color{black}\in \mathbb{Z}^{n}}$ is a sparse vector whose coefficients are NOT independent any more, and $e$ is related to ${\bf a}$ and ${\bf s}$ as well. We prove that the FS-ILWE problem can be solved in polynomial time, and present an efficient algorithm to solve it. Our generic key recovery method directly implies that many lattice-based Fiat-Shamir signatures will be totally broken with one (deterministic or probabilistic) bit of randomness leakage per signature. Our attack has been validated by experiments on two NIST PQC signatures Dilithium and qTESLA. For example, as to Dilithium-III of $125$-bit quantum security, the secret key will be recovered within $10$ seconds over an ordinary PC desktop, with about one million signatures. Similarly, key recovery attacks on Dilithium under other parameters and qTESLA will be completed within $20$ seconds and $31$ minutes respectively. In addition, we also present a non-profiled attack to show how to obtain the required randomness bit in practice through power analysis attacks on a proof-of-concept implementation of polynomial addition. The experimental results confirm the practical feasibility of our method.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Randomness leakage attacksFiat-Shamir signatureDilithiumqTESLAILWEthe least squares method
Contact author(s)
liuyuejun @ iie ac cn
History
2020-09-12: revised
2019-06-18: received
See all versions
Short URL
https://ia.cr/2019/715
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/715,
      author = {Yuejun Liu and Yongbin Zhou and Shuo Sun and Tianyu Wang and Rui Zhang and Jingdian Ming},
      title = {On the Security of Lattice-based Fiat-Shamir Signatures in the Presence of Randomness Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2019/715},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/715}},
      url = {https://eprint.iacr.org/2019/715}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.