基於格的證明系統
原文：https://mirror.xyz/privacy-scaling-explorations.eth/4OyAht_dHsVT1MgcZTwrK2qJ-bwxpINcpBmLNfF4I2E
作者：Miha Stopar (PSE)
譯者：Kurt Pan
後量子密碼學（PQC）很重要，因為它解決了量子電腦對傳統密碼學系統構成的潛在威脅。
量子電腦利用量子力學原理，在某些情況下能夠以指數級速度進行計算，遠超傳統電腦。特別是有兩種演算法帶來了重大威脅：
Shor 演算法：能高效解決整數分解與離散對數問題，而這些問題正是廣泛使用的密碼協議（如 RSA、DSA 與 Diffie-Hellman）的基礎。
https://en.wikipedia.org/wiki/Shor%27s_algorithm
Grover 演算法：通過有效地將密鑰長度減半，降低了對稱密鑰演算法的安全性（例如，128 位元的 AES 密鑰對 Grover 演算法來說僅提供 64 位元的安全性）。
https://en.wikipedia.org/wiki/Grover%27s_algorithm
如果大規模且具容錯能力的量子電腦變得切實可行，當前許多加密、數位簽章與密鑰交換協議都將面臨安全風險。
基於格的密碼學是現代密碼學中一個極具前景的領域，可能是後量子密碼學中最通用且效能最佳的子領域。例如，摺疊方案 LatticeFold 被認為與最快的傳統基於橢圓曲線的摺疊方案同樣高效。
https://eprint.iacr.org/2024/257.pdf
相較之下，競爭的非格後量子密碼學零知識證明系統（Ligero、Aurora）僅依賴非結構化雜湊函數的安全性，但它們在計算資源需求上極為龐大。
https://eprint.iacr.org/2022/1608.pdf https://eprint.iacr.org/2018/828.pdf
在本文中，我們將探討基於格的零知識證明系統構建過程中所面臨的一些挑戰。欲獲得更深入的解釋，請參考 Vadim Lyubashevsky 的影片。
https://www.youtube.com/watch?v=xEDZ4tyesMY&t=148s
基於離散對數的零知識證明
零知識證明（ZKP）是一種密碼學協議，允許一方（證明者）向另一方（驗證者）證明某個特定陳述為真，而不透露除該陳述真實性之外的任何額外資訊。
通常，證明者可能還希望展示這些陳述的其他屬性。例如，假設對一些公開值，證明者想要證明其知道 ，使得：
以及知道，使得：
此外，證明者還想要證明對某個，
對於證明 使得 的零知識證明，可以使用 Schnorr 協議 （https://en.wikipedia.org/wiki/Proof_of_knowledge）（嚴格來說，這是一個對誠實驗證者的零知識證明，但我們暫且忽略這一細節）：
證明者選擇 並發送 給驗證者。 驗證者選擇一個挑戰值 並發送給證明者。 證明者發送 給驗證者。 驗證者檢查是否滿足 。
現在，此協議可以輕鬆擴展到證明對 的知識，使得 。在這種情況下，證明者在第一步會同樣發送 ，並在第三步發送 給驗證者。驗證者接著將檢查是否滿足 。
注意，檢查額外屬性 很直接：
此外，例如，若有 ，則線性關係 也可輕易檢查：
然而，Schnorr 協議並非量子安全，因其依賴離散對數問題，而該問題可被 Shor 演算法破解。我們能否利用格來構造類似的零知識證明呢？
基於格的零知識證明
離散對數問題是指在給定 的情況下求 。在基於格的密碼學中，有一個類似的問題：最短整數解 （SIS）問題。
考慮線性方程組
其中 且 ，這個方程組可以利用高斯消去法在多項式時間內求解。
但是，這個問題的變體可能變得困難。例如，當我們要求 的範數小於某個界限 時。請注意，這個界限必須小於 ；否則， 就是一個平凡解。
SIS 問題 是指尋找 使得
我們能否針對這樣的 構造類似 Schnorr 的零知識證明？
基於格的 Schnorr 協議
令使得
且
下面的協議可行嗎？
協議的最後一步會是驗證者檢查是否滿足
然而，這樣做並不可行。問題在於 可能並不「短」（即範數不小）；如果我們不要求 小，證明者就可以利用高斯消去法構造出一個滿足 的 ！
因此，必須要求 小。為了達到這個目的，挑戰值 也必須小（注意 ），但另一方面，我們希望挑戰空間足夠大一一挑戰值越大，其健全性就越好。需要注意的是，如果證明者能預測挑戰 ，那麼證明者可以將第一個訊息設為 ，而最後一個訊息設為 。
這也是為何使用環 的原因之一——它提供了具有小範數的元素的一個大集合（即具有小係數的多項式，而非僅僅是小整數）。
在最後一步，驗證者還必須檢查 是否足夠小。
然而，這並不是基於格的 Schnorr 版本所面臨問題的全部。
如果這是一個證明 知識的證明，我們可以從證明者那裡提取出 的值。這通常通過迴繞（rewinding）來完成：我們作為黑盒運行證明者兩次，獲得兩個腳本： 與 。由此得到
在 Schnorr 演算法中，可以直接計算
求出滿足 的秘密 。利用格，我們可以求得 （可假設 是可逆的），使得 。然而，問題仍在於 可能並不夠小！
因此，使用格，我們只能提取出 使得
其中 以及 。
注意，雖然 的範數仍然較小（雖然沒有 那麼小），但對於給定的 與 來說，要找出這樣的 與 依然是困難的。
接下來，你將會看到提取器（extractor）如何“僅”返回 的 ，但這仍可用於構造基於格的證明系統。
基於格的承諾方案
基於格的證明系統發展過程中的重要一步，就是論文《More Efficient Commitments from Structured Lattice Assumptions》的發表。該論文中描述的承諾方案流程如下：
https://eprint.iacr.org/2016/997.pdf
密鑰生成
密鑰生成返回 和 分別為
其中 是隨機取自 ， 是隨機取自.
承諾
為了承諾 ，我們選擇一個隨機小範數多項式向量 ，輸出承諾
打開
一個承諾的有效打開
是一個三元組 , 和.
驗證者檢驗：
打開證明
上述協議的提取器
注意此承諾方案的打開值不僅僅包含 與 ；它還包含一個多項式 。這是由於前述提取器所面臨的問題所致。
提取器需要返回滿足下列條件的三元組
該元組可以通過迴繞得到：
接著我們有：
其中 ， .
因此，不是有 ，我們有 .
我們提取 為:
提取的元組為 。很容易看到 :
結論
自上述承諾方案問世以來，基於格的零知識證明領域已取得許多新進展。因此，請期待更多關於基於格以及其他後量子密碼學方案的新資料。於 PSE，我們致力於站在這一快速發展領域的前沿，不斷跟進並測試最新的後量子密碼學進展。我們的目標是確保在轉向量子安全系統的過程中，能夠充分應對挑戰與抓住機遇。