論文《How to Meet Ternary LWE Keys》：什麼是 t 以及它是如何使用的
我一遍又一遍地閱讀了A. May 的這篇論文，但是，可能因為我是這個領域的新手，我沒有成功理解 MEET-LWE 部分。
特別是，在第 5 部分中，它聲明選擇“隨機選擇的目標向量” $ t ∈ \mathbb{Z}_r^q $ . 後來，據說值 $ s1 $ 令人滿意的 $ π_r (As1 + e1) = t $ 可能是 LWE 系統的解決方案，和 s2 類似的東西。因此我的問題是：
- 是 $ t $ 真的完全隨機還是我錯過了什麼？為什麼大小 $ r $ ?
- 我們怎樣才能減少搜尋空間 $ s $ 使用提到的方程及其等價物 $ s2 $ ?
所以幾週後，我成功地找到了我的問題的一些答案。
真的是完全隨機的還是我錯過了什麼？
是的，t 是為了減少搜尋空間的歧義。一切都始於這樣的想法，例如： $ \begin{bmatrix} 1 \ -1 \ 0 \ -1 \ 1 \ 0 \ \end{bmatrix}
\begin{bmatrix} 1 \ 0 \ 0 \ -1 \ 0 \ 0 \ \end{bmatrix} + \begin{bmatrix} 0 \ -1 \ 0 \ 0 \ 1 \ 0 \ \end{bmatrix}
\begin{bmatrix} 1 \ -1 \ 0 \ 0 \ 0 \ 0 \ \end{bmatrix} + \begin{bmatrix} 0 \ 0 \ 0 \ -1 \ 1 \ 0 \ \end{bmatrix} $
這兩種向量組合導致相同的結果。但是瀏覽兩者是沒有用的，因為它們的組合是相同的。因此，可以通過忽略一些冗餘組合來減少搜尋空間，為此我們將一些值設置為 LWE 方程右側的常數（即 $ As $ 並不是 $ s $ ) 因為一些數學性質（A. May 引入的投影的同態性）。
為什麼大小 $ r $ ?
$ r=floor(log_q(R)) $ 在哪裡 $ R $ 是我們尋找的向量的表示空間的大小。在上面的例子中， $ R\geq2 $ 因為我們找到了兩種表示向量的方法。就這樣 $ log_q $ 其中 $ R $ 是空間中的座標數 $ \mathbb{Z}_r^q $ 我們可以將其設置為固定值以減少搜尋空間。但是，這個座標數必須是整數，因此我們對所獲得的座標進行四捨五入。
我們怎樣才能減少搜尋空間 $ s_1 $ 使用提到的方程及其等價物 $ s_2 $ ?
一種利用它的方法是應用匹配和過濾方法：
- 生成所有可能的一半 $ s_1 $ 正如 A. May 所描述的
- 合併它們並過濾，即拒絕獲得的 $ s_1 $ 如果 $ \pi_r(As_1) \ne t $ 或者如果它不是具有良好漢明權重的有效三元向量
- 做相當於 $ s_2 $ （注意方程 $ t $ 與我們在樹的右側不一樣）
- 將這些向量與 Odlyzko 散列相結合，並檢查 LWE 方程
當然，這必須適應更大的樹。