Attacks on public key cryptosystems based on free partially commutative monoids and groups

Françoise Levy-dit-Vehel; Ludovic Perret

doi:10.1007/978-3-540-30556-9_22

Attacks on public key cryptosystems based on free partially commutative monoids and groups

Françoise Levy-dit-Vehel, Ludovic Perret

Research output: Contribution to journal › Article › peer-review

Abstract

At INDOCRYPT 2003, Abisha, Thomas and Subramanian have proposed a public key encryption scheme and a zero-knowledge authentication protocol based on the word problem on monoids, as well as a group variant of these systems. We here present a total break attack on each of the two encryption schemes. The complexity bounds of our algorithms show that these schemes are insecure for practical parameter sizes. In the monoid setting, we go one step further by proposing an algorithm that breaks the NP-hard problem underlying both the encryption scheme and the zero-knowledge protocol, as well as an upper bound on its complexity.

Original language	English
Pages (from-to)	275-289
Number of pages	15
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3348
DOIs	https://doi.org/10.1007/978-3-540-30556-9_22
Publication status	Published - 1 Jan 2004

Keywords

Finitely presented groups
Free partially commutative monoids
Homomorphic mappings
Public key cryptanalysis
Thue systems
Word problem

Access to Document

10.1007/978-3-540-30556-9_22

Cite this

@article{f77222045d474d788ae76166c6fa0ef6,

title = "Attacks on public key cryptosystems based on free partially commutative monoids and groups",

abstract = "At INDOCRYPT 2003, Abisha, Thomas and Subramanian have proposed a public key encryption scheme and a zero-knowledge authentication protocol based on the word problem on monoids, as well as a group variant of these systems. We here present a total break attack on each of the two encryption schemes. The complexity bounds of our algorithms show that these schemes are insecure for practical parameter sizes. In the monoid setting, we go one step further by proposing an algorithm that breaks the NP-hard problem underlying both the encryption scheme and the zero-knowledge protocol, as well as an upper bound on its complexity.",

keywords = "Finitely presented groups, Free partially commutative monoids, Homomorphic mappings, Public key cryptanalysis, Thue systems, Word problem",

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

year = "2004",

month = jan,

day = "1",

doi = "10.1007/978-3-540-30556-9\_22",

language = "English",

volume = "3348",

pages = "275--289",

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

issn = "0302-9743",

}

Attacks on public key cryptosystems based on free partially commutative monoids and groups. / Levy-dit-Vehel, Françoise; Perret, Ludovic.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 3348, 01.01.2004, p. 275-289.

Research output: Contribution to journal › Article › peer-review

TY - JOUR

T1 - Attacks on public key cryptosystems based on free partially commutative monoids and groups

AU - Levy-dit-Vehel, Françoise

AU - Perret, Ludovic

PY - 2004/1/1

Y1 - 2004/1/1

N2 - At INDOCRYPT 2003, Abisha, Thomas and Subramanian have proposed a public key encryption scheme and a zero-knowledge authentication protocol based on the word problem on monoids, as well as a group variant of these systems. We here present a total break attack on each of the two encryption schemes. The complexity bounds of our algorithms show that these schemes are insecure for practical parameter sizes. In the monoid setting, we go one step further by proposing an algorithm that breaks the NP-hard problem underlying both the encryption scheme and the zero-knowledge protocol, as well as an upper bound on its complexity.

AB - At INDOCRYPT 2003, Abisha, Thomas and Subramanian have proposed a public key encryption scheme and a zero-knowledge authentication protocol based on the word problem on monoids, as well as a group variant of these systems. We here present a total break attack on each of the two encryption schemes. The complexity bounds of our algorithms show that these schemes are insecure for practical parameter sizes. In the monoid setting, we go one step further by proposing an algorithm that breaks the NP-hard problem underlying both the encryption scheme and the zero-knowledge protocol, as well as an upper bound on its complexity.

KW - Finitely presented groups

KW - Free partially commutative monoids

KW - Homomorphic mappings

KW - Public key cryptanalysis

KW - Thue systems

KW - Word problem

U2 - 10.1007/978-3-540-30556-9_22

DO - 10.1007/978-3-540-30556-9_22

M3 - Article

AN - SCOPUS:33745211763

SN - 0302-9743

VL - 3348

SP - 275

EP - 289

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

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

ER -

Attacks on public key cryptosystems based on free partially commutative monoids and groups

Abstract

Keywords

Access to Document

Fingerprint

Cite this