LWE 和擴展的活板門無爪功能
讓 $ q \geq 2 $ 是一個素數。考慮兩個函式，由下式給出：
$$ f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q), $$ $$ g(b, x) = Ax + b \cdot (As + e’) + e~~~(\text{mod}~q), $$
我們有： $$ \begin{align} b &\in {0, 1}, \ x &\in \mathbb{Z}{q}^{n}, \ s &\in \mathbb{Z}{q}^{m}, \ A &\in \mathbb{Z}{q}^{n \times m}, \ e’ &\in \mathbb{Z}{q}^{m}, \ u &\in \mathbb{Z}_{q}^{m}, \end{align} $$
$ e $ 從分佈中採樣：
$$ \begin{equation} D_{\mathbb{Z}q, B^{’}}(x) = \frac{e^{\frac{- \pi ||x||^{2}}{B^{‘2}}}}{\sum{x \in \mathbb{Z}q^{n}, ||x|| \leq B’} e^{\frac{- \pi ||x||^{2}}{B^{‘2}}}}, \end{equation} $$ 在哪裡 $$ B’ = \frac{q}{C{T} \sqrt{mn \log q}}, $$ $ C_{T} $ 是一個固定常數。
在本文中，函式在等式 29 中定義，並提到在最壞的情況下 $ A $ , $ u $ 和 $ e’ $ ，假設 LWE 對於多項式時間經典算法很難，區分 $ f $ 和 $ g $ 也很難，給定 $ A $ 並給定（多項式）“樣本”（因為 $ e $ 是一個機率分佈，輸出 $ f $ 或者 $ g $ 是樣本）來自任一 $ f $ 或者 $ g $ .
LWE 減少也適用於平均情況。
該論文還提到，這兩個函式是“擴展活板門無爪函式（定義 5、6、7）”系列。
作為對上述事實的證明的參考，本文引用了這篇論文（引理 9.3）。然而，在證明引理 9.3 的同時，第二篇論文還引用了其他一些論文，比如這篇論文。任何論文中的證據對我來說都不清楚。
我想問如何減少區分的任務 $ f $ 和 $ g $ 到 LWE。我還想問一下“無擴展活板門爪”功能在減少中的重要性。
據我了解，LWE 的硬度表示，如果我們被給予 $ A $ , 區分均勻隨機樣本和來自 $ As + e’ $ 很難。我不確定如何 $ b $ 和 $ x $ 或其他參數因素影響這一事實。那是我們需要擴展活板門無爪證明的地方嗎？
我認為以下減少是有意的：
讓 $ D $ 成為區分者 $ f, g $ . 建立區分器 $ D’ $ 對於 LWE：
- 將 LWE 實例作為輸入 $ (A, b’) $
- 創建神諭 $ h_{A, b’}(b,x) = Ax + bb’ + e\bmod q $
- 模擬 $ D $ 通過 oracle 訪問 $ h $ , 並返回什麼 $ D $ 做。
這個對手應該起作用似乎相對簡單，因為：
- 什麼時候 $ b’ $ 是均勻隨機的， $ h_{A,b’}(b,x) = f(b,x) $
- 什麼時候 $ b’ = As + e’ $ , $ h_{A,b’}(b,x) = g(b,x) $
您獲得的優勢最終應該獨立於特定的 LWE 實例 $ (A, b’) $ 你在減少使用。我想這是“最壞的情況 $ A, u, e’ $ “來自，但我之前沒有真正聽說過，所以不能肯定這是作者的意圖。
值得一提的是，我看不到你需要的地方 $ f, g $ 是擴展的陷門無爪功能（或任何此類）。相反，我認為正在發生的一切就是 $ f, g $ 每個都來自對 LWE 樣本的有效後處理（世界上的一個樣本來自 LWE 分佈，其中一個樣本是均勻隨機的）。如果這可以導致可區分的功能，它顯然會對 LWE 進行攻擊。