減少點陣基的目的是什麼？
這可能是一個過於寬泛的問題，但事實並非如此。我已經研究格子幾個月了，更具體地說，我研究的是：
- 格子問題 ( $ SVP $ , $ CVP $ 等等。）
- 後量子電腦中的格密碼學
- 格密碼學中的最壞情況硬度
- 使用 Lattice 的公鑰加密
- 格約簡算法（LLL 及其執行時間）
但是，我無法弄清楚與減少晶格基和晶格問題的關係。本質上，為什麼我們要減少格基？我知道減少格基的目標是獲得短且幾乎正交的基向量，但為什麼呢？更大的圖景是什麼？
公平地說，在過去幾個月的閱讀論文中，我發現只有幾個句子（這里和那裡）：
減少的鹼基允許精確或近似地解決以下重要的晶格問題（SVP、CVP）
如果我能得到一個方向或提示或其他東西來幫助我弄清楚這個概念，我將不勝感激。
格子加密中的格子減少
首先，格子減少在格子加密的背景下很有趣，因為正如其他答案中已經說明的那樣，它們允許我們在格子中找到短向量，這與 SVP（找到格子中的最短向量）有關。
我們關心解決 SVP，因為人們認為從帶錯誤的環學習 (RLWE)到 SVP 可能會降低安全性。因此，如果我們能夠解決 SVP（通過一些技術，例如格子縮減），我們可能能夠破解基於 RLWE 的方案，例如這些同態加密和密鑰 交換方案。
應該注意的是，諸如 LLL 之類的歸約技術不允許我們有效地求解高維格的 SVP，因此它們不能有效地破壞這些方案。
數論加密中的格約簡
但也有“經典”數論加密的應用。我將解釋一個（幾個）可能的應用程序。假設我們要攻擊（EC）DSA，其中隨機數是用偏置位生成的。事實證明，我們可以使用格歸約來恢復私有簽名密鑰。
如果我們能得到足夠多的消息/簽名對，它們都使用具有相同偏差的隨機數，那麼我們實際上可以編寫一個方程組（每個方程對應一個消息/簽名對），它可以被解釋為一個格子（就像你如何可以使用線性代數中的增廣矩陣來表示方程組）。
然後我們可以在這個方程組上實際執行晶格縮減（例如 LLL）。如果我們有足夠的消息/簽名對，那麼極有可能減少基礎中的條目之一將是私有簽名密鑰。這種攻擊的細節可以在這篇論文中找到。
在這種情況下，有關晶格減少的更多資訊，我鼓勵您查看論文Lattice Reduction: a Toolbox for the Cryptanalyst。
當它由短的、幾乎正交的向量給出時，更容易確定晶格的結構。例如，這組格點在
$$ \Lambda = \mathbb{Z}(-3,4) + \mathbb{Z}(5,-7) $$ 看起來像？關於什麼 $$ \Lambda = \mathbb{Z}(1,0) + \mathbb{Z}(0,1)? $$ 對於兩者來說，它是 $ \mathbb{Z}^{2} $ ，但在第二種情況下更容易確定。