基于多离散对数问题的公钥密码

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.