在我的遠端密碼學課程中，一項作業涵蓋了基於格的密碼學。這很難，我迷路了。沒有人可以幫助我。

到目前為止，我已經明白：

• 格子是歐幾里得空間中規則有序點的集合（它的術語像這樣讓我搜尋了好幾天的答案）。
• 可以通過稱為基的 n 個向量定義晶格，其中 n = 維度（目前，我在維度 2 中工作），並且可以通過將基中每個向量的正或負倍數應用於另一個向量來找到任何其他基在基礎上。
• 將晶格 L1 定義為一組點允許將整個集合乘以某個係數，這實際上會將其轉換為新的晶格 L2。
• 基向量的行列式本質上告訴我們平行六面體的體積（二維面積），它將重複形成晶格，晶格點是頂點。

但現在我被困住了：我如何將所有這些轉移到密碼學中？我有一個問題，要求我計算一個函式的 3 個輸入的輸出：

我們將看到 q-ary 格提供可證明的抗碰撞散列。我們選擇整數 q；a和b。我們的雜湊函式（由 Mikl´os Ajtai 在 1996 年的一篇突破性論文中提出）是一個 2 變數函式：h(x, y) = ax + by mod q。(a) 對於 q = 5；a = 14; b = 13; 計算 h(17, 8), h(21, 16) 和 h((17, 8) - (21, 16))

找到答案後……

h(17, 8) = 14*17 + 13*8 = 342 mod 5 = 2; 
h(21, 16) = 14*21 + 13*16 = 502 mod 5 = 2; 
h((17, 8)-(21, 16)) -> (h(-4, -8) = 14*-4 + 13*-8 = 160 mod 5 = 0

我相信這意味著在前兩個點上，格子已經移動了 5 加 2 的某個倍數，這使它位移了 2，從而形成了一個新的格子。而在最後一種情況下，晶格已經移動了其行列式的倍數，因此是同一個晶格。

但是，我無法理解雜湊的連結。在應用程序中，點是明文，答案是modulo 5散列函式的輸出嗎？如果是這樣，會不會有太多的碰撞？我們已經看到了導致答案為 的兩個範例2。如果它們不是同一個東西，這與最短向量問題或短整數解決方案有何联系？q-ary lattice 是否只是一種嘗試儲存複製晶格所需的基本模式？如果是這樣，格子本身不是明文和基本模式（由基礎和行列式給出）雜湊函式的答案嗎？您將如何使用點陣加密消息？

我希望我能找到一些用英語而不是符號來解釋這一點的文字……像這樣。希望我沒有重複。

恐怕你也無法將其理解為 DW，但讓我們開始吧。我有時無法理解你的問題。如果可能，請重述它們。

Ajtai 雜湊函式的定義

讓 $ n $ , $ m $ ， 和 $ q $ 為正整數。讓 $ R = \mathbb{Z}_q $ 是整數模的商環 $ q $ . 讓我們定義一個函式，它將一個向量映射到 $ D^m \subset R^m $ 到 $ R^n $ 並由矩陣索引 $ \boldsymbol{A} \in R^{n \times m} $ 如下：

$ f_\boldsymbol{A}(\vec{x}) = \boldsymbol{A} \vec{x} \bmod{q} = \sum_{i=1}^{m} x_i \vec{a}_i \bmod{q} $ .

Ajtai 散列函式被定義為上述散列函式的家族；

$ \mathcal{F}{n,m,q,D} = {f{\boldsymbol{A}}:D^m \to R^n \mid \boldsymbol{A} \in R^{n \times m}} $ .

您可以通過設置獲得您的功能 $ n=1 $ , $ m=2 $ , $ q=5 $ ， 和 $ D = R $ ; 然後設置 $ \vec{a}_1 = 14 \ (= 4) $ 和 $ \vec{a}_2 = 13 \ (= 3) $ .

例如，您可以設置 $ n = 256 $ , $ q = 4097 $ , $ m = 4096 $ ， 和 $ D = {0,1} $ . 函式的輸入是一個長度為的位串 $ 4096 $ 並且函式對這些參數的輸出是 $ 256 $ 維向量，其係數在 $ \mathbb{Z}_q $ .

是不是在縮小？

良好的參數使上述功能縮小。正確地說，如果域的大小大於範圍的大小，即 $ |D|^m > |R|^n $ ，函式（顯然）在縮小。

一個可能的參數選擇是 $ D = {0,1} $ 和 $ m > n \log_2(q) $ ，它經常出現在上下文中。另一種可能的選擇是 $ D = {-1,1} $ 或者 $ D = {-1,0,1} $ .

很難找到碰撞嗎？碰撞和短向量之間有什麼關係？

如果它們不是同一個東西，這與最短向量問題或短整數解決方案有何联系？

如果 $ D = R $ ，通過線性代數的冪很容易找到碰撞是函式。如果你可以使用高斯消元法 $ R $ 是一個欄位。但是，如果 $ D \subset R $ 和大小 $ D $ 小了，就變硬了。粗略地說，碰撞次數取決於配給 $ |D|^m/|R|^n $ .

1996 年，Ajtai 表明，對於好的參數，如果存在他的散列函式的反相器，那麼存在一種算法從任意 $ n $ 維晶格。Goldreich、Goldwasser 和 Halevi 在您提到的註釋中指出，如果存在找到 Ajtai 雜湊函式衝突的算法，那麼存在從任意 $ n $ 維晶格。減少是基於這樣一個事實，即短向量的總和（相對）短。

我們應該如何用格子詞來解釋上面的內容？

你會跳過這部分。

我們定義一個與矩陣相關的格 $ \boldsymbol{A}\in R^{n \times m} $ 作為

$ \Lambda = \Lambda_q^{\perp}(\boldsymbol{A}) = {\vec{e} \in \mathbb{Z}^m \mid \boldsymbol{A} \vec{e} \equiv \vec{0} \bmod{q}} $ .

這 $ \Lambda $ 是一個 $ m $ 維晶格。（您可以通過驗證任何兩個向量來檢查這是一個格子 $ \vec{e}, \vec{e}’ \in \Lambda $ ，它們的和位於 $ \Lambda $ 再次。你可以檢查這是 $ m $ -維通過驗證任何 $ q \vec{u}_i $ 在 $ \Lambda $ ， 在哪裡 $ \vec{u}_i $ 是單位向量）。

這個格子定義了一個地圖 $ \mathbb{Z}^m $ 到商群 $ \mathbb{Z}^m/\Lambda $ , 同構於 $ R^n $ . 該映射是一個雜湊函式。

反之，碰撞 $ \vec{e} \neq \vec{e}’ $ 為了 $ f_{\boldsymbol{A}} $ 意味著一個短的非零向量 $ \vec{e}-\vec{e}’ $ 在 $ \Lambda_q^{\perp}(\boldsymbol{A}) $ .

引用自：https://crypto.stackexchange.com/questions/14357