Attacks on Public-Key Cryptosystems Based on Free Partially Commutative Monoids and Groups

Françoise Levy-Dit-Vehel 1 Ludovic Perret 2
1 UMA - Unité de Mathématiques Appliquées
2 ALI - Algorithmique, Langage et Information
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.
Document type :
Book sections
Complete list of metadatas
https://hal-ensta-paris.archives-ouvertes.fr//hal-00988804
Contributor : Aurélien Arnoux <>
Submitted on : Friday, May 9, 2014 - 10:41:01 AM
Last modification on : Wednesday, July 3, 2019 - 10:48:04 AM

Links full text

istex

Identifiers

Collections

ENSTA | UMA_ENSTA

Citation

Françoise Levy-Dit-Vehel, Ludovic Perret. Attacks on Public-Key Cryptosystems Based on Free Partially Commutative Monoids and Groups. Progress in Cryptology - INDOCRYPT 2004, 3348, Springer, pp.275-289, 2004, Lecture Notes in Computer Science, 978-3-540-24130-0. ⟨10.1007/978-3-540-30556-9_22⟩. ⟨hal-00988804⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

133

Contact

Informations

CCSD