量子计算是一种基于量子力学原理的新型计算模式,由于其具有超越经典计算的强大并行计算能力,使得它突破了现有信息技术面临的极限。一些量子算法的出现给现代密码学带来了极大的挑战,Shor算法和Grover算法是当前对密码学最具威胁的两类量子算法。Shor算法能够在多项式时间内求解因子分解问题和离散对数问题,使得当前广泛使用的RSA、El Gamal和ECC等公钥密码系统不再安全。Grover算法是一种通用的量子搜索算法,能够对许多密码问题的求解达到平方根加速。对公钥密码体制进行抗量子攻击的研究,不仅可以评估密码体制在量子计算下的安全性,同时也扩大了量子计算和量子算法的应用范围。REESSE1+公钥密码体制是一种基于多变量和多难题的公钥密码体制,体制的安全性基于三个新难题——多变量排列问题、非范子集积问题和超越对数问题以及一个已有难题——多项式求根问题。论文围绕REESSE1+公钥密码体制的抗量子性,对体制中的四个困难问题进行了抗量子攻击的研究,主要的研究内容和成果包括:(1)对利用Shor算法和Grover算法攻击多变量排列问题进行了研究。分析得出多变量排列问题不可能转化为因子分解问题,因而利用Shor因子分解算法无法求解多变量排列问题。证明了求解多变量排列问题的难度至少等价于求解离散对数问题的难度,同时给出了多变量排列问题不可能转化为离散对数问题的必要条件,进而说明利用Shor离散对数算法求解多变量排列问题是不可行的。研究了利用Grover算法对多变量排列问题的攻击,结合多变量排列问题的经典攻击,给出了针对多变量排列问题的量子攻击算法,通过分析这些攻击算法的时间复杂性和成功率,认为这些攻击均是不成功的。提出了解求根问题的两种量子算法,定义了多集合搜索问题并给出其量子算法,详细设计了求根问题和多集合搜索问题量子算法中Oracle的量子线路。(2)对利用Shor算法和Grover算法攻击非范子集积问题进行了研究。理论上分析了非范子集积问题不能转化为因子分解问题,证明了求解非范子集积问题的难度至少等价于求解离散对数问题的难度,并给出非范子集积问题不能转化为离散对数问题的必要条件,得出Shor算法不适用于求解非范子集积问题的结论。实验上分析了非范子集积问题不能转化为隐含子群问题。研究了利用Grover算法对非范子集积问题的攻击,通过设计两种识别非范子集积问题解的量子Oracle,给出了攻击非范子集积问题的两种量子算法。设计了这两种量子Oracle的线路,归纳给出求取比特影子的量子线路设计方法。提出了求解非范子集积问题的量子中间相遇攻击算法。通过仿真Grover算法对非范子集积问题的攻击,对一些非范子集积问题实例进行了成功的求解,验证了针对非范子集积问题的量子攻击算法的正确性。(3)对利用Shor算法和Grover算法攻击超越对数问题进行了研究。通过证明求解超越对数问题的难度至少等价于求解离散对数问题的难度,并分析了超越对数问题不可能退化为离散对数问题,得出超越对数问题能够抵抗Shor离散对数算法攻击的结论。实验分析了超越对数问题不具有隐含周期的特性,故利用Shor算法的原理求解超越对数问题是不可行的。在Grover算法的基础上,提出了一种求解超越对数问题的量子计算算法,描述了算法中量子Oracle的设计原理,并详细设计了Oracle的量子线路。通过利用Grover算法攻击一些超越对数问题实例的仿真实验,验证了针对超越对数问题的量子攻击算法的正确性。(4)对利用Shor算法和Grover算法攻击多项式求根问题进行了研究。通过分析多项式求根问题的参数取值,得出Shor离散对数算法不能够求解多项式求根问题的结论。实验分析了多项式求根问题不具有隐含周期的特性,因而Shor算法也就不适用于求解多项式求根问题。在Grover算法的基础上,提出了求解多项式求根问题的量子计算算法,阐述了算法中量子Oracle的设计原理,并详细设计了Oracle的量子线路。通过对多项式求根问题的一些具体实例进行攻击的仿真实验,验证了针对多项式求根问题的量子攻击算法的正确性。总之,通过对REESSE1+公钥体制中四个困难问题的量子攻击研究,表明REESSE1+体制能够抵抗Shor算法的攻击,故目前这四个难题不存在量子计算机上的多项式时间解。详细研究了利用Grover算法对四个困难问题的攻击,可以通过增加参数的长度来抵御Grover算法的攻击。因此,REESSE1+体制能够抵抗现有条件下量子计算的攻击。这些研究对于评估REESSE1+公钥体制在量子计算下的安全性具有重要的参考价值。