公鑰密碼的量子攻擊研究現狀與展望

崔富鑫，王 輩，劉 焱，李 葉

(合肥本源量子計算科技有限責任公司，安徽 合肥 230000)

0 引言

公鑰密碼體制是密碼學史上一類極為重要的發明，它將數學、計算機與密碼學緊密結合，并解決了對稱密碼體制的三大問題：密鑰分發、密鑰管理和提供不可否認服務。自1976年Diffie與Hellman[1]提出公鑰密碼的思想以來，密碼學家設計了多個具有代表性的公鑰密碼算法，如Diffie-Hellman密鑰交換協議、RSA密碼體制、ElGamal加密體制、橢圓曲線密碼體制(Elliptic Curve Cryptography，ECC)，這些密碼算法的安全性建立在一些數學困難問題上。

公鑰密碼體制的安全性隨著Shor算法的提出受到了威脅。近些年，量子計算的蓬勃發展，也在推動著公鑰密碼攻擊的研究與實現。本文主要總結公鑰密碼在量子算法攻擊下的國內外研究進展，重點介紹RSA和ECC的量子算法攻擊現狀。結合后量子密碼遷移工作的緊迫性，進一步展望后量子密碼的未來發展以及量子算法對后量子密碼攻擊的可能性，為從事量子計算和信息安全領域的產學研工作者提供思路。

本文主要介紹幾類公鑰密碼加密算法和相關量子攻擊算法,介紹量子算法攻擊公鑰密碼的研究現狀,并對后量子密碼的發展以及產學研融合的未來作出總結與展望。

1 背景介紹

1.1 公鑰加密算法

在現代密碼學中，根據密鑰的不同特征，主要分為對稱密碼體制和公鑰密碼體制。前者在加解密算法中使用相同的密鑰，而后者則是使用不同的密鑰。

公鑰密碼體制中最著名的三個算法分別是RSA密碼體制、ElGamal密碼體制以及ECC體制。下面著重介紹RSA和ECC密碼體制的加密算法。

1.1.1 RSA加密算法

RSA算法是由Rivest、Shamir、Adleman[2]三人在1977年提出的，該算法也是首次實現的公鑰密碼算法，算法流程如下：

(1)密鑰生成：Alice選取兩個長度相等的大素數p和q，令N=pq；

(2)Alice選取e，d∈Z，并滿足ed=1 modφ(N)，其中φ(N)=(p-1)(q-1)，稱e為加密指數，d為解密指數，數對(N，e)為公鑰，(N，d)為私鑰，將公鑰對外公開；

(3)加密過程：Bob將消息M使用公鑰加密，得到密文C=Memod N后向外發送；

(4)解密過程：Alice接收到Bob的消息后利用私鑰解密，即Cd=Med=M mod N。

算法的安全性是基于數學中整數分解問題(Integer Factoring Problem，IFP)的困難性，因而在密鑰生成階段選取的素數越大，該算法越安全。但是RSA的攻擊問題是否等價于整數分解問題目前學界還沒有定論[3-4]，文獻[5]總結了對RSA的不同攻擊方式。當前整數分解最高效的算法——廣義數域篩法(General Number Field Sieve，GNFS)的時間復雜度依然是(亞)指數級的[6]，并且人們普遍相信這一問題在經典計算領域沒有多項式級別的算法。

1.1.2 ECC加密算法

基于離散對數問題(Discrete Logarithms Problem，DLP)的ElGamal加密算法最早由ElGamal[7]在1985年中提出。這一算法的困難問題可以簡潔地作如下表述：已知α，β=αx，求x mod ord(α)。橢圓曲線加密算法的困難問題與ElGamal加密算法的困難問題在形式上類似，該算法首先是由Miller在1985年[8]和Koblitz在1987年[9]分別獨立提出的。算法的流程如下：

(1)Alice選擇一條橢圓曲線Ep(a，b)，并選擇曲線上一點作為基點G；

