Public-key Cryptograph Based on the Multi-discrete Logarithm Problem

In this paper, the multi-discrete logarithm problem is formally defined, and the necessary conditions of resistance to the quantum algorithm for the hidden subgroup problem are given. It is more difficult than the discrete logarithm problem. And the number field sieve for the discrete logarithm problem is not suitable for addressing it. Furthermore, the public-key cryptograph is designed against the problem, of which the key amount is small. This paper analyses the principles of parameter selection and proves the correctness of the decryption works. It is critical that different random integers are received to the encrypt different messages.