Research Of Transcendental Logarithm Problem Defending Against Quantum Computation Attacks

Quantum computation is a new computation model based on quantum mechanics theory. Many fasten quantum algorithm has been published which means public-key cryptosystems are facing a big impact. Some of classical cryptosystems just like RSA, ECC, ElGamal are considered being unsafe on quantum computer so that a new field called post-quantum cryptography(PQC) was born. PQC mainly do research on building safe public-key cryptosystems on quantum computer. One of the research contents is trying to find new intractable problems against quantum computation, so that we can design new cryptosystems based on those problems.This paper will start from a new intractable problem, known as transcendental logarithm problem(TLP). The author will try to analysis the characteristic of this problem. Combined with those efficiency quantum algorithms including Shor’s algorithm and Grover’s search algorithm, the author will try to improve these algorithms to solve transcendental logarithm problem.During the process of using Grover’s algorithm to solve TLP, the algorithm has been improved as a result of analyzing the characteristic of TLP. The details of new algorithm has been given and its time cost is calling original function f for0.8786*π/4√2~n/K times. Due to the new algorithm can’t solve TLP in polynomial time, we think TLP is safe when facing to Grover’s algorithm.The attempt of using Shor’s algorithm to solve TLP is failed, but the conclusion of the characteristic of problems which can be solved by Shor’s algorithm is given. The reason of why TLP can’t be solved by Shor’s algorithm is briefly introduced after analyzing the characteristic of TLP. And an experiment is designed to prove this viewpoint.Based on these work, the security of the problem defending against quantum computation will be analyzed and then some improvement ideas to transcendental logarithm problem will be proposed.In this paper, the ways to analysis the characteristic of the quantum algorithm, the ideas to improve the quantum algorithm to solve the problem, and the proposals to improve transcendental logarithm problem to against quantum computation can all bring some inspiring significance to quantum computation and post-quantum cryptography.