(2)Alice選擇k作為私鑰，并計算K=kG作為公鑰公開，一起公開的還有橢圓曲線Ep(a，b)和基點G；

(3)Bob在收到公開的信息后，將要傳遞的信息編碼到橢圓曲線上一點M上，同時產生一個隨機數r；

(4)Bob計算A1=M+rK以及A2=rG；

(5)Bob將A1和A2發 送給Alice；

(6)Alice收到消息后計算A1-kA2=M+rK-krG=M，即可得到信息M。

ECC算法的安全性是基于橢圓曲線群運算上的離散對數問題(Elliptic Curve Discrete Logarithm Problem，ECDLP)的 困 難 性：已 知K，G∈Ep(a，b)且K=[k]G，求k mod ord(G)。該算法相較RSA算法能夠使用更短的密鑰達到相當的安全性，代價是增加了加密和解密時的計算量，美國國家標準技術研究院(NIST)在2016年的分析中指出，256位的ECC和3 072位RSA所達到的安全級別相同。

1.2 量子算法

1.2.1 Shor算法求解整數分解

1994年，美國數學家Shor[10]提出一個能夠在量子計算機上指數級加速大數分解問題和離散對數問題算法。利用該算法可以實現量子多項式時間復雜度的整數分解問題，完整的算法步驟如下：

首先將整數分解問題轉化為求階問題，假設要分解的整數為N，并且有最小的整數r使得ar=1 mod N，這里不妨假設r是偶數，則有：

然后進入算法的量子部分，量子部分的核心思想在于充分利用量子計算的特性，將周期信息編碼到基矢上然后讀出。量子部分的輸入為a，N，輸出為周期r的一個估計。該部分流程如下：

(1)取n=「log2N，其中「為向上取整函數；

(2)初始化t=2n個量子比特|0>t作為第一個量子寄存器，初始化n個量子比特得到量子態|0>n-1?|1>作為第二個量子寄存器，從而初始態為：

(3)對第一個量子寄存器制備最大疊加態：

(4)對兩個寄存器作用一系列模指數運算U2i，得到：

上述態也可以近似化簡為：

(5)對第一個量子寄存器作用量子傅里葉逆變換：

(6)測量第一個量子寄存器，得到比特串m。

上述流程為算法的量子部分，二進制比特串需經過后處理才能得到周期r。由上面的過程可知是某個的近似，由求r的過程稱為連分式算法，該算法可以將寫成一系列分數的形式，并且分數列與逐漸靠近，周期r大概率就隱藏在某個分數的分母中。算法的可行性由定理1保證。

定理1[11]設是一個滿足的有理數，則是的連分式的一個漸進值，從而可以利用連分式算法在O(t3)時間復雜度內計算。

讀取到上面的r后，需要判定r是否為a的周期，若否，重新進行算法的量子過程，直到找到周期，還需要判斷是否為偶數，若否，返回第一步重新取a。

關于Shor算法的時間復雜度有定理2成立。

定理2[10]n比特的整數分解可以在量子計算機上以O(Poly(n))次操作外加多項式復雜度的經典處理完成。

上述定理相較于數域篩法分解同比特數的整數所需的exp(Θ(n1/3log2/3n))次操作是一個巨大的飛躍。

與Shor算法十分類似，離散對數問題也可以通過與上述過程類似的量子線路來實現指數級的加速。

1.2.2 離散對數問題求解

Shor在文獻[10]中利用量子算法以多項式復雜度解決的另一個問題就是離散對數問題。即給定a和b=as，確定s，可以將這一問題進行轉化?？紤]二元函數為：f(x1，x2)=asx1+x2mod N，易得該函數為周期函數，并且周期是一個二元組，通過計算二元組能得到原離散對數問題的周期s。求解二元函數周期的量子算法流程如下：

(1)依然是取n=「log2N，其中「為取整函數，設r是使得armod N=1的最小正整數；

