Задача о коротком целочисленном решении

короткого целочисленного решения (SIS) и кольцевой SIS Проблемы — это две задачи среднего случая, которые используются в конструкциях криптографии на основе решетки . Криптография на основе решеток началась в 1996 году с плодотворной работы Миклоша Айтая. который представил семейство односторонних функций, основанных на проблеме SIS. Он показал, что в среднем случае это безопасно, если задача о кратчайшем векторе $\mathrm {SVP} _{\gamma }$ (где $\gamma =n^{c}$ для некоторой константы $c>0$) сложно в худшем случае.

Проблемы среднего случая — это проблемы, которые трудно решить для некоторых случайно выбранных случаев. Для криптографических приложений сложности наихудшего случая недостаточно, и нам необходимо гарантировать, что криптографическая конструкция сложна на основе средней сложности случая.

Решетки

Решетка полного ранга ${\mathfrak {L}}\subset \mathbb {R} ^{n}$ представляет собой набор целочисленных линейных комбинаций $n$ линейно независимые векторы $\{b_{1},\ldots ,b_{n}\}$, именованный базис :

${\mathfrak {L}}(b_{1},\ldots ,b_{n})=\left\{\sum _{i=1}^{n}z_{i}b_{i}:z_{i}\in \mathbb {Z} \right\}=\{B{\boldsymbol {z}}:{\boldsymbol {z}}\in \mathbb {Z} ^{n}\}$

где $B\in \mathbb {R} ^{n\times n}$ представляет собой матрицу, имеющую базисные векторы в своих столбцах.

Примечание: Учитывая $B_{1},B_{2}$ две основы для решетки ${\mathfrak {L}}$, существуют унимодулярные матрицы $U_{1}$ такой, что $B_{1}=B_{2}U_{1}^{-1},B_{2}=B_{1}U_{1}$.

Идеальная решетка

Определение: включен оператор ротационного сдвига. $\mathbb {R} ^{n}(n\geq 2)$ обозначается $\operatorname {rot}$и определяется как:

$\forall {\boldsymbol {x}}=(x_{1},\ldots ,x_{n-1},x_{n})\in \mathbb {R} ^{n}:\operatorname {rot} (x_{1},\ldots ,x_{n-1},x_{n})=(x_{n},x_{1},\ldots ,x_{n-1})$

Циклические решетки

Миччанчо ввел циклические решетки в своей работе по обобщению задачи о компактном рюкзаке на произвольные кольца. Циклическая решетка — это решетка, замкнутая относительно оператора вращательного сдвига. Формально циклические решетки определяются следующим образом:

Определение: решетка. ${\mathfrak {L}}\subseteq \mathbb {Z} ^{n}$ является циклическим, если $\forall {\boldsymbol {x}}\in {\mathfrak {L}}:\operatorname {rot} ({\boldsymbol {x}})\in {\mathfrak {L}}$.

Примеры:

1. $\mathbb {Z} ^{n}$ сама по себе является циклической решеткой.
2. Решетки, соответствующие любому идеалу в факторкольце многочленов $R=\mathbb {Z} [x]/(x^{n}-1)$ цикличны:

рассмотрим факторкольцо полиномов $R=\mathbb {Z} [x]/(x^{n}-1)$, и пусть $p(x)$ быть некоторым многочленом от $R$, то есть $p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}$ где $a_{i}\in \mathbb {Z}$ для $i=0,\ldots ,n-1$.

Определите коэффициент внедрения $\mathbb {Z}$-модульный изоморфизм $\rho$ как:

${\begin{aligned}\quad \rho :R&\rightarrow \mathbb {Z} ^{n}\\[4pt]\rho (x)=\sum _{i=0}^{n-1}a_{i}x^{i}&\mapsto (a_{0},\ldots ,a_{n-1})\end{aligned}}$

Позволять $I\subset R$ быть идеалом. Решетка, соответствующая идеалу $I\subset R$, обозначенный ${\mathfrak {L}}_{I}$, представляет собой подрешетку $\mathbb {Z} ^{n}$и определяется как

