Paper 2023/926
Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme
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
-
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}
}