(2)初始化t=O(log(r))個量子比特|0>t作為第一個量子寄存器，重復該步驟兩次，再初始化n個量子比特|0>n得到三個初始化的量子寄存器為：

(3)對前兩個量子寄存器分別作制備最大疊加態為：

(4)對三個寄存器作用一系列白盒Uf，得到：

上述態也可以近似寫成：

(5)對前兩個量子寄存器作用量子傅里葉逆變換：

(6)測量前兩個量子寄存器，得到兩個比特串(m1，m2)，可以利用廣義連分數算法得出s，此外，Eker?[12]通過多次測量得到{(m1j，m2j)}構造格，之后通過經典的格基約化算法求得s。

與整數分解的Shor算法類似，可以證明上述算法(包含經典部分的處理)的時間復雜度同樣是多項式量級的。

需要注意的是，這里給出的是有限域上的離散對數問題及其量子算法求解，而ECC算法依托的ECDLP則是將有限域上的四則運算替換成了有限域上橢圓曲線的有理點加運算。

1.2.3 量子優化算法

量子優化算法是一種在理念上完全不同于上述邏輯運算的量子算法。優化算法一般是將一個經典問題轉化為一個組合優化問題，下一步搭建一個能夠反映該優化問題的物理模型，最后利用量子退火機的特性(量子漲落及隧穿效應)求解該模型的最小值，由于量子隧穿效應的存在，使得上述求解在一般情形下能夠得到全局最優解。需要注意的是，由于絕熱量子計算被證明是等價于通用量子計算[13]，因而一些利用絕熱演化求解的優化問題也可以被通用量子計算機近似求解。

這種優化思路對攻擊RSA算法的困難問題——整數分解問題提供了一種全新的思路。將整數分解問題視作一個優化問題最早是由Burges[14]在2001年提出的，該方法在2007年被Schaller等人[15]改進。算法的一般流程如下：

(1)選擇兩個待定數字(設兩個數字為N的因子)，寫出兩個數字的二進制乘法表(表1為35的待定分解)，令t=「log(N)，該步驟的復雜度為O(t)；

表1 二進制乘法表

(2)將乘法表和N進行比對，化簡方程組，減少待定數字,該步驟的時間復雜度為O(t3)；

(3)將上述問題轉化為二次無約束布爾優化問題(Quadratic Unconstrained Boolean Optimization，QUBO)，該步驟時間復雜度為O(t3)；

(4)針對上一步驟的二次優化問題構建伊辛模型，該步驟時間復雜度為O(1)；

(5)利用量子退火機求解該模型得到最優解，量子計算時間復雜度為O(t2)。

上述步驟的復雜度由文獻[16]給出。不同于Shor算法需要在通用量子計算機上執行，量子優化算法一般在量子專用機上處理，這為優化算法開辟了完全不同的賽道，也在一定程度上規避了大規模通用量子計算機發展緩慢的困難。

2 量子算法攻擊公鑰密碼的研究

2.1 量子算法攻擊RSA的研究

2.1.1 Shor算法攻擊RSA

Shor算法被提出后引起了人們的廣泛關注，此后的時間不斷有基于Shor算法的改進方案被提出。改進工作在多個不同的角度同時進行，比如，致力于減少算法所需的邏輯比特數或者物理比特數，使用模擬計算不斷提高可分解的比特數或者將Shor算法與高性能算法相結合等。下面假設分解的數字為N，并且n=「log2N，算法運行中選取的隨機數為a。

(1)實現Shor算法所需邏輯比特數的改進

1995年，Vedral等人[17]首次給出了邏輯比特一個確定的上界7n+1，并且確定了線路復雜度為O(n3)量級，還進一步指出了將量子比特降到4n+3的可能性。

1996年，Beckman[18]等人基于離子阱量子計算機的工作將上述結果修改為5n+1，同時指出了繼續降低輔助比特數的可行性。1998年，Zalka[19]采用了并行算法計算加法以及快速傅里葉變換加速乘法等兩種改進方法，將量子比特繼續降到3n。

