Ограничения на q для q-ичных решеток?

Как упоминает Хильдер, с помощью техники «переключения модуля» конкретный выбор $q$ не имеет большого значения для безопасности LWE. Поэтому особая форма $q$ в основном для повышения эффективности. Я не тот человек, чтобы исчерпывающе перечислить их все, но можно легко указать на несколько, прочитав предложения NIST PQC KEM.

Например:

1. Выбор $ д = 2 ^ к $ для некоторых $к$ позволяет заменить модульные редукции на $q$ с битовыми сдвигами, более дешевая операция. Это одна из причин, по которой Сэйбер выбирает $q = 2^{13}$.

2. Выбор $q$ быть «Дружелюбным к NTT». НТТ - это некий аналог БПФ" мод $q$"(а не более $\mathbb{C}$), которые могут значительно ускорить полиномиальное умножение (примерно от $ О (п ^ 2) $ наивная сложность $O(n\log n)$). Размер ускорения напрямую связан с наличием подходящего аналога $i\in\mathbb{C}$. В лучшем случае (скажем, при работе над $\mathbb{Z}_q[x]/(x^n+1)$ за $n = 2^k$) происходит, когда у вас есть «примитивный $2n$корень из единицы», что происходит, когда $q\экв 1\bmod 2n$ (Я думаю). Обратите внимание, что это несовместимо с предыдущей оптимизацией. KEM Kyber делает этот выбор (почти есть небольшие технические отличия).

3. Выбор $q$ быть произведением небольших (размером слова) взаимно простых чисел, поэтому можно обратиться к китайской теореме об остатках и сохранить все арифметические размеры слова. Я не знаю KEM, который делает это, но это популярно в литературе по FHE (и часто носит название «система нумерации остатков» или арифметика RNS).

Так что есть аргументы в пользу выбора $q \экв 0 \bmod 2^k$, $q\экв 1\bмод 2\раз 2^к$, и $q$ произведение малых взаимно простых чисел. Все это может показаться взаимоисключающими оптимизациями, но можно быть умнее и использовать сразу несколько оптимизаций. Например, есть эта работа по встраиванию арифметического мода $2^к$ (т. е. «дружественный к модульной редукции») в кольцо, дружественное к NTT, что позволяет использовать обе оптимизации 1 и 2.