Paper 2023/926

Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme

Nicolas Aragon, Naquidis Center, France
Victor Dyseryn, XLIM, University of Limoges
Philippe Gaborit, XLIM, University of Limoges

We present a new attack against the PSSI problem, one of the three problems at the root of security of Durandal, an efficient rank metric code-based signature scheme with a public key size of 15 kB and a signature size of 4 kB, presented at EUROCRYPT'19. Our attack recovers the private key using a leakage of information coming from several signatures produced with the same key. Our approach is to combine pairs of signatures and perform Cramer-like formulas in order to build subspaces containing a secret element. We break all existing parameters of Durandal: the two published sets of parameters claiming a security of 128 bits are broken in respectively $2^{66}$ and $2^{73}$ elementary bit operations, and the number of signatures required to finalize the attack is 1,792 and 4,096 respectively. We implemented our attack and ran experiments that demonstrated its success with smaller parameters.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in CRYPTO 2023
rank-metriccode-basedpost-quantumdigital signaturescryptanalysis
Contact author(s)
victor dyseryn_fostier @ unilim fr
2023-06-14: approved
2023-06-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Aragon and Victor Dyseryn and Philippe Gaborit},
      title = {Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2023/926},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.