2003年，Beauregard[20]提出一種切實可行的2n+3型方案。該方案在兩個方面進行了改進，一是利用序列傅里葉變換(semi-classical Fourier transform)替代傳統的量子傅里葉變換，這使得控制比特的數量下降到1，取而代之的是需要O(n2)級別的經典信息傳輸來還原所需的傅里葉逆變換。另一處改進是借助了Draper[21]在2000年的一種利用傅里葉變換構造加法模塊的技術，從而構造更加節省比特數目的模指數運算模塊。然后在2021年，Rossi等人[22]將上述2n+3方法進行了部分優化，并在IBM的量子虛擬機運行該方法分解了51和57，并將該方法分解成功的概率與一般Shor算法之間進行了詳細的比較。值得注意的是，該方法相比原始Shor算法中針對無法完成分解的對(N，a)提高了一定的成功概率。

2006年，Takahashi和Kunihiro[23]首 先對上述結果進行了改進，總量子比特數降到2n+2，線路復雜度和線路深度分別為O(n3logn)與O(n3)，該線路的復雜度相較于文獻[20]縮減了近一半。2016年，H?ner等人[24]又提出了一種不同的思路實現2n+2比特數，該算法的線路復雜度與線路深度都和文獻[23]保持一致，并且與之前算法不同的是該算法實現模乘的模塊僅使用了Toffoli門和Clifford門。

仍然是在2006年，Zalka[25]給出了一種僅需要1.5n+2的理論模型，該文章還將Parker、Plenio在2000年給出的結論[26]進行了優化。文獻[26]指出，2n個控制比特中的一半不需要初始化到|0>(盡管仍需要2n次測量)，而Zalka則證明所有的控制比特都不需要初始化，不需要初始化的量子比特可以是任意態，也稱為“臟”(dirty)量子比特。

2017年，Gidney[27]將總比特數再次修改到2n+1，盡管這一數字大于1.5n+2，但該算法所需的初始化的比特數更少，需要n+2個初始化的量子比特和n-1個臟量子比特。

綜上所述，改進Shor算法攻擊RSA所需邏輯比特數的具體研究進程如表2所示。

表2 Shor算法攻擊RSA所需邏輯比特數的改進時間表

(2)Shor算法攻擊RSA的規模估計

2009年，Van等人[28]設計了一種分布式量子計算模型，該模型的結果顯示，攻擊RSA-2048所需的量子比特數可能在65億左右，此外，該算法采用了6n邏輯比特，總的Toffoli門數量約為3 200億，攻擊耗費的總時間預計為409天。

2010年，Jones等人[29]通過構造一種分層量子計算機模型將上述問題所需的比特數縮減到了6.2億左 右。2017年，O′Gorman和Campbell[30]通 過 詳 細 分析糾錯理論將該問題所需的量子比特數進一步縮減到2.3億左右。

2019年，Gheorghiu和Mosca[31]將量子比特數縮減到1.7億左右，文獻中采用的邏輯比特為4 098(即2n+2模型)，理論上的攻擊時間為24小時。同年，Gidney等人[32]對上述結果做出較大改進，將所需量子比特數縮減到2 000萬左右。盡管他們使用的是邏輯比特數為3n理論模型，但是成功地將線路深度下降到500n2+n2logn，理論上的攻擊時間也縮短到8小時。

2021年，Gouzien和Sangouard[33]采 用 時 間 換 量 子 體積的思路給出一種同樣是基于Shor算法(該算法的理 論 部 分 來 自Eker?和H?stad的 工 作[12])的 構 造，使用該構造攻擊RSA-2048所需的邏輯量子比特數為8 284，但所需的物理比特數僅僅只有13 436，相比兩千萬這是巨大的飛躍，甚至可能將攻擊RSA-2048的時刻表拉入近二十年之內。盡管理論上的運行時間有177天，但相較千萬級物理比特數目的差距這完全是可接受的。此外，文章還指出，可以通過增加量子比特的形式來減少運行時間，比如，當物理比特數增加到184 000時，運行時間可縮短至68天。

