Cryptology ePrint Archive: Report 2021/134
Cryptanalysis of a code-based signature scheme without trapdoors
Marco Baldi and Jean-Christophe Deneuville and Edoardo Persichetti and Paolo Santini
Abstract: In this work, we consider a recent application of coding theory in the context of post-quantum digital signature schemes, and their cryptanalysis. We indeed implement an attack on the recent attempt by Li, Xing and Yeo to produce a code-based signature scheme using the Schnorr-Lyubashevsky approach in the Hamming metric. Differently from other (unsuccessful) proposals, this new scheme exploits rejection sampling along with dense noise vectors to hide the secret key structure in produced signatures. We show that these measures, besides yielding very slow signing times and rather long signatures, do not succeed in protecting the secret key. We are indeed able to prove the existence of a strong correlation between produced signatures, which ultimately leaks information about the secret key. To support this claim, we use both theoretical arguments and numerical evidences. Finally, we employ such a weakness to mount a full key recovery attack, which is able to recover the secret key after the observation of a bunch of signatures.
Category / Keywords: public-key cryptography / Code-based cryptography; Cryptanalysis; Digital signature; Zero-knowledge identification scheme
Date: received 6 Feb 2021
Contact author: jean-christophe deneuville at enac fr
Available format(s): PDF | BibTeX Citation
Version: 20210210:073206 (All versions of this report)
Short URL: ia.cr/2021/134
[ Cryptology ePrint archive ]