On the Security of MOR Public Key Cryptosystem

摘要

For a finite group G to be used in the MOR public key cryp-tosystem, it is necessary that the discrete logarithm problem(DLP) over the inner automorphism group Inn(G) of G must be computationally hard to solve. In this paper, under the assumption that the special con-jugacy problem of G is easy, we show that the complexity of the MOR system over G is about log |G| times larger than that of DLP over G in a generic sense. We also introduce a group-theoretic method, called the group extension, to analyze the MOR cryptosystem. When G is considered as a group extension of H by a simple abelian group, we show that DLP over Inn(G) can be 'reduced' to DLP over Inn(H). On the other hand, we show that the reduction from DLP over Inn(G) to DLP over G is also possible for some groups. For example, when G is a nilpo-tent group, we obtain such a reduction by the central commutator attack.