KDDI 研發實驗室和九州大學正在參加一項密碼分析競賽(由德國達姆施塔特工業大學主辦,預計來自世界各地的密碼學研究人員將參加該競賽。)宣佈在該競賽中首次破譯了該問題。世界。
密碼學在網絡上用於金融領域的交易安全。在稱為公鑰加密的方法中,使用兩種數學上相關的密鑰(公鑰和私鑰)交換信息。然而,由於擔心量子計算機實現時會被破譯,因此正在考慮一種稱為“格密碼學”的高難度公鑰密碼系統。
LWE 問題是求解有意添加誤差的多維聯立線性方程的問題。這相當於破譯格密碼。要實現安全加密,需要增加LWE問題的維數(未知變量的數量)或者增加誤差以使其難以破譯。但如果維數太高,計算時間就會增加,如果誤差太大,則無法進行正確的密碼處理的概率就會增加。為此,許多研究機構正在進行高速求解方法的研究,以找到保證安全性的最佳誤差維度和大小。
此次,研究組成功對解密算法進行了加速和並行化,通過使用商業雲中的20台虛擬PC,可以解決用暴力破解需要一萬多年的60維問題。使用超級計算機的方法,我用了大約16天的時間破解了LWE問題。他們還破譯了維度為 55 或更小的問題。
這項研究的結果將為確定使用格密碼作為下一代公鑰密碼系統時的安全維度和錯誤大小提供重要信息。未來,他們希望進一步推進加速解密算法的研究,實現高速、安全的下一代公鑰密碼系統。