Breaking the Peregrine Signature Scheme

[Xiuhan Lin]

Dear all,

We would like to share our cryptanalytic results on the Peregrine signature scheme, now available on the IACR eprint archive at the following URL: https://eprint.iacr.org/2023/1628.

This paper is a follow-up on the preliminary annoucement of Peregrine's vulnerability to statistical learning attack that we made back in January ( https://groups.google.com/g/kpqc-bulletin/c/B4cFSHYcwiY ). The paper presents a complete analysis of this security flaw, as well as improvements of the original attack strategy based on lattice decoding techniques. We mount practical key recovery attacks against both the reference implementation and the specification versions of Peregrine (which, as noted in our earlier email, differ substantially). Concretely, for the reference implementation (resp. specification) of Peregrine-512, we fully recover the signing key with good probability in a few hours given around 25,000 (resp. 11 million) signatures.

It has come to our attention that Prof. Kwangjo Kim (whom we thank for his enthusiasm regarding this result) mistakenly shared a preliminary version of this work not meant for public dissemination in a recent message to the kpqc bulletin ( https://groups.google.com/g/kpqc-bulletin/c/UExquYvUNyg ). Please refer instead to the version now available on eprint. In addition, you can find our attack code on GitHub at: https://github.com/lxhcrypto/Peregrine_attack.


Best regards,

Xiuhan Lin, Moeto Suzuki, Shiduo Zhang, Thomas Espitau, Yang Yu, Mehdi Tibouchi, and Masayuki Abe.