LWE：將連續高斯四捨五入為真正的離散高斯
簡短版本：如何將連續高斯四捨五入為真正的離散高斯（通常表示為 $ \mathcal{D}{\mathbb{Z},\alpha q} $ )? 目標是獲得從連續 LWE 到真正離散 LWE 的約簡，並將其與從 $ \textsf{GapSVP}\gamma $ 到連續 LWE。
更長的版本：在
$$ Reg05 $$，他們考慮的離散高斯（表示 $ \bar{\Psi}\alpha $ ，或者有時 $ \lfloor\mathcal{D}{\alpha q}\rceil $ ) 因為雜訊是“奇怪的高斯”：它可以從參數的連續高斯獲得 $ \alpha q $ 你只是四捨五入到最接近的整數模 $ q $ . 他們還證明，如果你能解決連續 LWE，你就能解決 $ \textsf{GapSVP}\gamma $ . 為了也用這個奇怪的離散高斯證明 LWE 的安全性，他們解釋了從連續 LWE 到這個“奇怪的離散”LWE 的簡單簡化：如果你能解決“奇怪的離散”LWE，你可以通過以下方式解決連續 LWE 問題只需將您的樣本四捨五入到最接近的整數，然後在這些樣本上呼叫離散預言。所以硬度是這樣的： $$ \text{strange discrete LWE} \leftarrow \text{continuous LWE} \leftarrow \textsf{GapSVP}\gamma $$
但是，如果我理解正確，這個高斯不是“真正的高斯”，人們更喜歡使用“真正的離散高斯”，比如$$ MP12 $$（我想當您想要更多涉及的屬性時，它具有更好的數學屬性，例如奇異值的界限）。但是，不可能以相同的方式使用
$$ Reg05 $$結果證明了“真離散”LWE 的硬度，因為我們不能再將連續分佈變成真離散分佈。 那麼進行這種舍入以獲得以下減少的通常方法是什麼？ $$ \text{true discrete LWE} \leftarrow \text{continuous LWE} $$ 這張紙$$ GMPW20 $$表明$$ Pei10 $$解決了這個問題……但我找不到在哪裡。
此外，是否有直接的減少：
$$ \text{true discrete LWE} \leftarrow \text{GapSVP}_\gamma $$
沒有通過離散案例中轉？
參考
$$ MP12 $$ 格子活板門：更簡單、更緊密、更快、更小、Miccincio、Peikert。
$$ GPV08 $$ 如何使用短基：硬格的活板門和新的密碼構造，Gentry，Peikert，Vaikuntanathan。
$$ Pei10 $$ 格的高效並行高斯採樣器，Peikert。
$$ MW17 $$ 整數上的高斯採樣：高效、通用、恆定時間、Miccincio、Walter。
$$ HSL17 $$ 圓角高斯、Hülsing、Lange、Smeets。
$$ GMPW20 $$ 改進了格密碼學、Genise、Miccincio、Peikert、Walter 的離散高斯和亞高斯分析。
獎勵：其他不相關的資訊：出於好奇，目前採樣的最新技術是什麼 $ \mathcal{D}_{\mathbb{Z},\alpha q} $ ? 有沒有確切的抽樣方法？對這種採樣進行程式的推薦方法是什麼，既程式簡單又在實踐中效率不低？現在我看到了第 4.1 節$$ GPV08 $$給出了一種簡單的拒絕抽樣方法來逼近真實離散高斯的樣本. 後來在改進$$ Pei10 $$, 這有點複雜。我剛看到$$ MW17 $$，我需要檢查它的實際作用。
- 編輯 -
我也很困惑為什麼人們那麼喜歡“真正的離散高斯”：人們可能會說“兩個離散高斯的總和是離散高斯”。很公平。但是對於“奇怪的高斯”，您總是可以說，與最初的連續高斯相比，對連續高斯進行四捨五入會使問題更加複雜：所以在證明中，您總是可以說“讓我們用連續高斯替換奇怪的高斯”，現在我們分析了對這個新協議的攻擊：現在，我們確實有一個很好的屬性，即兩個連續高斯的和是一個連續的高斯。奇怪的離散高斯也似乎更有效$$ HSL17 $$比真正的離散高斯採樣，那麼有什麼好處？您是否有一個真正需要這種真正離散高斯分佈的應用範例？
例如，$$ MP12 $$使用這些真正的高斯，但搜尋到決策減少$$ MP12 $$是為連續高斯公式製定的。我能看到的唯一可能需要真正高斯的定理（我沒有檢查最後一節“應用程序”）是引理 2.9，它限制了 $ \mathbf{R} $ （正確性所必需的）。然而，該定理對於任何 $ \delta $ -次高斯分佈，所以我希望奇怪的高斯分佈也是 $ \delta $ -subgaussian 一些合理的 $ \delta $ ，並且因為對於真正的離散高斯，他們獲得了一個值 $ C $ 僅憑經驗，我想對於奇怪的高斯人也有可能這樣做。
回答您的第一個簡短問題：這是Peikert'10定理 3.1 的（非常）特例。具體來說，使用“ $ x_2 $ 從連續高斯變體中選擇，讓 $ \Lambda_1+c_1 $ 是整數格 $ \mathbb{Z} $ ， 然後讓 $ \Sigma, \Sigma_1, \Sigma_2 $ 是合適的正數。
關於為什麼真正的離散高斯是有用的：通常是因為它們允許我們證明我們想要的東西，無論是對於功能（例如，好的奇異值）還是安全性。對於後者，僅僅說已知的攻擊（似乎）使用圓角高斯函式變得“更複雜”是不夠的；我們必須證明不能以任何方式利用四捨五入。例如，許多證明需要正確模擬實際系統中使用的特定分佈。使用真正的離散高斯函式通常可以實現這一點，而如何使用舍入的高斯函式則不清楚。