LWE:从连续高斯到真正的离散高斯

Question

简略版:如何才能将连续高斯圈成真正的离散高斯(通常表示为\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。它们还证明了，如果你能求解连续的线性微分方程，你就可以求解\textsf{GapSVP}_\gamma。为了证明用这个奇怪的离散高斯的LWE的安全性，他们解释了从连续LWE到这个“奇怪离散”LWE的一个微不足道的约简:如果你能解决“奇异离散”LWE，你可以通过把你的样本四舍五入到最近的整数来解决连续LWE问题，并调用这些样本上的离散oracle。硬度是这样的：

\text{strange discrete LWE} \leftarrow \text{continuous LWE} \leftarrow \textsf{GapSVP}_\gamma

然而，如果我正确理解，这种高斯不是“真实高斯”，人们更喜欢使用像[MP12]这样的“真正离散高斯”(我猜，当您想要更多涉及的属性时，它具有更好的数学特性，比如奇异值的界)。但是，我们不可能以同样的方式使用Reg05结果来证明“真离散”线性微分方程的硬度，因为我们不能再把一个连续分布转化为一个真正离散的分布。

那么，通常如何进行舍入才能得到以下的缩减呢？

\text{true discrete LWE} \leftarrow \text{continuous LWE}

本文[GMPW20]认为[Pei10]解决了这一问题。但我找不到哪里。

此外，是否有直接减少：

\text{true discrete LWE} \leftarrow \text{GapSVP}_\gamma

而不经过离散的情况？

参考资料

[MP12]格子陷阱:更简单，更紧，更快，更小，米其西奥，佩克特。

[GPV08]如何使用一个简短的基础:硬格和新密码构造的陷阱门，Gentry，Peikert，Vaikuntanathan。

[Pei10]是一种高效的并行高斯采样器。

整数上的[MW17]高斯采样:有效，泛型，常数时间，Micciancio，Walter.

[HSL17]圆形高斯人，Hülsing，Lange，Smeets。

[GMPW20]改进了格点密码学，Genise，Micciancio，Peikert，Walter的离散高斯和亚高斯分析。

奖励:额外的无关信息:出于好奇，在\mathcal{D}_{\mathbb{Z},\alpha q}上采样的最新进展如何？有什么精确的取样方法吗？什么样的抽样方法是推荐的，它既简单，又不太低效。现在，我看到[GPV08]的4.1节给出了一个简单的拒绝抽样方法来近似一个真正离散高斯的样本。后来在[Pei10]中对它进行了改进，这有点复杂。我刚看到[MW17]，我需要检查一下它到底做了什么。

-编辑--

我也很困惑为什么人们那么喜欢“真正的离散高斯”：人们可能会说“两个离散高斯的和是离散高斯的总和”。当然可以。但是对于“奇怪高斯人”来说，与初始连续高斯相比，舍入一个连续高斯使得问题变得更加复杂:所以在证明中，你总是可以说“让我们用一个连续高斯替换奇怪高斯”，现在我们分析了对这个新协议的攻击:现在，我们有了这样一个很好的性质，两个连续高斯的和是连续高斯的。奇怪的离散高斯人似乎也比真正的离散高斯人更有效的[HSL17]，那么有什么好处呢？你会有一个应用的例子吗?在这个例子中，真正需要的是这个离散的高辛？

例如，[MP12]使用这些真正的高斯，但是对[MP12]的决策约简的搜索是针对连续高斯的。我能看到的唯一定理(我没有检查最后一节“应用程序”)实际上需要真正的高斯，那就是引理2.9，它定义了\mathbf{R}的奇异值(正确性所必需的)。然而，对于任何\delta-subgaussian分布，这个定理都是正确的，所以我认为对于一些合理的\delta，奇异高斯也是\delta-subgaussian，而且对于真正的离散高斯，它们只在经验上得到了C的值，所以我想，对于奇异高斯，也有可能这样做。

Answer 1

要回答第一个简短的问题:这是佩克特‘10定理3.1的一个(非常)特例。具体来说，使用“x_2是从连续高斯选择的”变量，设\Lambda_1+c_1是整数格\mathbb{Z}，\Sigma, \Sigma_1, \Sigma_2是合适的正数。

关于为什么真正的离散高斯是有用的:这通常是因为它们允许我们证明我们想要的东西，无论是为了功能(例如，很好的奇异值)还是为了安全性。对于后者来说，仅仅说已知的攻击(似乎)变得“更加复杂”与圆形高斯人是不够的；我们必须证明舍入是不可能被任何方式利用的。例如，许多证明需要正确地模拟实际系统中使用的特定分布。使用真正的离散高斯通常使这成为可能，但它还不清楚如何用圆形的。

Answer 2

出于好奇，D_{\mathbb{Z},\alpha q}抽样的最新进展如何？

这是一个相当复杂的问题。有许多相互竞争的方法可以对其进行抽样，您可以大致分为：

1. 适用于任何概率分布的技术
2. 特定于离散高斯的技术

MW17的表1讨论了一些抽样方法。Michael的论文“*具有低相对误差的整数采样”也调查了一些方法，所以也许是一个很好的资源。不过还有更多。特别是，我还知道：

1. 极地取样器
2. 条件密度取样器

此外，还有许多不同的事情可以做，以优化的事情，如拒绝抽样。我记得本文是关于NIST PQC候选人的研究.猎鹰，但我相信最近有一些尝试使拒绝抽样“恒定时间”的1，我不记得是即时的。

根据特定的应用程序，还可以做一些非常简单的事情。我见过有人提到，对于加密，\mathcal{D}_{\sigma,\mathbb{Z}}是错误的发行版，我们可以从\mathsf{Binom}(n, p)这样的发行版中为合适的p进行示例。这有点像离散高斯(光尾，居中等)，但更容易取样。此优化只适用于加密，而不适用于2签名。

有什么精确的取样方法吗？

有很多。卡尼的方法很可能最接近“精确抽样法”的含义，尽管像Knuth-姚抽样这样的东西也适用于这种描述。在最坏的情况下，不可能从无限支持的分布中精确采样，所以精确的采样方法在实际中并不特别有用。Karney方法的特点意味着，尽管如此，即使在该模型中，它也是一种“几乎”精确的抽样方法。卡尼氏论文很好地解释了这一点，例如，这里是抽象的：

给出了一种正态分布精确采样的算法。该算法读取给定基中若干均匀分布的随机数字，并在同一基中生成法向偏差表示的初始部分。然后，将均匀随机数字直接复制到法向偏差的表示中。因此，与现有方法相比，有可能产生法向偏差，使其精确地四舍五入到任何精度，平均成本在精度范围内成线性。该方法不执行扩展精度算法，不调用任何先验函数，实际上也不使用浮点算法；它只使用简单的整数操作。它可以很容易地从参数为有理数的离散正态分布中得到精确的样本。

我认为初始部分的成本不是恒定的(因此算法不是“恒定时间算法+在输出端粘贴均匀随机位)，但这仍然是一个与其他”精确“取样器不同的结果，值得指出。

1常数时间是用词不当，人们真正想要的是，时间分布与任何秘密无关。我相信链接的猎鹰纸(或另一份不同的猎鹰纸)试图通过一种叫做等时算法的概念或其他类似的概念来将其正式化，但这种(正式的)概念似乎并不普遍。

2参见这以获得更多详细信息。