The design of a large number of cryptographic primitives is based on the intractability of the traditional discrete logarithm problem (tDLP). However, the well known quantum algorithm of P. Shor  solves the tDLP in polynomial time, thus rendering all cryptographic schemes based on tDLP ineffective, should quantum computers become a practical reality. In  M. Sramka et al. generalize the DLP to arbitrary finite groups. The DLP for a non-abelian group is based on a particular representation of a chosen family of groups, and a choice of a class of generators for these groups. In this paper we show that for PSL(2, p) = 〈α, β〉, p an odd prime, certain choices of generators (α, β) must be avoided to insure that the resulting generalized DLP is indeed intractable. For other types of generating pairs we suggest possible cryptanalytic attacks, reducing the new problem to the earlier case. We note however that the probability of success is asymptotic to 1/p as p → ∞. The second part of the paper summarizes our successful attack of the SL(2, 2n) based Tillich Zémor cryptographic hash function , and show how to construct collisions between palindromic strings of length 2n + 2.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com