Pitfalls in public key cryptosystems based on free partially commutative monoids and groups

DOI10.1016/J.AML.2005.11.014MaRDI QIDQ2371104zbMATH OpenOpenAlexFDO

Authors Rainer Steinwandt, María Isabel González Vasco

Publication date 29 June 2007

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aml.2005.11.014

zbMATH Keywords

ciphertext only attacksgroupsmonoidspublic key cryptography

Mathematics Subject Classification ID

Cryptography (94A60)

Review text

Public key cryptosystems are usually based on factoring large integers or computing discrete logarithms in suitably represented finite cyclic groups. Two exceptions are the public key schemes proposed by [\textit{P. J. Abisha, D. G. Thomas}, and \textit{K. G. Subramanian}, Progress in cryptology -- INDOCRYPT 2003. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2904, 218--227 (2003; Zbl 1123.94333)], which are based on partially commutative monoids and groups. Pitfalls in these cryptosystems were already considered by [\textit{F. Levy-dit-Vehel} and \textit{Perret}, Progress in cryptology -- INDOCRYPT 2004. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 3348, 275--289 (2004; Zbl 1113.94313)], who described some attacks which, despite being exponential on the size of the public alphabet \(\Delta\), could be fast enough to compromise the use of practical \(\Delta\). In this paper, it is shown that encryption schemes based on free partially commutative monoids are vulnerable to suitable \textit{ciphertext only} attacks as well, which is further evidence that such cryptosystems do not offer acceptable security.

Recommendations

• Progress in Cryptology - INDOCRYPT 2004
• Progress in Cryptology - INDOCRYPT 2003
• scientific article; zbMATH DE number 1618049
• Cryptography and Coding
• A ``factorization algorithm for elements of a symmetric group

Cites work

• A reaction attack on a public key cryptosystem based on the word problem
• Clouds over a public key cryptosystem based on Lyndon words
• scientific article; zbMATH DE number 49145 (Why is no real title available?)
• Progress in Cryptology - INDOCRYPT 2003
• Progress in Cryptology - INDOCRYPT 2004

Cited in

(6)

• Progress in Cryptology - INDOCRYPT 2003
• Completion Attacks and Weak Keys of Oleshchuk’s Public Key Cryptosystem
• Progress in Cryptology - INDOCRYPT 2004
• Monoidal categories, representation gap and cryptography
• Security analysis of word problem-based cryptosystems
• Attacking a public key cryptosystem based on tree replacement

This page was built for publication: Pitfalls in public key cryptosystems based on free partially commutative monoids and groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2371104)