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 Sn 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 Sn, 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.

Keywords

• cryptanalysis
• symmetric group
• public key encryption