Рассмотрим формулировку LWE, где нам дано либо $(х,S х+е)$ или же $(х,у)$ --- куда $S$ является $м \раз п$ секретная/скрытая матрица, $х$ представляет собой случайную выборку $n \раз 1$ вектор, $е$ является $м\раз 1$ вектор ошибки Гаусса и $u$ является равномерно случайной выборкой --- и велел различать эти два случая. Согласно сообщению, это должно быть сложно для классических алгоритмов. здесь. Назовите эту проблему «обратным LWE».
У меня возникло несколько вопросов по настройке.
Трудна ли задача различения без $е$?
Обратите внимание, что в стандартном LWE, когда нам дается $(А,Ас+е)$ или же $(х,у)$, и сказал различать два случая, проблема легко без ошибки. Мы просто решаем систему линейных уравнений, чтобы получить $n$ записи $s$.
Однако здесь нужно найти $м \раз п$ записи нашей секретной матрицы $S$. Я не вижу, как это сделать, просто $м$ уравнения.
Рассмотрим вариант задачи, где нам дано либо $$ \{ (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_k, Sx_k + e_k)\} ~~\text{or}$$
$$\{ (x_1, u_1), (x_2, u_2), \ldots, (x_k, u_k)\},$$
и сказал различать два случая. Назовите эту проблему «обратным LWE с повторяющимся секретом». $к$ полиномиально велико в $n$. Трудна ли эта проблема?
Обратите внимание, что гибридный аргумент (например, используемый в одном из ответов здесь) указывает на то, что проблема остается серьезной. вот это гибрид $H_i$:
$$H_i = \{ (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_i, Sx_i + e_i), (x_{i+1}, u_{i+1}) \ldots , (x_{k}, u_{k}) \} .$$
Тогда есть прямой способ заключить, что если мы решим «обратный LWE с повторяющимся секретом», мы сможем решить обратный LWE. Поскольку обратный LWE труден, наша задача также должна быть сложной.
Тем не менее, я с трудом осознаю этот факт.
Обратите внимание, что если у нас нет члена ошибки, то есть очень простой способ различить эти два случая, для $k \geq n+1$. Обратите внимание, что может быть только $n$ линейно независимый $x_i$-с. Итак, различитель просто ищет $n$ отчетливый $x_i$-s в данных образцах, отмечает, где матрица $S$ переводит эти векторы в и для $n+1^{\text{th}}$ отдельный образец, использует линейность, чтобы сначала вычислить, где $S$ принимает его, а затем проверяет, соответствует ли это тому, что было дано.
Почему термины ошибки приводят к сбою этого различителя? Даже при гауссовой ошибке из-за линейной зависимости не должно ли $n+1^{\text{th}}$ быть достаточно сконцентрированной вокруг некоторого значения, чтобы мой различитель смог добиться успеха?
