當前位置: 華文問答 > 科學

清華大學陳一鐳發表量子演算法,有望解決世界級演算法難題「格密碼」,該項工作有怎樣的前景和意義?

2024-04-11科學

作為朋友圈已經被刷屏的相關人士,本來想等自己把論文看過一遍之後再回答,但是這個問題的熱度似乎有點高,底下也有些回答讓我不盡滿意,所以還是簡單寫一點。

disclaimer: 個人對格問題的經典求解略知一二,但是對量子演算法所知不多,有說的不對的地方敬請見諒。

首先,十分敬佩陳老師能做出這樣的成果,無論最後這個結論是被驗證還是被推翻,都極大地推進了我們在格密碼量子安全性上的認知。然後,我對這個工作的意義談一下個人的看法。

(1) 這項工作是否破解了格密碼?

正如陳老師在論文中指出的,這項工作對LWE問題的參數選取有一定要求,目前主流的標準演算法並不在可破解的範圍之內。但是這項工作(如果被驗證)會極大地降低人們對格密碼的信心,導致人們對格密碼作為抗量子密碼的前景產生極大的憂慮。

而且,除了標準演算法之外,格密碼有很多其他的套用,例如內容基加密ABE或全同態加密FHE。這些方案大多都落入了這一工作可攻擊的參數選取範圍之內。近年來,格密碼領域有一個趨勢是使用NTRU替代LWE(或RLWE)。至於NTRU是否可以繞過這一攻擊,可能還有待進一步的研究。

(2) 這項工作是否意味著我們需要放棄對格密碼的研究?

即使格密碼最後被證明了不是抗量子的,也不意味著格密碼的研究失去意義,畢竟即使是明確無法抗量子攻擊的橢圓曲線配對,目前仍有許多的研究工作基於其上展開。格密碼的能力比配對密碼更強,可以實作例如任意多項式策略的內容基加密、全同態加密等功能,這些都是傳統的配對密碼無法做到的。因此在可用於破解密碼演算法的通用量子電腦真正誕生之前,格密碼仍然會得到廣泛的關註(盡管可能不如現在)。

另外,目前一些研究者正嘗試將格密碼用代數模型抽象化(正如將配對密碼抽象為雙線性對映)。如果這一方向可以走通,基於格密碼的方案很有可能可以平移到編碼等其他困難問題上。因而格密碼的研究目前還算不上是死路一條。或者不如說,正是因為出現了這些問題,才有必要把更多的關註投入到格密碼的研究上。

(3) 這項工作對密碼學的影響?

首先提一下,區塊鏈上的簽名和零知識證明是可以基於哈希構造的,而哈希(或廣義地說,對稱密碼)由於不具備代數結構,被認為是最能抗量子的演算法。所以除非真的證明了NP in QBP,否則無需太過擔憂量子計算出現後,區塊鏈會瞬間倒塌這件事——盡管他們可能需要盡早布局更換鏈上的演算法。

如果陳老師的結果被證明成立,可能會促進密碼學中幾個領域的成果湧現:

第一,基於其他抗量子問題的密碼方案研究。之前由於格密碼一家獨大,基於編碼、多變量等的方案被廣泛忽視了。特別地,是否可以基於編碼、多變量等假設實作復雜的功能性密碼方案,如身份基加密、內容基加密、群簽名、環簽名,都是尚待研究的藍海。

第二,用於密碼學的量子計算演算法的研究。盡管後量子密碼已經提了很久,但大多數密碼研究者都還是量子計算的外行,對後量子密碼的研究也仍是從經典計算的角度。但這一工作的出現,意味著後量子密碼研究者如果不懂量子計算,恐怕很難在這個領域作出大的成就了。至少從我個人而言,我感覺自己得開始進入辛苦的補課過程了。

第三,格密碼本身的研究。正如SIDH被攻破後,同源密碼的論文反而變多了一樣,特定參數下的LWE被攻破,反而會有許多研究者,考慮如何基於不滿足攻擊條件的那些格問題和參數,構造新的格密碼演算法。如果是已經投入格密碼研究的碩士生或博士生,不妨嘗試從這個角度出發思考問題,說不定會有新的成果產出。

第四,格方法用於求解其他困難問題的研究。RSA、ECC等經典密碼,在有側通道資訊泄露的情況下,都可以用格演算法求解。那麽,對於編碼、多變量等其他目前仍被認為是抗量子的問題,是否存在一種辦法,將其轉化為格問題,從而實作多項式復雜度的量子求解?以及,不滿足攻擊條件的那些格密碼演算法,是否也有可能在存在資訊泄露的條件下,可以轉化為此類問題,從而能被量子演算法求解?這些似乎都是很值得研究的問題。

最後:科學就是在不斷的試錯中發展起來的。目前國內的科研氛圍總地來說有些浮躁,很多人不願接受失敗。當然,這其中有客觀原因,但對於科學本身來說,這不算是好事。希望中國研究者能在密碼學領域作出更多突破性成果,也和各位共勉。