綜上，Shor算法攻擊RSA-2048所需量子比特數的預估發展如表3所示。

表3 攻擊RSA-2048所需總比特數的進展

除了上述兩個主要的方向的進展外，量子模擬計算[33-35]、Shor算法與高性能計算相結合[36]，Shor算法結合數論方法采用特殊處理[37]等方法均有相應的進展。

2.1.2 量子優化算法攻擊RSA

將整數分解問題轉化為優化問題后，后續的工作進展主要集中在利用量子近似優化算法(Quantum Approximate Optimization Algorithm，QAOA)、量子退火以及絕熱演化等算法求解模型的方法研究[38]。

首先是2008年，Peng等人[39]第一次物理上實現了量子絕熱算法分解因數，本次實驗使用3量子比特分解了21，在當時也是首次實現對大于15的數字的量子算法分解。

2012年，Xu等 人[40]利 用 優 化 理 論 及NMR技 術在只使用4量子比特的情況下分解了143，與前人的方法相較，該文章在分解前進行了部分數學上的預處理(解方程)，從而可以用更少的量子比特數來分解較大的數字。

隨后在2014年，Dattani等人[41]利用相同的算法和4個量子比特得到了44 929和56 153的分解，對比2012年的類似結果，之所以能夠有如此大的改進，得益于經典部分的數據處理，比如56 153的情況多數限制方程組都可以被約化，使得最后目標函數或者哈密頓量所具有的自由度與分解143的情況無異。

2016年，Pal等人[42]將經典處理和絕熱演化相結合，在僅使用三個量子比特的情況下成功分解了551。2017年，Li等人[43]再次利用該思想在僅使用3個量子比特的情形下分解了291 311。

此外，在2016年，Dridi和Alghassi[44]利用D-Wave 2000Q實現了小于223 357=401×557的一般分解，并且指出了如何利用Gr?bner基來減少哈密頓量的自由度以實現減少所需量子比特數的目的。

2018年，Jiang等人[45]提出一個理論框架，該框架可以將整數分解問題轉化成優化問題進而構建為可執行的伊辛模型。對于給定的數字N，文章給出了算法所需的量子比特數O(log2(N))，并且文中展示了如何分別使用4、12、59、94個邏輯比特完成15、143、59 989以及376 289的分 解。驗 證過 程 同樣使用的是D-Wave 2000Q。

2020年，Saxena等人[46]提出了一種經典-量子混合方案，該方案可以看作是文獻[40]和[42]的一個推廣，特點是將量子絕熱基態搜尋轉變為可在一般量子計算機上執行的量子線路(將演化過程按時間切割，得到一系列酉矩陣，然后用通用門來表示這些酉矩陣)，文章還通過IBM的量子計算機展示了上述方法分解35的過程。

同年，Wang等人[16]將優化方法的理論進行了細致的整理，給出了每個步驟的復雜度信息，并且借助D-wave給出了10 000以內的一般分解和最大到20比特(1 028 171)的數字分解。

2020年，IBM的Karamlou等 人[47]成 功 分 解1 099 551 473 989，使用的依然是變分方法，這也是當前文獻可考的使用量子算法分解的最大數字。不過這一數字遠沒有通用機上分解的最大數字21更有意義，原因在于：理論上，只要選取足夠大的相近素數相乘得到N，比如一對靠近2m的孿生素數，通過經典處理大概率能夠以4個以內量子比特實現N的分解。事實上，IBM的這篇文章也正是這么做的，注意到如下事實：1 099 551 473 989=1 048 589×1 048 601以及220=1 048 576。

2.2 量子算法攻擊DLP與ECDLP的進展

