Cryptology ePrint Archive: Report 2002/070

Weak Keys in MST1

Jens-Matthias Bohli and Maria Isabel Gonzalez Vasco and Consuelo Martinez and Rainer Steinwandt

Abstract: The public key cryptosystem $MST_1$ has been introduced in~\cite{MaStTr00}. Its security relies on the hardness of factoring with respect to wild logarithmic signatures. To identify `wild-like' logarithmic signatures, the criterion of being totally-non-transversal has been proposed.

We give tame totally-non-transversal logarithmic signatures for the alternating and symmetric groups of degree $\ge 5$. Hence, basing a key generation procedure on the assumption that totally-non-transversal logarithmic signatures are `wild like' seems critical. We also discuss the problem of recognizing `weak' totally-non-transversal logarithmic signatures, and demonstrate that another proposed key generation procedure based on permutably transversal logarithmic signatures may produce weak keys.

Category / Keywords: public-key cryptography / logarithmic signatures, group based cryptography, MST1

Date: received 31 May 2002

Contact author: mvasco at orion ciencias uniovi es

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20020603:184031 (All versions of this report)

Short URL: ia.cr/2002/070

Discussion forum: Show discussion | Start new discussion