LWE和扩展的陷门无爪函数

Question

设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对于多项式时间经典算法来说是困难的，在给定A和给出(多项式多个)“样本”(由于e是概率分布，<D15或D17都是样本)的情况下，f和g也很难区分。

LWE的减少也适用于一般情况。

本文还指出，这两个函数是一个“扩展的陷阱门无爪函数”(定义5，6，7)。

作为对上述事实的证明，本文参考了这论文(引理9.3)。然而，在证明引理9.3的同时，第二篇论文也引用了其他一些文献，如这文献。我在任何一份报纸上都不清楚证据。

我想问如何将区分f和g的任务减少到LWE。我还想问一问，在这个减缩过程中，“扩展的无陷阱门爪”功能的重要性。

根据我的理解，LWE的硬度表示，如果给我们A，区分均匀随机样本和样本与As + e'是困难的。我不知道b和x或其他参数是如何影响这一事实的。那就是我们需要无爪越野车的地方吗？

Answer 1

我认为削减的目的如下：

让D成为f, g的区别。为LWE构建一个区分器D'，即：

1. 接受LWE实例(A, b')作为输入
2. 创建甲骨文h_{A, b'}(b,x) = Ax + bb' + e\bmod q
3. 使用oracle访问D模拟h，并返回D所做的事情。

相对来说，这位对手应该发挥作用相对简单，因为：

1. 当b'是一致随机的，h_{A,b'}(b,x) = f(b,x)
2. 当b' = As + e'，h_{A,b'}(b,x) = g(b,x)

您获得的优势绑定最终应该独立于您在缩减中使用的特定LWE实例(A, b')。我想这就是“A, u, e'上最坏的情况”的来源，但我以前还没有真正听说过，所以不能肯定这就是作者的意图。

值得一提的是，我看到没有任何地方需要f, g是扩展的、不带爪的函数(或任何类似的函数)。相反，我认为正在发生的一切是，f, g每个来自高效的后处理一个LWE样本(在世界上一个样本来自LWE分布，其中一个是一致随机的)。如果这可能导致可区分的功能，它将明确地对LWE进行攻击。