基於格的難題你只說了一個RLWE，不知你是不是已經了解基於格的其它難題。參照剛才在另外一個問題中的回復。
密碼學難題還有很多。說幾個比較熱門的。基於格的密碼難題 \rm SVP
和 \rm CVP
，這兩個難題都是抗量子的。還有基於他們構建的LWE和RLWE問題，它們是構建全同態加密的基礎。
相關的知識內容可關註我並去我專欄學習。
下面我們來講下基本的\rm SVP
和 \rm CVP
。
最短向量問題 \rm SVP
讓我們定義最基本的涉及格的計算難題：最短向量問題，簡稱 \rm SVP
。 在這裏，我們給出了一個格，需要我們找到最短的非零格點。 更準確地說，\rm SVP
有三個變體，這取決於我們是否必須實際找到最短的向量，找到它的長度，或者僅僅取決於它是否比某些給定的數位小：
Search
\rm SVP
: 給定格基 B∈\mathbb{Z}^{m×n}
求 v∈\mathcal{L}(B)
，使 ||v||=λ_1(\mathcal{L}(B))
。
Optimization
\rm SVP
: 給定格基 B∈\mathbb{Z}^{m×n}
，找到 λ_1(\mathcal{L}(B))
。
Decisional
\rm SVP
:給定格基 B∈\mathbb{Z}^{m×n}
和有理數 r\in \mathbb{Q}
，判斷λ_1(\mathcal{L}(B))\leq r
是否成立。
註意，我們限制格基由整數向量組成，而不是任意的實向量。這樣做的目的是使輸入以有限的多位表示，這樣我們就可以將 \rm SVP
視為一個標準的計算難題。我們還可以允許格基由有理向量組成。這將導致一個本質上等價的定義，因為透過縮放，可以使所有有理數座標都是整數。
上述三個變體之間的兩個簡單關系是，決策變體不比最佳化變體更難，最佳化變體不比搜尋變體更難。 事實上，可以證明逆向也是正確的：最佳化變量不比決策變量更難，搜尋變量不比最佳化變量更難。 總之，這三個變體本質上是等價的。
最近的向量問題 \rm CVP
另一個基本格難題是最近的向量問題，簡稱 \rm CVP
，i.e.，目標是找到最接近給定空間點的格點。 和以前一樣，對於任何近似因子 \gamma \geq 1
，我們可以定義三個變體：
Search
\rm CVP_\gamma
: 給定格基 B∈\mathbb{Z}^{m×n}
和向量 t\in \mathbb{Z}^{m}
，尋找 v\in \mathcal{L(B)}
使得 ||v-t|| \leq \gamma \cdot {\rm {dist}} (t, \mathcal{L}(B))
。
Optimization
\rm CVP_\gamma
：給定格基 B∈\mathbb{Z}^{m×n}
和向量 t\in \mathbb{Z}^{m }
，求 d
使d≤{\rm dist}(t，\mathcal{L}(B))≤\gamma\cdot d
。
Promise
\rm CVP_\gamma
: 由 a triple (B,t,r)
給出一個難題例項，其中 B∈\mathbb{Z}^{m×n}
是格基， t∈\mathbb{Z}_m, r∈\mathbb{Q}
。 在 YES 例項中， {\rm dist}(t，\mathcal{L}(B)≤r
。在沒有情況下， {\rm dist}(t，\mathcal{L}(B)\geq r
。
\rm CVP
和 \rm SVP
都是困難的計算問題，我們將在本課程後面更詳細地討論這些問題。 還有一些格中容易計算的問題，如：
Membership
: 給定格基 B∈\mathbb{Z}^{m×n}
和向量 v\in \mathbb{Z}^{m}
，decide v
是否屬於 \mathcal{L}(B)
。 方程式 Bx=v
可以看作是 n
個變量中的 m
線性方程式組。 因此，我們可以透過高斯消除來有效地解決它。 如果一個解存在，並且它恰好在 \mathbb{Z}^n
(as opposed to \mathbb{Q}^n
)中，則輸出YES；否則輸出NO。
Equivalence
: 給定格基 B_1, B_2∈\mathbb{Z}^{m×n}
, decide if \mathcal{L}(B_1) = \mathcal L(B_2)
。 為了解決這個問題，我們檢查了兩件事： B_1
的每一列都包含在 \mathcal L(B_2)
中， B_2
的每一列都包含在 \mathcal L(B_1)
中。 如果 \mathcal{L}(B_1) = \mathcal L(B_2)
，則滿足這兩個檢查。 相反，如果滿足這些檢查，則 \mathcal{L}(B_1) \subseteq \mathcal L(B_2)
和 \mathcal{L}(B_1) \supseteq \mathcal L(B_2)
，因此 \mathcal{L}(B_1) = \mathcal L(B_2)
。