2016年，Eker?和H?stad[12]討 論 了 如 何 利 用 格 基約化算法在Shor算法求解DLP后處理中的作用。此外，有關量子算法攻擊DLP的文獻非常少，物理實現更是幾乎沒有，直到2021年，Aono等人[48]才第一次利用IBM的量子計算機解決一個2比特的離散對數問題。盡管求解DLP的量子算法早在1994年Shor已給出，并且Shor在文章中指出素數域上的DLP可以推廣到其他域，但相關的研究直到近十年后才開始進行。

量子算法攻擊ECC的方案最早可以追溯到2003年Proos和Zalka的工作[49]，文獻中主要考慮的有限域為素數域GF(p)，而沒有考慮諸如GF(2n)類有限域。在此基礎上，文獻給出了算法所需的邏輯量子比特數約為6n，其中n為密鑰長度，盡管這一數字大于Shor算法的各種改進版本所需的邏輯比特數，但考慮到ECC加密算法的密鑰長度天然比RSA的密鑰長度短得多，攻擊相同安全級別的ECC較RSA所需的邏輯比特數仍然是降低的。

2017年，Roetteler等人[50]給出了攻擊素數域上ECDLP的精確估計。文中所需的邏輯比特數為9n+2[log2n]+10，線路所需的Toffoli門至多為448n3log2n+4090n3。并且他們同樣將上述估計與攻擊RSA的估計進行比較，指出對于通用量子計算機，攻擊安全性能相當的同等安全級別ECC問題要比RSA問題更加簡單。

2020年，H?ner等人[51]通過平衡總量子比特數和線路深度以及T門數量，改進了Shor算法求解ECDLP量子線路中的點加線路模塊，使之相較文獻[50]達到更短的線路深度和更少的T門數量。

然 后 在2021年，Wroński[52]通 過 分 析ECDLP經典攻擊中的指標積(Index Calculus)算法，其算法求解的關鍵是代數方程組的求解，他將其代數方程組的求解問題轉化為QUBO問題，從而可以發揮量子退火機的優勢，不過這一步驟的復雜度仍然難以估計。此外，作者借助D-Wave Leap cloud攻擊了GF(p)(p=251)上的ECDLP。需要注意的是，經典場景下的指標積算法是一個亞指數級時間復雜度算法。該方案只是將量子退火理論與ECDLP相結合，目前還不能證明其優越性。

2021年，Banegas[53]等人針對定義在GF(2n)域上ECDLP做了Shor算法攻擊實現的資源評估，需要7n+[log2n]+9個量子比特以及Toffoli門至多為，CNOT門的個數依然是O(n3)量級的。2022年，Liu等人[54]進一步優化Shor算法求解GF(2n)域上ECDLP的量子線路。利用節省空間的量子Karatsuba乘法器，可以實現較低CNOT門個數的模數求逆和模數除法線路，進而達到整體線路中CNOT門個數降為O(n2)量級的效果。

綜上所述，量子算法攻擊ECDLP的進展如表4所示。

表4 量子算法攻擊ECDLP的進展

3 結論

本文較詳細地分析了量子算法攻擊公鑰密碼的研究現狀，重點介紹了Shor以及量子優化算法攻擊RSA的發展進程和Shor算法攻擊ECDLP的發展進程，旨在幫助研究者們快速地了解國內外的研究方法與最新進展，為后續的工作起到借鑒作用。

由于通用量子計算機發展緩慢，在密碼攻擊領域，實現1 024比特的RSA攻擊和163比特的ECC攻擊還相當遙遠。目前，已公布的文獻中能夠通過Shor算法使用真實的量子計算機分解的最大數字仍然是21，而且每前進1比特都相當困難，盡管有很多文獻不斷向下調整目標所需的邏輯比特或者物理比特，但Shor算法距離攻擊公鑰密碼的距離仍舊十分遙遠。此外，盡管通用機上的分解算法進展緩慢，但使用優化算法量子專用機卻表現得出人意料，尤其是處理整數分解問題，通過經典部分的預處理，退火機能夠分解的數字比通用機大幾十個量級。

