원문정보
초록
영어
Quantum computation is a new computational model based on quantum mechanical principle. Shor invented the polynomial time algorithms for the prime factorization and discrete logarithm problem, which indicated that the cryptosystems based on them are totally unsafe in the quantum world. Grover constructed an algorithm that finds a solution in only O(2n)steps whereas the exhaustive search algorithm needs O(2n) steps on average. In this paper we investigate the cryptanalysis of a new cryptography problem----multivariate permutation problem (MPP), which could be used to design public-key cryptosystem, with the help of the two quantum algorithms. Specially, we discuss the strength of a private key of the REESSE1+ public-key cryptosystem, whose security is based on the hardness of MPP. Besides, some suggestions are also given about the implementation of the REESSE1+.
목차
1. Introduction
2. The MPP and the REESSE1+
2.1. Some Definitions
2.2. The MPP and REESSE1+
3. Shor’s Algorithm and Grover’s Algorithm
3.1. Shor’ Algorithm
3.2. Grover’s Algorithm
4. Attack by a Single Ci
4.1. The Attack Algorithm
4.2. The Running Time and Success Rate
5. Attack by Eliminating W Through ℓ(xi)+ ℓ(xj) = ℓ(ym)+ ℓ(yn)
6. Eliminating W through ||W||-th Power
7. Attack when W or δ is Revealed
7.1. When W is Revealed
7.2. When δ is Revealed
8. Impact on the REESSE1+
Acknowledgements
References