Во-первых, должно быть ясно, что всегда можно увеличить шум в экземпляре LWE без ущерба для безопасности, поэтому (для фиксированного модуля) большее отношение модуля к шуму означает «не худшую» безопасность.
Конечно, это не объясняет, почему безопасность должна различаться в зависимости от $\сигма/q$, а не какое-то более сложное выражение.
Есть две причины понять, почему это «правильный» способ измерения размера шума.
Во-первых, это то, что проявляется при редукции от наихудшего случая к среднему.
Например, Первоначальное сокращение Регева показывает, что:
Теорема 1.1 (неформальная) Позволять $п, р$ быть целыми числами и $\альфа\в(0,1)$ быть таким, что $\альфа-р>2\sqrt{n}$. Если существует эффективный алгоритм, решающий $LWE(p, \Psi_\alpha)$ тогда существует эффективный квантовый алгоритм, который аппроксимирует вариант решения задачи о кратчайших векторах (GAPSVP) и задачи о кратчайших независимых векторах (SIVP) с точностью до $\тильда{О}(н/\альфа)$ в худшем случае.
Обратите внимание, что $1/\альфа$ - это отношение «модуль к шуму», поэтому коэффициент аппроксимации, который нужно принять, трудно напрямую масштабировать с $1/\альфа$.
На практике никто не хочет конкретно обращаться к уменьшению наихудшего случая к среднему при выборе параметров по двум причинам:
$\sigma := \alpha q > 2\sqrt{n}$ требуется, поэтому для $n> 500$ (что является удобной нижней границей) нужно $\сигма > 40$, намного больше, чем люди используют на практике.
Кроме того, в редукции имеется «зазор герметичности», см. раздел 6 Еще один взгляд на герметичность 2). Это влияет только на «константы» в редукции, но влияние довольно велико, и для обращения к редукции приходится выбирать весьма неэффективные параметры.
Итак, как мы можем сказать, что конкретно меньшее отношение модуля к шуму в LWE означает лучшую безопасность?
Здесь есть два момента:
Модуль LWE не сильно влияет на его безопасность, см., например, cor 3.2 of Классическая твердость LWE.
Вы можете явно параметризовать известные атаки с точки зрения отношения модуля к шуму, см. глава 4 диссертации Рэйчел Плейер, или же оценщик LWE.
Обратите внимание, что это история для LWE. Вы также использовали тег для Ring LWE. Там все несколько сложнее и может зависеть от «поведения расщепления» модуля $q$ в любом числовом поле, в котором вы работаете, хотя я не тот человек, который может написать ответ на эту тему.