${\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}\subset \mathbb {Z} ^{n}.$

Теорема: ${\mathfrak {L}}\subset \mathbb {Z} ^{n}$ является циклическим тогда и только тогда, когда ${\mathfrak {L}}$ соответствует некоторому идеалу $I$ в кольце факторполиномов $R=\mathbb {Z} [x]/(x^{n}-1)$.

доказательство: $\Leftarrow )$ У нас есть:

${\mathfrak {L}}={\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}$

Позволять $(a_{0},\ldots ,a_{n-1})$ быть произвольным элементом в ${\mathfrak {L}}$. Затем определите $p(x)=\sum _{i=0}^{n-1}a_{i}x^{i}\in I$. Но поскольку $I$ это идеал, мы имеем $xp(x)\in I$. Затем, $\rho (xp(x))\in {\mathfrak {L}}_{I}$. Но, $\rho (xp(x))=\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}_{I}$. Следовательно, ${\mathfrak {L}}$ является циклическим.

$\Rightarrow )$

Позволять ${\mathfrak {L}}\subset \mathbb {Z} ^{n}$ быть циклической решеткой. Следовательно $\forall (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}:\operatorname {rot} (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}$.

Определите набор полиномов $I:=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}\mid (a_{0},\ldots ,a_{n-1})\in {\mathfrak {L}}\right\}$:

1. С ${\mathfrak {L}}$ решетка и, следовательно, аддитивная подгруппа в $\mathbb {Z} ^{n}$, $I\subset R$ является аддитивной подгруппой $R$.
2. С ${\mathfrak {L}}$ является циклическим, $\forall p(x)\in I:xp(x)\in I$.

Следовательно, $I\subset R$ является идеалом и, следовательно, ${\mathfrak {L}}={\mathfrak {L}}_{I}$.

Идеальные решетки

Позволять $f(x)\in \mathbb {Z} [x]$ быть моническим многочленом степени $n$. Для криптографических приложений $f(x)$ обычно выбирается неприводимым. Идеал, порожденный $f(x)$ является:

$(f(x)):=f(x)\cdot \mathbb {Z} [x]=\{f(x)g(x):\forall g(x)\in \mathbb {Z} [x]\}.$

Факторполиномиальное кольцо $R=\mathbb {Z} [x]/(f(x))$ перегородки $\mathbb {Z} [x]$ на классы эквивалентности многочленов степени не выше $n-1$:

$R=\mathbb {Z} [x]/(f(x))=\left\{\sum _{i=0}^{n-1}a_{i}x^{i}:a_{i}\in \mathbb {Z} \right\}$

где сложение и умножение сокращаются по модулю $f(x)$.

Рассмотрим коэффициент вложения $\mathbb {Z}$-модульный изоморфизм $\rho$. Тогда каждый идеал в $R$ определяет подрешетку $\mathbb {Z} ^{n}$ называется идеальной решеткой .

Определение: ${\mathfrak {L}}_{I}$, решетка, соответствующая идеалу $I$, называется идеальной решеткой. Точнее, рассмотрим факторкольцо многочленов $R=\mathbb {Z} [x]/(p(x))$, где $(p(x))$ идеал, порожденный степенью $n$ полиномиальный $p(x)\in \mathbb {Z} [x]$. ${\mathfrak {L}}_{I}$, представляет собой подрешетку $\mathbb {Z} ^{n}$и определяется как:

${\mathfrak {L}}_{I}:=\rho (I)=\left\{(a_{0},\ldots ,a_{n-1})\mid \sum _{i=0}^{n-1}a_{i}x^{i}\in I\right\}\subset \mathbb {Z} ^{n}.$

Примечание:

