On the Wagner-Magyarik cryptosystem

Françoise Levy-Dit-Vehel; Ludovic Perret

doi:10.1007/11779360_25

On the Wagner-Magyarik cryptosystem

Françoise Levy-Dit-Vehel
, Ludovic Perret

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

Original language	English
Title of host publication	Coding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers
Publisher	Springer Verlag
Pages	316-329
Number of pages	14
ISBN (Print)	3540354816, 9783540354819
DOIs	https://doi.org/10.1007/11779360_25
Publication status	Published - 1 Jan 2006
Event	International Workshop on Coding and Cryptography, WCC 2005 - Bergen, Norway Duration: 14 Mar 2005 → 18 Mar 2005

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3969 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Workshop on Coding and Cryptography, WCC 2005
Country/Territory	Norway
City	Bergen
Period	14/03/05 → 18/03/05

Access to Document

10.1007/11779360_25

Cite this

Levy-Dit-Vehel, F., & Perret, L. (2006). On the Wagner-Magyarik cryptosystem. In Coding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers (pp. 316-329). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3969 LNCS). Springer Verlag. https://doi.org/10.1007/11779360_25

@inproceedings{b866d84fc0ec449d83b5a4510af725fc,

title = "On the 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.",

author = "Fran{\c c}oise Levy-Dit-Vehel and Ludovic Perret",

year = "2006",

month = jan,

day = "1",

doi = "10.1007/11779360\_25",

language = "English",

isbn = "3540354816",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "316--329",

booktitle = "Coding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers",

note = "International Workshop on Coding and Cryptography, WCC 2005 ; Conference date: 14-03-2005 Through 18-03-2005",

}

Levy-Dit-Vehel, F & Perret, L 2006, On the Wagner-Magyarik cryptosystem. in Coding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3969 LNCS, Springer Verlag, pp. 316-329, International Workshop on Coding and Cryptography, WCC 2005, Bergen, Norway, 14/03/05. https://doi.org/10.1007/11779360_25

On the Wagner-Magyarik cryptosystem. / Levy-Dit-Vehel, Françoise; Perret, Ludovic.
Coding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers. Springer Verlag, 2006. p. 316-329 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3969 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the Wagner-Magyarik cryptosystem

AU - Levy-Dit-Vehel, Françoise

AU - Perret, Ludovic

PY - 2006/1/1

Y1 - 2006/1/1

N2 - 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.

AB - 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.

U2 - 10.1007/11779360_25

DO - 10.1007/11779360_25

M3 - Conference contribution

AN - SCOPUS:33746737541

SN - 3540354816

SN - 9783540354819

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 316

EP - 329

BT - Coding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers

PB - Springer Verlag

T2 - International Workshop on Coding and Cryptography, WCC 2005

Y2 - 14 March 2005 through 18 March 2005

ER -

On the Wagner-Magyarik cryptosystem

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this