如何生成新的 LWE 樣本
假設我們有少量固定數量的 LWE 樣本 $ s $ 和錯誤 $ e $ ，其中採用誤差分佈，因此 LWE 問題很困難。
我的問題：如何進一步生成 LWE 樣本（具有相同的秘密 $ s $ )，給定 LWE 樣本。
在$$ Reg10 $$（Sec2.“其他含義”）存在這樣的程序，但是我無法找到明確的解釋（或在他們建議的參考文獻中）。
**$$ Remark $$**我們可以自己進一步生成 LWE 樣本也就不足為奇了，因為 LWE 問題的難度不取決於樣本的數量（當誤差分佈為高斯分佈時）。
基本思想是對給定的 LWE 樣本進行隨機（高斯）整數組合，並添加一點“平滑”雜訊。這將導致新樣本在統計上接近具有相同秘密的 LWE 樣本，但誤差分佈更寬（因 $ \tilde{O}(\sqrt{n}) $ 對於典型參數）。這本質上是 Regev 在特殊的 Ajtai 晶格系列上的經典 BDD 到 LWE 約簡。
更準確地說，給定 LWE 樣本分組為 $ (\mathbf{A} \in \mathbb{Z}_q^{n \times m}, \mathbf{b}^t = \mathbf{s}^t \mathbf{A} + \mathbf{e}^t) $ 在哪裡 $ m \approx n \log q $ , 生成一個新樣本 $ (\mathbf{a}’ = \mathbf{A} \cdot \mathbf{r} \in \mathbb{Z}_q^n, b’ = \mathbf{b}^t \cdot \mathbf{r} + \tilde{e} \in \mathbb{Z}_q) $ ， 在哪裡 $ \mathbf{r} \in \mathbb{Z}^m $ 和 $ \tilde{e} \in \mathbb{Z} $ 具有適當參數的離散高斯分佈。可以證明，選擇原件的機率很高 $ (\mathbf{A}, \mathbf{b}) $ , 的分佈 $ \mathbf{a}’ $ 幾乎是均勻的。此外，以任何固定的選擇為條件 $ \mathbf{a}’ $ , 的分佈 $ \mathbf{e}^t \cdot \mathbf{r} + \tilde{e} $ （這是輸出樣本中的“誤差”項）接近離散高斯。
這個過程在 Gentry-Peikert-Vaikuntanathan，“硬格的活板門……”（用於 IBE 的嚴格安全證明）中進行了概述，並且在 Applebaum-Cash-Peikert-Sahai，“Fast Cryptographic Primitives”中更正式地完成。 ..”（作為 KDM 安全公鑰方案的加密算法）。