除了量子硬件發展的限制，當前量子算法攻擊公鑰密碼還存在一些技術上的約束和困難，有待后續解決，具體問題見表5。

表5 量子算法攻擊公鑰密碼的困難

由于量子計算對公鑰密碼的威脅，各國密碼管理部門對后量子密碼(Post-Quantum Cryptography，PQC)研究也開始重視和推進，旨在能威脅現行公鑰密碼的通用量子計算機問世之前，完成公鑰密碼系統到后量子密碼系統的整體遷移。2022年7月5日晚，NIST公布其后量子密碼標準化項目第三輪篩選的結果。提前被選中并將進行標準化的算法包括：CRYSTALS-Kyber、CRYSTALS-Dilithium、Falcon、SPHINCS+。其中CRYSTALS、Falcon是基于格的后量子密碼算法，SPHINCS+是基于哈希的后量子密碼算法。NIST正持續推進PQC的標準化過程，歐盟和亞洲國家也高度關注。世界各國的數字空間也將面臨下一代公鑰密碼系統的遷移。這一趨勢必將引發新一輪的IT產業變革，促進全球數字經濟發展。

目前，國內不少科研學術機構和商業機構一方面在持續研究量子算法對公鑰密碼的攻擊工作，另一方面也在高度關注后量子密碼的遷移工作。在公鑰密碼攻擊方面，上海大學的王潮團隊、中國科學技術大學的彭新華團隊一直致力于研究量子算法對RSA的攻擊工作；合肥本源量子計算科技有限責任公司致力于在真實的量子計算機上研究對RSA和ECC的量子攻擊算法實現。另一方面，很多科研團隊在后量子密碼的研究工作上也進展頗豐，如國內清華大學丁津泰教授參與設計的CRYSTALS-Kyber算法，順利入選NIST關于后量子密碼第四輪標準。

未來，密碼學與量子計算的結合將會越來越緊密，后續需研究與發展的方向可以關注下面幾個方面：

(1)不斷優化Shor算法對公鑰密碼的攻擊實現。Shor算法在理論上已威脅到公鑰密碼體制的安全性，且實驗已經驗證其正確性。在量子硬件條件受限的情況下，不斷優化與改進Shor算法攻擊RSA或ECC所需的量子比特數、量子門個數及其他性能指標是未來必然的一項研究工作。

(2)發掘專用型量子計算用于密碼部件設計及公鑰密碼攻擊的潛能。量子設計密碼是一個新的領域，如何從傳統密碼的經典線路過渡到量子線路實現，以及實現怎樣的密碼算法安全指標。結合量子密碼設計，在量子環境下，分析公鑰密碼的攻擊實現以及可達到的安全級別。

(3)PQC遷移是必然趨勢，且宜早不宜遲。IBM可能在2030年之前實現1 000量子比特的大規模實用量子計算機；加拿大將在2030年規劃實現PQC的遷移；美國政府系統的后量子遷移工作將在10年后初步完成，并倡導工業界盡快完成后量子密碼遷移。當前，部署后量子密碼的遷移工作是未來十年工作的重點，工程量浩大，需要全世界各行各業一起努力，一起面對與解決遷移過程中遇到的各種問題。

(4)拓展量子算法對后量子密碼的攻擊工作。未來后量子密碼面臨的挑戰主要是針對不同的困難問題分析它們的量子計算安全性?；诰幋a的后量子密碼算法可以經得起多年考驗，根本原因是其底層困難問題的歸約仍然處于未知狀態，因而缺乏針對性的高效算法。對于基于格的后量子密碼，其底層安全性是基于確切的數學困難問題，未來是否也有類似Shor算法的量子算法可以高效攻擊格密碼進而帶來底層隱患尚不確定。

綜上所述，量子算法對公鑰密碼的威脅程度主要取決于量子計算硬件的發展，但對公鑰密碼的量子攻擊研究依然需要不斷優化與改進以提高其性能效率。未來十年，后量子密碼的遷移是大勢所趨，需要各行各業協同推進。