最近，NTT Research宣布，由NTT Research密碼學(xué)和信息安全實驗室（Cryptography & Information Security (CIS) Lab）以及NTT社會信息學(xué)實驗室（NTT Social Informatics Laboratories）的兩名科學(xué)家分別撰寫的兩篇論文入選為“2022年度IEEE計算機科學(xué)基礎(chǔ)研討會（FOCS）論文”。

?

這兩篇論文就量子計算給密碼系統(tǒng)帶來的挑戰(zhàn)進行了深入探討。以《Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier》為題的論文，是由NTT Research CIS實驗室高級科學(xué)家、普林斯頓大學(xué)助理教授Mark Zhandry合著；另一篇《On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds》則是由NTT社會信息學(xué)實驗室研究員Takashi Yamakawa合著。

?

由IEEE計算機學(xué)會計算數(shù)學(xué)基礎(chǔ)技術(shù)委員會（TCMF）贊助的FOCS，是理論計算機科學(xué)領(lǐng)域的頂級會議。量子計算則是本次論文征集的16個感興趣的領(lǐng)域之一。

?

隨著完全實用化成為現(xiàn)實，量子計算機將帶來巨大的應(yīng)用前景，但同時也將對現(xiàn)有的公鑰密碼系統(tǒng)構(gòu)成威脅。這兩篇論文指出了一些未來可行或不可行的可能領(lǐng)域。Mark Zhandry博士的合著論文介紹了一種用于促進量子態(tài)“倒帶”的強大技術(shù)；Takashi Yamakawa博士的論文表明，在量子態(tài)下可能無法進行非常有效的“恒定循環(huán)”ZK（Zero-Knowledge，零知識）證明。

?

NTT Research CIS實驗室主任Tatsuaki Okamoto表示：“我們很高興FOCS選擇了這兩篇論文，它們?yōu)槲覀儗罅孔用艽a學(xué)的理解開辟了新天地，值得廣泛關(guān)注。”

?

Mark Zhandry博士的論文中指出，“倒帶”是降低安全性的重要工具。在密碼學(xué)中，安全性要通過約簡證明。具體來講，約簡將攻擊者（adversary，攻擊加密算法的計算機）轉(zhuǎn)化為解決難題的有效算法（整數(shù)拆分算法、結(jié)構(gòu)化網(wǎng)格等），并圍繞該算法設(shè)計給定的密碼系統(tǒng)。

?

在“倒帶”中，則是減少將“攻擊者”運行到某個時間點，回溯到上一步，以某種方式改變“攻擊者”的觀點，然后再次運行。然而，量子算法的程序狀態(tài)非常微妙，容易在運行“攻擊者”時遭受破壞。這篇論文提出了一種針對量子攻擊者的新“倒帶”技術(shù)，通過將該技術(shù)與基于帶誤差學(xué)習(xí)（LWE）的可折疊哈希函數(shù)相結(jié)合。

?

Takashi Yamakawa的論文側(cè)重于證明ZK交互式，即允許一方（證明者）向另一方（惡意驗證者）證明聲明的內(nèi)容是真實的，并且不泄露額外信息的基本密碼原語信息。這些ZK證明協(xié)議已經(jīng)用多種語言表述，包括那些被歸類為非確定性多項式難題（NP）的語言。除了廣義表述之外，ZK證明在解決NP問題方面的效率提升也十分顯著。

?

他們通過“倒帶”技術(shù)并提供對惡意驗證者的黑盒訪問，實現(xiàn)了恒定的通信輪次與超恒定的輪次，所以存在延遲問題。也可以使用非黑盒技術(shù)，但這將使計算效率可能很低，以至于速度下降100萬倍或更多。因此，Takashi Yamakawa的論文給出了一個負(fù)面但有趣的結(jié)論：非常有效的ZK證明在量子時代可能無效。

?

曾贊助Takashi Yamakawa博士訪問普林斯頓大學(xué)的Mark Zhandry博士說，“我發(fā)現(xiàn)Takashi的工作非常有趣的是，它突出了在量子算法中一個非常微妙的問題：時間的本質(zhì)。算法在不同的輸入規(guī)模中通常會有不同的運行時間，甚至在相同的輸入規(guī)模上也會有不同的運行時間。傳統(tǒng)意義上這不是什么大問題。但Takashi的工作表明，從數(shù)量上看，（在量子算法中）這些可變的運行時間可能會帶來很大的問題。”

?

關(guān)于NTT Research

NTT Research于2019年7月開設(shè)辦事處，是一家硅谷創(chuàng)新公司，并以“開展基礎(chǔ)研究和推進技術(shù)，促進人類社會積極變革”為使命。目前， NTT Research在美國桑尼維爾設(shè)有三個實驗室：物理和信息學(xué)（PHI）實驗室、密碼學(xué)和信息安全（CIS）實驗室以及醫(yī)療健康信息學(xué)（MEI）實驗室。該組織旨在解決以下三個領(lǐng)域的現(xiàn)實問題：1）量子信息、神經(jīng)科學(xué)和光子學(xué)；2) 密碼和信息安全；3) 醫(yī)療衛(wèi)生信息學(xué)。

?

關(guān)于NTT社會信息學(xué)實驗室

NTT社會信息學(xué)實驗室是日本NTT R&D的一個部門，致力于通過 ICT技術(shù)為先進社會系統(tǒng)和人類社會的轉(zhuǎn)型發(fā)展做出貢獻。研究目標(biāo)包括：人類幸福的福祉研究；通過ICT技術(shù)和社會科學(xué)的融合為社會系統(tǒng)提供創(chuàng)新技術(shù)；建立新技術(shù)以消除網(wǎng)絡(luò)攻擊等威脅；通過對社會信息的分析和預(yù)測，建立技術(shù)以實現(xiàn)創(chuàng)新和創(chuàng)建安全的社會系統(tǒng)；通過平衡可用性和安全性的數(shù)據(jù)分發(fā)和利用，創(chuàng)建高附加值的社會系統(tǒng)；利用密碼學(xué)和物理特性創(chuàng)新數(shù)據(jù)保護技術(shù)。

?

文：businesswire

編譯：李每

編輯：慕一
注：本文編譯自“?businesswire”，不代表量子前哨觀點。

?