Earticle

초록

영어

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+.

목차

Abstract
 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

키워드

저자

• Guodong Sun [ College of Computer Science, Beijing University of Technology, Beijing, China ]
• Shenghui Su [ College of Information Engineering, Yangzhou University, Yangzhou, China ]
• Maozhi Xu [ School of Mathematics Sciences, Peking University, Beijing, China ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Security and Its Applications

• 간기

  격월간

• pISSN

  1738-9976

• 수록기간

  2008~2016

• 등재여부

  SCOPUS

• 십진분류

  KDC 505 DDC 605