數字生活愈發依賴密碼學的保護。每當發送私信或網上支付時，你都在依靠算法保護數據安全。為了確保這些系統不被破解，研究人員不斷測試其強度。
LLL算法(以1982年發表論文的三位研究者Arjen Lenstra、Hendrik Lenstra Jr.和 László Lovász命名)是重要工具之一。LLL及其衍生算法有時能破解密碼系統，通過研究其行為，可以設計更安全的系統。此外，該算法在計算數論等高等數學領域也有用處。
多年來，研究人員不斷優化LLL算法的變體，但效果有限。最近，兩位密碼學家開發了一種更有效的LLL類算法，顯著提升了效率。這項新技術在2023年國際密碼學大會上獲得最佳論文獎，將為計算機科學家和數學家使用LLL類方法拓展更多可能。
密西根大學密碼學家克里斯·佩克特(未參與論文研究)稱這項技術令人興奮，雖然研究了幾十年，但仍有驚喜發現。
LLL類算法在格世界中運行，這裡是指由規則排列的無限點集。可以想像你正在鋪地板，可以用方形地磚，地磚的角就構成了一個格。你也可以選擇其他形狀的地磚，比如長平行四邊形，形成不同的格。
每個格都可以用「基」描述，這是一個向量集(本質上是數字列表)，通過不同方式組合這些向量，可以得到格中的所有點。例如，一個格的基由兩個向量組成：[3,2]和[1,4]。這個格就是所有通過加減複製這兩個向量的點。
但這不是唯一的基，每個維度大於2的格都有無限多個可能的基。不過，並非所有基都一樣好用。向量更短、互相近乎正交的基通常更容易處理，更適合解決某些計算問題，因此被稱之為「好」基。下圖中的藍色向量就是例子。「壞」基的向量更長，也不那么正交，比如紅色向量。
這就是LLL要做的事：輸入多維格的基，它會輸出一個「更好」的基。這個過程稱為格基約簡。
這與密碼學有什麼關係呢？在某些情況下，破解密碼系統的任務可以轉換為另一個問題：在格中找到一個相對較短的向量。而有時，這個向量可以從LLL類算法生成的簡化基中找到。這種策略幫助研究人員攻克了一些看似與格毫無關聯的系統。
從理論上講，原始LLL算法運行速度很快：運行時間不會隨輸入大小(格的維度和基向量中數字的比特數)呈指數級增長。但是它會以多項式函數增加，加密研究員杜卡斯表示，如果實際操作，多項式時間並不總是可行的。
這意味著原始LLL算法無法處理太大輸入。研究人員一直致力於優化LLL類算法以支持更大輸入，取得了不錯的效果。但一些任務仍然無法解決。
萊恩和他的導師亨寧格合著的新論文結合了多種策略來提高他們的LLL類算法的效率。一方面，該技術使用遞歸結構將任務分解成更小的塊。另一方面，算法仔細管理涉及數字的精度，在速度和正確結果之間找到平衡。這項新工作使研究人員能夠簡化具有數千個維度的格基。
過去的工作也採用了類似的方法：2021年的一篇論文也結合了遞歸和精度管理來快速處理大型格，但它只適用於特定類型的格，並不適用於所有在密碼學中重要的格。新的算法在更廣泛的範圍內表現良好。密碼研究人員埃斯皮托說，他很高興有人做了這件事，他們的工作提供了「概念證明」，新的結果表明「你可以非常快速地進行格約簡」。
新技術已經開始發揮作用。數學家佩奇說，他和他的團隊已經將改編後的算法用於一些計算數論任務。
LLL類算法還可以在設計抗未來量子計算機的格密碼系統研究中發揮作用。它們不會威脅到這些系統，因為攻克它們需要找到比這些算法能實現的更短的向量。但已知最好的攻擊方法將LLL類算法作為「基本構建塊」，研究人員可以通過新的工具擴展可運行的攻擊算法實驗範圍，更清晰地了解其性能。
