Paper 2023/1628

Cryptanalysis of the Peregrine Lattice-Based Signature Scheme

Xiuhan Lin, School of Cyber Science and Technology, Shandong University, Qingdao, China
Moeto Suzuki, Kyoto University, Kyoto, Japan
Shiduo Zhang, Institute for Advanced Study, Tsinghua University, Beijing, China
Thomas Espitau, PQShield SAS, Paris, France
Yang Yu, Institute for Advanced Study, Tsinghua University, Beijing, China, BNRist, Tsinghua University, Beijing, China, Zhongguancun Laboratory, Beijing, China, National Financial Cryptography Research Center, Beijing, China
Mehdi Tibouchi, Kyoto University, Kyoto, Japan, NTT Social Informatics Laboratories, Tokyo, Japan
Masayuki Abe, Kyoto University, Kyoto, Japan, NTT Social Informatics Laboratories, Tokyo, Japan

The Peregrine signature scheme is one of the candidates in the ongoing Korean post-quantum cryptography competition. It is proposed as a high-speed variant of Falcon, which is a hash-and-sign signature scheme over NTRU lattices and one of the schemes selected by NIST for standardization. To this end, Peregrine replaces the lattice Gaussian sampler in the Falcon signing procedure with a new sampler based on the centered binomial distribution. While this modification offers significant advantages in terms of efficiency and implementation, it does not come with a provable guarantee that signatures do not leak information about the signing key. Unfortunately, lattice based signature schemes in the hash-and-sign paradigm that lack such a guarantee (such as GGH, NTRUSign or DRS) have generally proved insecure. In this paper, we show that Peregrine is no exception, by demonstrating a practical key recovery attack against it. We observe that the distribution of Peregrine signatures is a hidden transformation of some public distribution and still leaks information about the signing key. By adapting the parallelepiped-learning technique of Nguyen and Regev (Eurocrypt 2006), we show that the signing key can be recovered from a relatively small number of signatures. The learning technique alone yields an approximate version of the key, from which we can recover the exact key using a decoding technique due to Thomas Prest (PKC 2023). For the reference implementation (resp. the official specification version) of Peregrine-512, we fully recover the secret key with good probability in a few hours given around 25,000 (resp. 11 million) signature samples.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in PKC 2024
CryptanalysisLattice-based signatureStatistical learningNTRU
Contact author(s)
xhlin @ mail sdu edu cn
suzuki moeto 56f @ st kyoto-u ac jp
zsd19 @ mails tsinghua edu cn
t espitau @ gmail com
yu-yang @ mail tsinghua edu cn
mehdi tibouchi @ ntt com
msyk abe @ ntt com
2024-01-23: revised
2023-10-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiuhan Lin and Moeto Suzuki and Shiduo Zhang and Thomas Espitau and Yang Yu and Mehdi Tibouchi and Masayuki Abe},
      title = {Cryptanalysis of the Peregrine Lattice-Based Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1628},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.