如何證明從決定到 LWE 的減少？

我是密碼學的新手，並試圖正式理解 LWE（錯誤學習）的概念。我將說明我對定義的理解，這可能是不正確的。

根據我的理解定義

讓R $ R $ 是具有機率的有限單位交換環μ $ \mu $ （誰的σ $ \sigma $ -代數是離散的）。R $ R $ 據說滿足最壞情況搜尋 LWE 假設，如果對於所有多項式n $ n $ 和所有多項式時間隨機算法小號 $ S $ ， 地圖 米↦分鐘s∈R米p(米,s),$$ \begin{equation} m\mapsto \min_{s\in R^m} p(m,s)\text{,} \end{equation} $$ 在哪裡 p(米,s)=公關{(一個,和)∈R米×n(米)×Rn(米):小號(−s一個+和,一個)=s},$$ \begin{equation} p(m,s) = \Pr{(A,e)\in R^{m\times n(m)} \times R^{n(m)}: S (-sA+e,A)=s}\text{,} \end{equation} $$ 可以忽略不計。在上述等式中，一個 $ A $ 從均勻機率中採樣，並且和 $ e $ 從產品機率中採樣μn(米) $ \mu^{n(m)} $ .

R $ R $ 據說滿足最壞情況決策 LWE 假設，如果對於所有多項式n $ n $ 和所有多項式時間隨機算法D $ D $ ， 地圖 米↦分鐘s∈R米|p1(米,s)−p2(米)|,$$ \begin{equation} m\mapsto \min_{s\in R^m} |p_1(m,s)-p_2(m)|\text{,} \end{equation} $$ 在哪裡 p1(米,s)=公關{(一個,和)∈R米×n(米)×Rn(米):D(−s一個+和,一個)=1},p2(米)=公關{(b,一個)∈Rn(米)×R米×n(米)×:D(b,一個)=1},$$ \begin{equation} \begin{split} p_1(m,s) &= \Pr{(A,e)\in R^{m\times n(m)}\times R^{n(m)}: D (-sA+e,A)=1},\ p_2(m) &= \Pr{(b,A)\in R^{n(m)}\times R^{m\times n(m)}\times: D (b,A)=1}\text{,} \end{split} \end{equation} $$ 可以忽略不計。在上述等式中，一個 $ A $ 和b $ b $ 從均勻機率中採樣，並且和 $ e $ 從產品機率中採樣μn(米) $ \mu^{n(m)} $ .

問題

我證明瞭如果R $ R $ 是一個帶有機率的有限域μ $ \mu $ （誰的σ $ \sigma $ -代數是離散的）並且如果R $ R $ 滿足最壞情況搜尋 LWE 假設，則R $ R $ 也滿足最壞情況決策 LWE 假設。但是如何證明反過來呢？到目前為止我所看到的所有文獻都只是說它是微不足道的，但我無法證明它。更明確地說，我需要以下陳述的證明：

如果R $ R $ 是具有機率的有限單位交換環μ $ \mu $ （誰的σ $ \sigma $ -代數是離散的）並且如果R $ R $ 滿足最壞情況決策 LWE 假設，則R $ R $ 也滿足最壞情況搜尋 LWE 假設。

我的嘗試

假使，假設R $ R $ 滿足最壞情況決策 LWE 假設。讓n $ n $ 是一個多項式並讓小號 $ S $ 是多項式時間隨機算法（其輸入是Rn(米)×R米×n(米) $ R^{n(m)}\times R^{m\times n(m)} $ 並且其輸出是元素R米 $ R^m $ ）。我們需要證明地圖 米↦分鐘s∈R米p(米,s),$$ \begin{equation} m\mapsto \min_{s\in R^m} p(m,s)\text{,} \end{equation} $$ 在哪裡p(米,s) $ p(m,s) $ 定義如上，可忽略不計。給定一個輸入(b,一個)∈Rn(米)×R米×n(米) $ (b,A)\in R^{n(m)}\times R^{m\times n(m)} $ 在哪裡b=−s一個+和 $ b=-sA+e $ ,小號 $ S $ 會返回一些猜測G∈R米 $ g\in R^m $ 可能等於也可能不等於s $ s $ . 一個可以計算b+G一個 $ b+gA $ 並表示為和′ $ e’ $ . 如果G=s $ g=s $ ， 然後和′=和 $ e’=e $ . 如果G≠s $ g\neq s $ ， 然後和′=和 $ e’=e $ 可能持有也可能不持有。我不知道現在該怎麼辦。

由於您非常接近正確答案，因此我不會給您正確答案，而是會給您定性描述您需要做的最後一步。

根據選擇的精確誤差分佈和 $ e $ 從，LWE 分佈(一個,s一個+和) $ (A, sA + e) $ 可以是：

1. 完全是均勻分佈（比如說，如果和 $ e $ 是均勻隨機的）
2. 在計算上可與製服區分開來（例如，如果和 $ e $ 支持{0} $ {0} $ ）， 或者
3. （被認為是）在計算上與製服（如果和 $ e $ 是“有界的”——您可以明確地將其視為具有參數的 iid 高斯座標≈n $ \approx n $ ).

在考慮隨機變數時，請牢記這三種情況(一個,s一個+和) $ (A, sA+e) $ . 請注意（對於固定一個 $ A $ ） 地圖s↦s一個 $ s\mapsto sA $ 定義一個格子。決策性 LWE 問題（大致）是關於檢測這種晶格結構。例如

1. 在第一種情況下，s一個+和 $ sA+e $ 是統一的R $ R $ ，例如錯誤和 $ e $ “洗掉”任何晶格結構（理論上的資訊），
2. 在第二種情況下s一個 $ sA $ 恰好是格子中的一個點，並且存在測試某個候選點的成員資格的有效方法b=s一個 $ b = sA $ 在這種情況下，在晶格中，並且
3. 在第三種情況下，s一個 $ sA $ 是晶格的一個擾動點，很難確定你是否“接近”晶格。

所有這一切都是說您的問題有非常不同的答案，具體取決於錯誤分佈的精確特徵，因此錯誤分佈必須以某種方式考慮到您的答案中。為了提示它會如何，你說

如果G≠s $ g\neq s $ ， 然後和′=和 $ e′=e $ 可能持有也可能不持有。我不知道現在該怎麼辦。

什麼時候G≠s $ g\neq s $ ， 然後b+G一個=(G−s)一個+和 $ b + gA =(g-s)A+e $ . 粗略地說，你接下來要做的是爭辯說這不太可能(G−s)一個+和 $ (g-s)A+e $ 從誤差分佈中得出。這是因為

1. 誤差分佈集中在零附近（甚至可能是有界的），例如誤差分佈的任何元素都將具有|和| $ |e| $ “小”，和
2. 什麼時候G≠s $ g\neq s $ ,(G−s)一個 $ (g-s)A $ 將大於λ1(大號(一個)) $ \lambda_1(\mathcal{L}(A)) $ , 格子的最短向量大號(一個) $ \mathcal{L}(A) $ . 對於隨機一個 $ A $ ，這通常是“大”的。

您可以量化參數化事物似乎是合理的，這樣，使用上述兩個陳述的量化版本，不太可能G≠s $ g\neq s $ >

引用自：https://crypto.stackexchange.com/questions/98971