On Wagner-Magyarik Cryptosystem

Abstract : We investigate a monoid variant of the scheme based on the word problem on groups proposed by Wagner and Magyarik at Crypto'84, that has the advantage of being immune to reaction attacks so far. We study the security of this variant. Our main result is a complexity-theoretic one: we show that the problem underlying this cryptosystem, say WM, is NP-hard. We also present an algorithm for solving WM. Its complexity permits to shed light on the size of the parameters to choose to reach a given level of security.
Type de document :
Article dans une revue
Lecture notes in computer science, springer, 2006, 3969, pp.316-329. 〈10.1007/11779360_25〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00978821
Contributeur : Aurélien Arnoux <>
Soumis le : lundi 14 avril 2014 - 17:18:07
Dernière modification le : mercredi 6 décembre 2017 - 16:46:10

Identifiants

Collections

Citation

Françoise Levy-Dit-Vehel, Ludovic Perret. On Wagner-Magyarik Cryptosystem. Lecture notes in computer science, springer, 2006, 3969, pp.316-329. 〈10.1007/11779360_25〉. 〈hal-00978821〉

Partager

Métriques

Consultations de la notice

303