平均病例SIS和平均病例BDD

Question

在基于格的密码学中，我们称之为平均情况 SIS (短整数解)问题，因为它是这样的一类问题“A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}，查找向量s\in \mathbb{Z}^{m}_{q} \backslash \{0\}，使得As=0和||s||\leq \beta”。

但是，像这样的例子“A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}，找到了一个类似于AB=C和||B||\leq \beta的物理模型”。后一种情况比较普遍，而前一种情况只是包括后一种情况。

同样的情况也发生在BDD (有界距离译码)问题中。我们认为LWE问题是一个平均值问题，因为它只包含了一些BDD问题的例子。

我理解得对吗？

Answer 1

如果你想要的话，你可以用参数(n,m,q, \beta)定义一个“一般的SIS问题”如下:我给你一个矩阵A\in\mathbb{Z}_q^{n\times m}，你必须找到一个非零向量\vec x \in \mathbb{Z}_q^m，这样||\vec x|| \leq \beta和A\cdot \vec x = \vec 0。

矩阵A指定这个一般SIS问题的一个实例。通过定义如何选择实例A，可以得到问题的不同变体。SIS的平均情况硬度只是假设从某些实例的分布中随机选择实例时，很难找到上述问题的解决方案。这与最坏情况下的硬度形成了对比，而最坏的情况是假设这个问题在某些情况下很难解决，比如A。

现在，当我们讨论SIS问题时，默认情况下，这指的是我前面描述的问题的假设平均情况硬度，其中实例上的分布是\mathbb{Z}_q^{n\times m}上的均匀分布。如果你喜欢的话，你可以把它看作是一个更普遍的SIS问题家族的特例，在这种情况下，我们可以考虑不同情况下的平均硬度，或者最坏情况下的硬度。

然而，术语“平均值”与这样一个事实无关，即SIS可以被看作是一个更普遍的问题的特例，在这种情况下，人们试图找到一个小范数矩阵B，例如AB=C，而不是像A\vec x = 0这样的小范数向量\vec x。请注意，第一个问题也是众所周知的(它要求解决几个不均匀SIS问题的实例)，而且如果我们将k和C定义为系统的参数，则实际上更为普遍。但这与术语平均值无关--事实上，你可以同等地讨论一般情况下的硬度和最坏情况下的硬度，因为你也考虑了这个更普遍的问题。BDD和LWE也是如此。