eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in CRYPTO 2023
Keywords
rank-metriccode-basedpost-quantumdigital signaturescryptanalysis
Contact author(s)
victor dyseryn_fostier @ unilim fr
History
2023-06-14: approved
2023-06-13: received
See all versions
Short URL
https://ia.cr/2023/926
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/926,
      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{https://eprint.iacr.org/2023/926}},
      url = {https://eprint.iacr.org/2023/926}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.