P. Santini

Nicolas Aragon, Marco Baldi, Jean-Christophe Deneuville et al.

We present an attack against a code-based signature scheme based on the Lyubashevsky protocol that was recently proposed by Song, Huang, Mu, Wu and Wang (SHMWW). The private key in the SHMWW scheme contains columns coming in part from an identity matrix and in part from a random matrix. The existence of two types of columns leads to a strong bias in the distribution of set bits in produced signatures. Our attack exploits such a bias to recover the private key from a bunch of collected signatures. We provide a theoretical analysis of the attack along with experimental evaluations, and we show that as few as 10 signatures are enough to be collected for successfully recovering the private key. As for previous attempts of adapting Lyubashevsky's protocol to the case of code-based cryptography, the SHMWW scheme is thus proved unable to provide acceptable security. This confirms that devising secure code-based signature schemes with efficiency comparable to that of other post-quantum solutions (e.g., based on lattices) is still a challenging task.

Paolo Santini, Marco Baldi, Giovanni Cancellieri et al.

In this paper we study recent reaction attacks against QC-LDPC and QC-MDPC code-based cryptosystems, which allow an opponent to recover the private parity-check matrix through its distance spectrum by observing a sufficiently high number of decryption failures. We consider a special class of codes, known as monomial codes, to form private keys with the desirable property of having a unique and complete distance spectrum. We verify that for these codes the problem of recovering the secret key from the distance spectrum is equivalent to that of finding cliques in a graph, and use this equivalence to prove that current reaction attacks are not applicable when codes of this type are used in the McEliece cryptosystem.