国内有学者声称可以通过372个量子比特破解RSA-2048问题,这是否意味着RSA加密算法在近期就会被破解?

发布时间:2023-08-18

  答:去年底,国内学者在预印本网站arXiv上发表了关于大数分解量子算法的工作[arXiv:2212.12372v1]。为了显示在近期量子技术水平下的可实现性,该工作采取了量子经典混合方法,其基本思路是利用Schnorr整数分解算法这一经典算法进行预处理和后处理,将整数分解问题转化为格约化问题,同时利用量子近似优化算法(QAOA)来优化这一问题的求解效率。该文作者估计,通过该方法破解RSA-2048所需要的量子比特数为372,远低于Shor算法;而如此规模的量子比特数很有希望在几年之内达到,因此难免让人引发联想:这是否意味着RSA-2048加密系统会在短期内被破解呢?

  答案是否定的。尽管该方法在原理上仅要求300多个量子比特,但同时也涉及上千线路深度,这对于量子系统的要求仍然在短期内难以达到。评估量子计算系统的能力,除了量子比特数目以外,还受到系统的稳定性(由退相干时间表征)、操作的准确性(由单比特门、双比特门以及测量的保真度表征)的影响。具体而言,退相干时间描述了系统丢失其量子信息的特征时间,类似于放射性半衰期。线路的深度越大,执行所需的时间就越长,量子信息丢失的概率就越大,引入错误的可能性越高。而门操作的数目越多,其错误的来源就越多,发生的错误就越复杂。因此,以当前最前沿的量子技术水平(单比特门保真度99.9%, 双比特门保真度99.5%)来估计,由372个量子比特以及1118层线路深度的量子计算系统来执行该算法,保真度将不足2-1600,相当于亿亿亿……(60个)分之一!这意味着实验结果将完全淹没在系统噪声当中。

  除了技术上的难度,该方法在原理上同样存在很大的不确定性。不同于Shor算法,该方法采取的量子经典混合算法并不具有明确的复杂度分析。正如该文作者自己所指出的,“由于量子近似优化算法的收敛性不明确,该算法的量子加速还不清楚。”除此之外,该方法的基础——Schnoor算法的有效性自提出以来也一直受到学术界的质疑。Schnoor算法只提出了解可能存在的条件,而对出现的概率却无法评估,导致算法的效用大打折扣。例如,著名格密码专家Leo Ducas通过实验得出结论,对于分解40位的整数,使用该方法在1000次测试中并未成功发现满足要求的解,这进一步降低了其有效性。近期,谷歌量子计算团队进一步通过实验表明 [arXiv:2307.09651],即使是在假设没有噪声的情况下,该算法最多只能分解80位的整数,这就意味着即使暴力破解所有可能性,算法仍然失效,因此该方法本质上是无法扩展的。

相关文章