Lattice-Crypto
晶格問題的最壞情況硬度
我剛開始研究基於格的密碼學，我無法理解從最壞情況到平均情況減少的概念。
我們通常說，Average Case Hardness：一個問題的隨機實例很難解決。最壞情況硬度：很難解決問題的每個實例（即使大多數實例都很容易）
到目前為止，一切都很好
但我無法建立晶格和最壞情況硬度概念之間的關係。假設我們的問題是“最短向量問題（SVP）”。我知道這是一個難題，我們可以根據這個或其他相關問題的難度來證明基於格的密碼系統的安全性。
我的問題是：這個問題的實例是什麼？格子？給定基地？還是那個格子的最短向量？首先，我認為“最差”與“最短向量”有關，但我錯了。你能解釋一下嗎？
（近似）最短向量問題的一個實例只是一些格的基礎。所需的輸出是該格的任何（大約）最短的非零向量。為了在最壞的情況下解決這個問題，算法必須在給定任意格的任意基的情況下產生所需的輸出。（其他晶格問題也有類似的情況，通常包括基礎，有時還包括其他資訊，例如最近向量問題中的任意目標點。）