Cryptanalysis of a Proposal Based on the Discrete Logarithm Problem Inside Sn

Abstract In 2008, Doliskani et al. proposed an ElGamal-style encryption scheme using the symmetric group S n as mathematical platform. In 2012, an improvement of the cryptosystem’s memory requirements was suggested by Othman. The proposal by Doliskani et al. in particular requires the discrete logarithm problem in S n , using its natural representation, to be hard. Making use of the Chinese Remainder Theorem, we describe an efficient method to solve this discrete logarithm problem, yielding a polynomial time secret key recovery attack against Doliskani et al.’s proposal. View Full-Tex