Рассмотрим следующую модификацию задачи о коротком целочисленном решении (SIS):
Позволять $n$ быть целым числом и $\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log\alpha)$ быть функциями $n$. Образец униформы $A\gets[-\alpha,\alpha]^{n\times m}$. Задача состоит в том, чтобы вычислить «короткий» вектор $e\in\mathbb{Z}^m$ в ядре $А$. Это:
- $|е| <\бета$.
- $A.e=0^n$. Здесь равенство выполняется над целыми числами
Обычная версия SIS такая же, как и выше, за исключением случаев, когда $A.e=0^n$ держит мод $q$, и $д=2\альфа+1$ (так что $А$ однороден в $\mathbb{Z}_q^{n\times m}$). Этот вариант удаляет модуль.
Вопрос: Есть ли какие-либо нетривиальные результаты по сложности/легкости для этой версии SIS? Какие настройки параметров просты, а какие (если есть) могут оказаться сложными на основе сложных задач решетки, как в обычной версии SIS?
Тривиальная атака: Существует тривиальный алгоритм в случае, когда $\бета$ огромный. Вы можете вычислить вектор ядра по целым числам, взяв миноры матрицы $А$. Эти миноры и, следовательно, вектор ядра можно легко оценить сверху с помощью $ (\ альфа п) ^ {О (п)} $. Итак, в режиме $\бета= (\альфа п)^{О(п)}$, есть тривиальная атака.
Меня больше всего интересует случай, когда $\альфа,\бета$ полиномиальны в $n$. Есть ли здесь какие-то нападки или можно проявить жесткость?
Я выбрал дистрибутив для $А$ выше, чтобы дать конкретную проблему. Но меня также интересуют другие дистрибутивы на $А$. Например, что, если записи $А$ дискретные гауссианы и т.д.?
Можно также рассмотреть неоднородный вариант этого варианта СИС, где $Ae=u$, для некоторого вектора $u$ (опять же без модуля). Мы должны быть осторожны, хотя что касается больших $u$ решения не будет. Может быть, мы ограничиваемся случайным $и\в\{0,1\}$, или в $[-\gamma,\gamma]^n$. Мне также было бы интересно, можно ли что-нибудь сказать и об этой проблеме, кроме прямой адаптации тривиальной атаки сверху.
