论文部分内容阅读
随着量子计算的持续发展,其应用场景越来越多元化,而在密码学中的应用是最值得研究的场景之一。量子计算环境下需要对不同密码算法的安全性能进行评估,量子线路模型是一个重要的工具。与量子图灵机模型等价的量子线路模型能够清晰、直观地模拟量子信息的处理过程,对设计量子计算装置和新的量子算法都有很好的指导作用;量子算法通常由量子线路表示出来,设计出好的量子线路意味着能更好地实现量子算法。目前,衡量量子线路的优劣有三个指标——量子比特数目、Toffoli门/T门数目和Toffoli门/T门深度。RSA、椭圆曲线离散对数和特征为2的域上的椭圆曲线离散对数以及AES是典型的密码系统。对这些密码算法的量子线路进行合理设计使得量子比特数目、Toffoli门/T门数目和Toffoli门/T门深度尽可能优化有助于进一步评估密码系统在新时代的安全性能。本文围绕密码算法的量子线路优化这一主题,通过挖掘经典-量子的相互作用、协同的机理以及噪声、拓扑结构对量子资源的影响,应用了近似编码表示、加窗查表操作、改进的量子Karatsuba乘法以及近似最小斯坦纳树问题归约等关键方法,为密码算法的量子分析丰富了理论基础和技术支撑。本文的主要研究工作如下:1.为了在含噪声环境中使得Shor整数分解算法的量子线路所需时间资源花费和空间资源花费达到很好的折衷,利用整数取模的陪集表示技术和加窗技术来优化整数分解的求阶(即求周期)量子线路。在这项工作中,整数取模的陪集表示技术通过增加一定的近似误差来实现时间空间资源代价的折衷;加窗查表操作可大大降低量子线路中所需要的Toffoli门数目。结果表明,近似造成的误差可以随着整数取模的陪集表示中填充比特数目的增加呈指数级降低,以至于能低于目前其他因环境噪声引起的误差;由加窗QROM查表进行数据寻址读取被量子寄存器索引的经典值能够减少求阶量子线路中所需的乘法操作次数和加法操作次数。2.针对素数域上椭圆曲线离散对数求解的量子线路优化问题,通过对量子线路中的模加部分进行改进,使用近似编码表示方法结合加窗方法对素数域上椭圆曲线离散对数求解的量子线路进行优化,在增加对数规模的量子比特的条件下使得模乘法、模平方、模逆部分需要的T门数目和T门深度得到了优化。在这项工作中,借助加窗技术和整数取模的陪集表示技术,在加法的近似编码表示基础上给出了椭圆曲线群上离散对数求解量子线路的整体优化和资源估计有效降低了T门数目以及T门深度,并对设计的量子线路进行了仿真实验。数值结果表明,在增加对数规模的量子比特后,通过选取适当的窗口参数,T门数目和T门深度都得到了相当可观的减少。3.针对连通性受限的特征为2的有限域中椭圆曲线离散对数求解的量子线路优化问题,通过分析点加操作所需要的加法、二进制移位、乘法、平方、求逆等量子线路在量子比特连通性受限时的资源花费,在Karatsuba乘法的基础上借助最小斯坦纳树问题归约对求逆和除法中的CNOT门数目进行了优化,在考虑拓扑结构的情况下评估了特征为2的有限域上椭圆曲线离散对数问题求解的量子算法的性能。在这项工作中,以费马小定理的求逆算法(Itoh-Tsujii算法)为基础、借鉴最小斯坦纳树问题归约方法对连通性受限的F2n上椭圆曲线离散对数求解中点加操作的子线路所需的CNOT门数目进行优化,优化后的CNOT门数目为O(n~2/log?),其中?为连通性受限的图中节点的最小度数。数值仿真结果表明,在Karatsuba乘法的基础上借助最小斯坦纳树问题归约能够对除法线路中的CNOT门数目进行了优化,除法线路中的CNOT门数目得到了相当可观的减少。4.针对AES-128中的8?8S盒变换的优化实现问题,引入了衡量时间资源代价和空间资源代价折衷的指标——量子比特数目与T门深度之积,使用加窗量子查表方法在改进的Karatsuba乘法的基础上进一步优化了求乘法逆以及实现S盒所需的量子资源。在这项工作中,对三种乘法量子线路作了全面的量子资源代价对比,选取了在S盒中求乘法逆的量子线路的时间资源代价和空间代价折衷方面更优的求乘法逆线路;用加窗查表方法进一步减少了求乘法逆以及S盒实现所需要的量子乘法次数。结果表明,基于空间资源优化的量子Karatsuba乘法使用加窗查表技术在实现8?8S盒变换中的求乘法逆操作时,Toffoli门数目、量子比特数目、量子比特数目与T门深度之积更优。