A zero knowledge identification scheme based on the q-ary SD problem

Abstract : At CRYPTO'93, Stern proposed a 3-pass code-based identification scheme with a cheating probability of 2/3. In this paper, we propose a 5-pass code-based protocol with a lower communication complexity, allowing an impersonator to succeed with only a probability of 1/2. Furthermore, we propose to use double-circulant construction in order to dramatically reduce the size of the public key. The proposed scheme is zero-knowledge and relies on an NP-complete coding theory problem (namely the q-ary Syndrome Decoding problem). The parameters we suggest for the instantiation of this scheme take into account a recent study of (a generalization of) Stern's information set decoding algorithm, applicable to linear codes over arbitrary fields Fq; the public data of our construction is then 4 Kbytes, whereas that of Stern's scheme is 15 Kbytes for the same level of security. This provides a very practical identification scheme which is especially attractive for light-weight cryptography.
Type de document :
Communication dans un congrès
Selected Areas in Cryptography, Aug 2010, Waterloo, Canada. Springer, 6544, pp.171-186, 2011, LNCS. 〈10.1007/978-3-642-19574-7_12〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00674249
Contributeur : Pascal Véron <>
Soumis le : mardi 20 mars 2012 - 10:19:35
Dernière modification le : dimanche 15 octobre 2017 - 22:44:05
Document(s) archivé(s) le : jeudi 21 juin 2012 - 02:21:17

Fichier

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

Identifiants

Collections

Citation

Pierre-Louis Cayrel, Pascal Véron, Sidi Mohamed El Yousfi Alaoui. A zero knowledge identification scheme based on the q-ary SD problem. Selected Areas in Cryptography, Aug 2010, Waterloo, Canada. Springer, 6544, pp.171-186, 2011, LNCS. 〈10.1007/978-3-642-19574-7_12〉. 〈hal-00674249〉

Partager

Métriques

Consultations de la notice

248

Téléchargements de fichiers

367