1. Оказывается, ${\text{GapSVP}}_{\gamma }$ даже для маленьких $\gamma =\operatorname {poly(n)}$ на идеальных решетках обычно легко. Интуиция подсказывает, что алгебраические симметрии приводят к тому, что минимальное расстояние до идеала находится в узком, легко вычислимом диапазоне.
2. Используя предоставленные алгебраические симметрии в идеальных решетках, можно преобразовать короткий ненулевой вектор в $n$ линейно независимые (почти) одинаковой длины. Поэтому на идеальных решетках $\mathrm {SVP} _{\gamma }$ и $\mathrm {SIVP} _{\gamma }$ эквивалентны с небольшими потерями. Более того, даже для квантовых алгоритмов $\mathrm {SVP} _{\gamma }$ и $\mathrm {SIVP} _{\gamma }$ Считается, что в худшем случае это будет очень сложно.

Задача с коротким целым числом

Задача короткого целочисленного решения (SIS) — это задача среднего случая, которая используется в конструкциях криптографии на основе решетки. Криптография на основе решеток началась в 1996 году с плодотворной работы Айтая. который представил семейство односторонних функций, основанных на задаче SIS. Он показал, что в среднем случае это безопасно, если $\mathrm {SVP} _{\gamma }$ (где $\gamma =n^{c}$ для некоторой константы $c>0$) сложно в худшем случае. Наряду с приложениями в классической криптографии, проблема SIS и ее варианты используются в нескольких схемах постквантовой безопасности, включая CRYSTALS-Dilithium и Falcon .

СИС _{q , n , m , β}

Позволять $A\in \mathbb {Z} _{q}^{n\times m}$ быть $n\times m$ матрица с записями в $\mathbb {Z} _{q}$ который состоит из $m$ равномерно случайные векторы ${\boldsymbol {a_{i}}}\in \mathbb {Z} _{q}^{n}$: $A=[{\boldsymbol {a_{1}}}|\cdots |{\boldsymbol {a_{m}}}]$. Найдите ненулевой вектор ${\boldsymbol {x}}\in \mathbb {Z} ^{m}$ такое, что для некоторой нормы $\|\cdot \|$:

• $0<\|{\boldsymbol {x}}\|\leq \beta$,
• $f_{A}({\boldsymbol {x}}):=A{\boldsymbol {x}}={\boldsymbol {0}}\in \mathbb {Z} _{q}^{n}$.

Решение СИС без необходимого ограничения на длину решения ( $\|{\boldsymbol {x}}\|\leq \beta$) легко вычислить с помощью метода исключения Гаусса . Мы также требуем $\beta <q$, в противном случае ${\boldsymbol {x}}=(q,0,\ldots ,0)\in \mathbb {Z} ^{m}$ это тривиальное решение.

Чтобы гарантировать $f_{A}({\boldsymbol {x}})$ имеет нетривиальное короткое решение, нам требуется:

• $\beta \geq {\sqrt {n\log q}}$, и
• $m\geq n\log q$

Теорема: Для любого $m=\operatorname {poly} (n)$, любой $\beta >0$и любые достаточно большие $q\geq \beta n^{c}$ (для любой константы $c>0$), решение $\operatorname {SIS} _{n,m,q,\beta }$ с немалой вероятностью по меньшей мере так же сложно, как решить задачу $\operatorname {GapSVP} _{\gamma }$ и $\operatorname {SIVP} _{\gamma }$ для некоторых $\gamma =\beta \cdot O({\sqrt {n}})$ с высокой вероятностью в худшем случае.

R-SIS _{q , n , m , β}

Задача SIS, решенная над идеальным кольцом, также называется проблемой Ring-SIS или R-SIS. В этой задаче рассматривается факторкольцо многочленов. $R_{q}=\mathbb {Z} _{q}[x]/(f(x))$ с $f(x)=x^{n}-1$ для некоторого целого числа $n$ и с некоторой нормой $\|\cdot \|$. Особый интерес представляют случаи, когда существуют целые числа $k$ такой, что $n=2^{k}$ поскольку это ограничивает частное круговыми полиномами.

Затем мы определяем проблему следующим образом:

Выбирать $m$ независимые равномерно случайные элементы $a_{i}\in R_{q}$. Определить вектор ${\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{m}$. Найдите ненулевой вектор ${\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}$ такой, что:

• $0<\|{\vec {\boldsymbol {z}}}\|\leq \beta$,
• $f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}$.

Напомним, что для того, чтобы гарантировать существование решения проблемы СИС, нам необходимо $m\approx n\log q$. Однако проблема Ring-SIS обеспечивает нам большую компактность и эффективность: чтобы гарантировать существование решения проблемы Ring-SIS, нам требуется $m\approx \log q$ .

: Негациркулянтная матрица Определение $b$ определяется как:

${\text{for}}\quad b=\sum _{i=0}^{n-1}b_{i}x^{i}\in R,\quad \operatorname {rot} (b):={\begin{bmatrix}b_{0}&-b_{n-1}&\ldots &-b_{1}\\[0.3em]b_{1}&b_{0}&\ldots &-b_{2}\\[0.3em]\vdots &\vdots &\ddots &\vdots \\[0.3em]b_{n-1}&b_{n-2}&\ldots &b_{0}\end{bmatrix}}$

Когда кольцо факторполиномов $R=\mathbb {Z} [x]/(x^{n}+1)$ для $n=2^{k}$, кольцевое умножение $a_{i}.p_{i}$ можно эффективно вычислить, сначала сформировав $\operatorname {rot} (a_{i})$, нега-циркулянтная матрица $a_{i}$, а затем умножить $\operatorname {rot} (a_{i})$ с $\rho (p_{i}(x))\in Z^{n}$, вектор коэффициентов внедрения $p_{i}$ (или, альтернативно, с $\sigma (p_{i}(x))\in Z^{n}$, вектор канонических коэффициентов.

Более того, проблема R-SIS является частным случаем проблемы SIS, когда матрица $A$ в задаче СИС ограничивается блоками негациркулянта: $A=[\operatorname {rot} (a_{1})|\cdots |\operatorname {rot} (a_{m})]$.

M-SIS _{q , n , d , m , β}

Проблема SIS, решаемая в решетке модулей, также называется проблемой Module-SIS или M-SIS. Как и R-SIS, эта задача рассматривает факторкольцо полиномов. $R=\mathbb {Z} [x]/(f(x))$ и $R_{q}=\mathbb {Z} _{q}[x]/(f(x))$ для $f(x)=x^{n}-1$ с особым интересом в тех случаях, когда $n$ является степенью 2. Тогда пусть $M$ быть модулем ранга $d$ такой, что $M\subseteq R^{d}$ и пусть $\|\cdot \|$ быть произвольной нормой над $R_{q}^{m}$.

Затем мы определяем проблему следующим образом:

Выбирать $m$ независимые равномерно случайные элементы $a_{i}\in R_{q}^{d}$. Определить вектор ${\vec {\boldsymbol {a}}}:=(a_{1},\ldots ,a_{m})\in R_{q}^{d\times m}$. Найдите ненулевой вектор ${\vec {\boldsymbol {z}}}:=(z_{1},\ldots ,z_{m})\in R^{m}$ такой, что:

• $0<\|{\vec {\boldsymbol {z}}}\|\leq \beta$,
• $f_{\vec {\boldsymbol {a}}}({\vec {\boldsymbol {z}}}):={\vec {\boldsymbol {a}}}^{T}.{\vec {\boldsymbol {z}}}=\sum _{i=1}^{m}a_{i}.z_{i}=0\in R_{q}^{d}$.

Хотя M-SIS является менее компактным вариантом SIS, чем R-SIS, проблема M-SIS асимптотически по крайней мере так же сложна, как и R-SIS, и, следовательно, дает более жесткие ограничения на предположение о жесткости SIS. Это делает предположение о твердости M-SIS более безопасным, но менее эффективным базовым предположением по сравнению с R-SIS.

См. также

• Решеточная криптография
• Гомоморфное шифрование
• Кольцевое обучение с ошибками обмена ключами
• Постквантовая криптография
• Проблема с решеткой