證明一個小的 Ring-LWE 秘密是唯一的
我只想知道我的證明是否正確，即證明如果 Ring-LWE 秘密很小，那麼它是唯一的。在給出我的證明之前，這是一個事實：
事實1： $ \Pr [\Vert r \Vert_\infty \leq \beta: r\xleftarrow{\$} R_q]\leq \left(\dfrac{2\beta+1}{q}\right)^n $ ， 在哪裡 $ R_q=\mathbb{Z}_q[X]/(X^n+1) $ ， 在哪裡 $ n $ 是二的冪， $ q $ 是一個素數並且 $ \beta $ 是一些正實數。
現在，讓 $ D_\sigma $ 是離散高斯分佈 $ R=\mathbb{Z}[X]/(X^n+1) $ （也可以看作是離散高斯 $ \mathbb{Z}^n $ 通過係數嵌入 $ R $ 至 $ \mathbb{Z}^n $ . 另一個事實：
事實2： $ \Pr[\Vert z\Vert_\infty \leq \mathcal{O}(\sigma\sqrt{n}): z\leftarrow D_\sigma]>1-2^{-n} $ 為適當的選擇 $ \sigma $ .
現在假設 $ a\xleftarrow{\$}R_q $ 和 $ s,e\leftarrow D_\sigma $ 以便 $ b=as+e $ ， 因此 $ (a,b) $ 是秘密的 RLWE 樣本 $ s $ . 因此， $ \Vert s\Vert_\infty,\Vert e\Vert_\infty $ 都小於 $ \beta=\mathcal{O}(\sigma\sqrt{n}) $ 以事實 2 的壓倒性機率。
現在我想證明不可能找到另一個 $ s^\prime, s^\prime\neq s $ , $ \Vert s^\prime\Vert_\infty\leq \beta $ 這樣 $ b=as^\prime+e^\prime $ , $ \Vert e^\prime \Vert_\infty\leq \beta $ 以壓倒性的機率。這是我的論點：
以矛盾進行。認為 $ b=as^\prime+e^\prime $ . （假使，假設 $ a $ 是一個可逆元素 $ R_q $ , 這種情況下的機率是壓倒性的 $ q=3\pmod{8} $ ）。然後 $ s^\prime=a^{-1}(b-e^\prime)=a^{-1}(e-e^\prime)+s $ . 因此， $ (a^{-1},s^\prime) $ 是秘密的 RLWE 樣本 $ e^\prime-e $ 自從 $ a^{-1} $ 是一致隨機的，因為 $ a $ 是均勻隨機的。因此，這樣的 $ s^\prime $ 與中的均勻隨機元素無法區分 $ R_q $ 由決策-RLWE 假設。但根據事實 1，對於 $ q>4\beta +2 $ , 的機率 $ \Vert s^\prime \Vert_\infty \leq \beta $ 是 $ <2^{-n} $ . 因此，這麼小的 $ s $ 是獨一無二的，具有壓倒性的機率。（這也說明如果我們不對 $ s $ , RLWE 的秘密 $ b $ 不是唯一的，因為我們可以簡單地構造這樣的 $ s^\prime $ ).
所以，我想知道我的論點是否正確，並希望任何人提供任何有用的回饋。
您試圖做出的陳述是資訊論的（某物的存在），而不是計算的（找到某物的容易程度），因此您呼叫 RLWE 硬度假設這一事實令人擔憂。
您確實有權做的一件事是確實考慮兩種解決方案的區別 $ [\mathbf A; \mathbf I] \cdot (s-s’, e-e’) = 0 $ . 事實上，這些差異的集合形成了 SIS 格，所以你基本上是在試圖證明沒有 SIS 解決方案可以解決 $ 2\beta $ 在裡面 $ \ell_\infty $ 規範。換句話說，要證明 RSIS 格的最小距離在 $ 2\beta $ .
標准證明策略如下：
- 考慮每個非零 $ z $
- 對於一個隨機 $ \mathbf A $ ， 注意 $ \mathbf Az $ 是統一的
- 限定機率 $ \mathbf Az $ 落入一個半徑球 $ 2\beta $ （使用你的第一個事實）
- 對所有的應用聯合綁定 $ z $ 範數小於 $ 2\beta $
- 得出結論。
您可以在各種講義中找到此類證明的詳細資訊（例如，https ://homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-9.pdf 的引理 5 ）。這通常是針對一般晶格（沒有環結構）給出的，但是，除了不可逆性問題（你已經想出瞭如何處理 $ q \cong 3 \mod 8 $ ) 證明可以適應環設置。