Я не могу найти явное выражение для этого преимущества.
Нет ни одного.
Это связано с тем, что это согласуется с современным состоянием теории сложности, которое $\mathsf{P} = \mathsf{NP}$, и поэтому $\mathsf{Adv}_{n,m,q,\sigma}^{\mathsf{DLWE}}$ есть некоторый полином от размеров соответствующих параметров.
это также в соответствии с текущим криптографическим представлением о том, что это не так, и что верны более агрессивные вещи, а именно, что $\mathsf{Adv}^{\mathsf{DLWE}}_{n,m,q,\sigma}$ почти полностью контролируется $n\лог д$, и в частности:
- $м$ может быть довольно большим, не влияя на безопасность, и
- $\сигма$ может быть весьма небольшим (теоретически $\sigma = \Omega(\sqrt{n})$ обычно требуется, хотя практически $\сигма = O(1) \приблизительно 8$ является общим).
Так как же конкретно оценить это преимущество? Как правило, путем (конкретной) оценки состояния известных атак.
Для этого есть два основных ресурса:
«Оценщик LWE» Albrect et al. невероятно популярен. Вы можете увидеть исходный документ здесь, и (более современный) модуль sage здесь.
Существующие конкретные предложения примитивов на основе решетки. Например, финалисты NIST PQC Kyber, Sabre и NTRUPrime включают (конкретный) анализ, обосновывающий их выбор параметров. Для более тяжелых примитивов Стандарт гомоморфного шифрования содержит таблицы предлагаемых параметров, а также сводки атак, на основании которых были построены эти таблицы.
Это все сказано...
Сокращает ли $q$ и увеличение $\сигма$ подразумевает меньшее преимущество (и, следовательно, лучшую безопасность?)
При прочих равных ответ - да.
Учитывая экземпляр LWE $(\mathbf{A}, \vec б)$, можно по модулю переключиться с $q\mapsto q'$ (за $д'<д$, анализ чище, если $q' \mid q$ хоть).
Это примерно отображает стандартное отклонение ошибки от $\sigma \mapsto \frac{q'}{q}\sigma < \sigma$.
Затем можно было бы увеличить эту ошибку до некоторого стандартного отклонения $\sigma' > \sigma > \frac{q'}{q}\sigma$ путем добавления соответствующего гауссиана.
Это означает, что существует относительно простое сокращение от $\mathsf{DLWE}_{n, m, q, \sigma}\leq \mathsf{DLWE}_{n, m, q', \sigma'}$ за $\сигма' > \сигма$ и $q' \mid q$ (случай $д'<д$ ненамного сложнее, но придется иметь дело с некоторой «ошибкой округления»), так что преимущество будет меньше.
