Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Cryptanalysis of a code-based one-time signature

Abstract : In 2012, Lyubashevsky introduced a new framework for building lattice-based signature schemes without resorting to any trapdoor (such as GPV [6] or NTRU [7]). The idea is to sample a set of short lattice elements and construct the public key as a Short Integer Solution (SIS for short) instance. Signatures are obtained using a small subset sum of the secret key, hidden by a (large) Gaussian mask. (Information leakage is dealt with using rejection sampling.) Recently, Per-sichetti proposed an efficient adaptation of this framework to coding theory [12]. In this paper, we show that this adaptation cannot be secure, even for one-time signatures (OTS), due to an inherent difference between bounds in Hamming and Euclidean metrics. The attack consists in rewriting a signature as a noisy syndrome decoding problem, which can be handled efficiently using the extended bit flipping decoding algorithm. We illustrate our results by breaking Persichetti's OTS scheme built upon this approach [12]: using a single signature, we recover the secret (signing) key in about the same amount of time as required for a couple of signature verifications.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal-enac.archives-ouvertes.fr/hal-02614017
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mercredi 20 mai 2020 - 15:56:37
Dernière modification le : mardi 4 janvier 2022 - 05:47:03

Fichier

DenGab20.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jean-Christophe Deneuville, Philippe Gaborit. Cryptanalysis of a code-based one-time signature. Designs, Codes and Cryptography, Springer Verlag, 2020, ⟨10.1007/s10623-020-00737-8⟩. ⟨hal-02614017⟩

Partager

Métriques

Consultations de la notice

46

Téléchargements de fichiers

115