Improved Identification Schemes Based on Error-Correcting Codes

Abstract : As it is often the case in public-key cryptography, the first practical identification schemes were based on hard problems from number theory (factoring, discrete logarithms). The security of the proposed scheme depends on an NP- complete problem from the theory of error correcting codes: the syndrome decoding problem which relies on the hardness of decoding a binary word of given weight and given syndrome. Starting from Stern's scheme [18], we define a dual version which, unlike the other schemes based on the SD problem, uses a generator matrix of a random linear binary code. This allows, among other things, an improvement of the transmission rate with regards to the other schemes. Finally, by using techniques of computation in a finite field, we show how it is possible to considerably reduce: -- the complexity of the computations done by the prover (which is usually a portable device with a limited computing power), -- the size of the data stored by the latter.
Type de document :
Article dans une revue
Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 1997, 8 (1), 〈10.1007/s002000050053〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00680477
Contributeur : Pascal Véron <>
Soumis le : mardi 20 mars 2012 - 11:07:42
Dernière modification le : mardi 9 juin 2015 - 17:28:59
Document(s) archivé(s) le : jeudi 21 juin 2012 - 02:22:33

Fichier

gsdscheme.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Pascal Véron. Improved Identification Schemes Based on Error-Correcting Codes. Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 1997, 8 (1), 〈10.1007/s002000050053〉. 〈hal-00680477〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

221