文章基本信息

标题：Quantum Cryptanalysis of Multivariate Permutation Problem
本地全文：下载
作者：Guodong Sun ; Shenghui Su ; Maozhi Xu 等
期刊名称：International Journal of Security and Its Applications
印刷版ISSN：1738-9976
出版年度：2014
卷号：8
期号：6
页码：261-272
DOI：10.14257/ijsia.2014.8.6.23
出版社：SERSC
摘要：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+.
关键词：Quantum cryptanalysis; Shor’s algorithm; Grover’s algorithm; the multivariate permutation problem; REESSE1