Регистрация Войти
Рейтинг:1
avatar Crypto

Зачем использовать негациклические свертки для полиномиального умножения вместо обычных сверток?

флаг pm
warforgad

При умножении полиномов из $\mathbb{Z}_q[X] / (X^n-1) $, дискретный NTT используется, потому что: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \right ) $$ Однако практически во всех схемах, которые я видел, негациклический используется свертка - кольцо $\mathbb{Z}_q[X] / (X^n+1) $ и трюк используется для вычисления $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right ) \справа) $ с использованием $\mathsf{NTT}_n$ потому что мы должны умножить многочлены в $\mathbb{Z}_q[X] / (X^{2n}-1) $.
У меня вопрос - зачем заморачиваться $\mathbb{Z}_q[X] / (X^n+1) $ а не просто использовать $\mathbb{Z}_q[X] / (X^n-1) $, тем самым применяя $\mathsf{NTT}_n$ по прямому пути без лишних сложностей?

41
0 + 0
Рейтинг:1
kodlu avatar Crypto
флаг sa
kodlu

Вы утверждаете (я исправил ваши обозначения, классы вычетов берутся с $/$ нет $\обратная косая черта)$ первый setminus не то же самое:

Однако практически во всех схемах, которые я видел, негациклический используется свертка - кольцо $\mathbb{Z}_q[X] / (X^n+1) $ и трюк используется для вычисления $\mathsf{NTT}_{2n}^{-1}\left( \mathsf{NTT}_{2n}\left(f\right) * \mathsf{NTT}_{2n}\left(g\right ) \справа) $ с использованием $\mathsf{NTT}_n$ потому что мы должны умножить многочлены в $\mathbb{Z}_q[X] / (X^{2n}-1) $.

и задать вопрос:

зачем возиться с $\mathbb{Z}_q[X] / (X^n+1) $ а не просто использовать $\mathbb{Z}_q[X] \setminus (X^n-1) $?

Если у нас есть полиномиальная факторизация $х^{2n}-1=(х^n-1)(х^n+1)$ затем вычисления по модулю $х^{2n}-1$ можно ускорить, свернув (через NTT) по каждому из факторов, а затем объединив. Так

  1. У нас есть факторизация, которая ведет к быстрому преобразованию, поэтому мы идем по этому пути. Крайним случаем является сложное БПФ, когда мы можем полностью разложить на линейные множители. $x^n-1=\prod_{i=1}^n (\omega^i-1)$ с $\омега$ примитивный $n^{th}$ корень единства.
  2. Факторизация уникальна, вы не можете использовать $(х^n+1)$ только с тех пор $(х^n+1)^2=(х^{2n}+2 х^n+1)$ и $q$ вообще не характерно 2. Если вы имели в виду на самом деле просто используйте $х^{2n}-1$ напрямую, у вас не будет ускорения.
0 + 0
флаг pm
warforgad
Извините, у меня плохо с частным обозначением. Я думаю, что вы неправильно поняли мой вопрос (или я неправильно понял ваш ответ). Я не спрашиваю, как умножать многочлены степени $(2n-1)$, используя НТП порядка $n$, и не спрашиваю, почему нельзя умножать многочлены из $\mathbb{Z}_q[X]/(X ^n+1)$ с НТЦ. Я спрашиваю, зачем в первую очередь использовать полиномы по модулю $X^n+1$ (для чего нужен трюк с $(X^{2n}-1)$), а не использовать полиномы по модулю $X^n-1$
1
Ответить
kodlu avatar
флаг sa
kodlu
если ваша длина $N=2n,$, т.е. четная, это ЯВЛЯЕТСЯ факторизацией, которую вы должны использовать для начала, т.е. $x^{2n}-1=(x^n-1)(x^n+1)$ потому что любой $2n^{th}$ корень из единицы в любом поле или кольце либо имеет порядок $2n$ (те, которые равны -1 при возведении в степень $n$), либо имеют порядок, делящий $n$.
0
Ответить
kodlu avatar
флаг sa
kodlu
вы начинаете с $N$ как данности.
0
Ответить
Рейтинг:1
Hilder Vitor Lima Pereira avatar Crypto
флаг us
Hilder Vitor Lima Pereira

Основная трудная проблема, используемая для построения криптографических примитивов, требует, чтобы мы использовали это кольцо полиномов по модулю $X^n + 1$.

Например, если безопасность вашей схемы зависит от RLWE, вам придется придерживаться тех колец, которые обеспечивают безопасность RLWE, а это означает, что вы не можете использовать $X^n - 1$, как обсуждалось в этот ответ.

У вас такая же ситуация с Проблема Ring-SIS.

В общем, вы должны быть осторожны, когда создаете экземпляр любой проблемы с $X^n - 1$ как модуль, потому что можно вычислить полиномы на $1$ работать с целыми числами вместо многочленов. Это обсуждается, например, в разделе «Полиномиальное вычисление» Эта бумага.

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.