自量子密碼成立以來，已經在量子計算機算法方面開展了大量工作。最重要的，與密碼學最相關的是Grover搜索算法（Grover’s algorithm）和Shor因式分解算法（Shor’s algorithm）。
首先，我們來討論Grover搜索算法。計算中的經典問題是給出N個項目的列表X以在列表中搜索具有屬性的項目，我們將稱之為P。在數學上我們正在尋找X中的x使得P(x) = 1，比如說。現在，如果X是非結構化集合，那么通常我們能做的最好就是獲取X中的每個元素并測試P(x) = 1。如果我們懷疑只存在一個這樣的x，那么這將需要N步。密碼學上認為X是AES的密鑰集合，P(x)是測試密鑰是否將一個明文映射到給定密文的函數。傳統的做法是，我們嘗試定義密碼，讓它努力尋找x，使得該P(x) = 1完全由N給出。
然而，量子可以讓我們做的更好。Grovers搜索算法可以在sqrt(N)步驟中解決上述問題。這意味著具有128位密鑰的AES密碼在量度上僅提供64位安全性，而不是128位安全性。對于分組密碼，這意味著如果我們希望防止量子攻擊，我們需要將密鑰大小加倍。
Grovers搜索算法的另一個應用是在哈希函數中查找沖突。散列函數H中的沖突是一對值x和y，如H(x) = H(y)。哈希函數旨在使查找沖突變得困難。在簽名之前對消息進行數字簽名方案中需要這樣做。因為如果你可以找到碰撞(x，y)，那么你可以將消息x上的簽名作為簽名傳遞給消息y。
傳統上，如果哈希函數的輸出是來自大小為N的集合X的元素，并且輸出基本上是隨機的，那么找到碰撞的最佳算法將采用sqrt(N)步驟。但是，Grovers的搜索算法可以適應這種情況，它允許我們在N ^ {1/3}步驟中量子地找到碰撞。因此，如果我們的哈希函數是量子安全的，我們需要使用具有更大輸出長度的散列函數。
然而，Shor的因式分解算法最有趣的量子算法。該算法實際上做的是找到有限abelian群中的循環長度。Shor的算法可以在很短的時間內解決這個問題，這是我們不知道如何在經典計算機上做的事情。各種有趣的加密問題可以降低到在有限的阿貝爾群中找到循環長度的問題。最重要的是分解數字并找到離散對數。問題是，因式分解和離散對數是當今使用的所有公鑰密碼體制的基礎。因此，量子計算機的發展將使所有部署的公鑰算法立即變得不安全。
總而言之，如果構建量子計算機，我們必須增加對稱密碼的密鑰長度，例如AES（比如使用AES-256而不是AES-128），我們需要找到新的公鑰算法。
版權申明：本內容來自于互聯網，屬第三方匯集推薦平臺。本文的版權歸原作者所有，文章言論不代表鏈門戶的觀點，鏈門戶不承擔任何法律責任。如有侵權請聯系QQ：3341927519進行反饋。
