Краткое целочисленное решение задачи - Short integer solution problem

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

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

Решетки

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

${\displaystyle {\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}\}}$

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

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

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

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

${\displaystyle \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})}$

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

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

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

Примеры:^[3]

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}.}$

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

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

${\displaystyle {\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\}}$

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

${\displaystyle \Rightarrow )}$

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

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

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

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

Идеальные решетки^[4][5]

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

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

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

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

где сложение и умножение приводятся по модулю ${\displaystyle f(x)}$.

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

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

${\displaystyle {\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}.}$

Замечание:^[6]

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

Краткое целочисленное решение задачи

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

SIS_п,м,q,β

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

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

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

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

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

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

Кольцо-СИС

Проблема Ring-SIS, компактный кольцевой аналог проблемы SIS, изучалась в.^[2][8] Они рассматривают кольцо факторных полиномов ${\displaystyle R=\mathbb {Z} [x]/(f(x))}$ с ${\displaystyle f(x)=x^{n}-1}$ и ${\displaystyle x^{2^{k}}+1}$соответственно, и расширяют определение норма по векторам в ${\displaystyle \mathbb {R} ^{n}}$ к векторам в ${\displaystyle R^{m}}$ следующее:

Учитывая вектор ${\displaystyle {\vec {\boldsymbol {z}}}=(p_{1},\ldots ,p_{m})\in R^{m}}$ куда ${\displaystyle p_{i}(x)}$ являются полиномами от ${\displaystyle R}$. Рассмотрим коэффициент вложения ${\displaystyle \mathbb {Z} }$-модульный изоморфизм ${\displaystyle \rho }$:

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

Позволять ${\displaystyle {\boldsymbol {z_{i}}}=\rho (p_{i}(x))\in Z^{n}}$. Определить норму ${\displaystyle {\vec {\boldsymbol {z}}}}$ в качестве:

${\displaystyle \|{\vec {\boldsymbol {z}}}\|:={\sqrt {\sum _{i=1}^{m}\|{\boldsymbol {z_{i}}}\|^{2}}}}$

В качестве альтернативы, лучшее представление о норме достигается за счет использования каноническое вложение. Каноническое вложение определяется как:

${\displaystyle {\begin{aligned}\sigma :R=\mathbb {Z} /(f(x))&\rightarrow \mathbb {C} ^{n}\\p(x)&\mapsto (p(\alpha _{1}),\ldots ,p(\alpha _{n})\end{aligned}}}$

куда ${\displaystyle \alpha _{i}}$ это ${\displaystyle i^{th}}$ сложный корень ${\displaystyle f(x)}$ за ${\displaystyle i=1,\ldots ,n}$.

R-SIS_м,q,β

Учитывая кольцо факторных полиномов ${\displaystyle R=\mathbb {Z} [x]/(f(x))}$, определять

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

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

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

Определение: В отрицательно циркулянтная матрица из ${\displaystyle b}$ определяется как:

${\displaystyle {\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}}}$

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

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

Смотрите также

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

Рекомендации

1. Айтай, Миклош. [Создание сложных экземпляров задач решетки.] Труды двадцать восьмого ежегодного симпозиума ACM по теории вычислений. ACM, 1996.
2. Микчанчо, Даниэле. [Обобщенные компактные рюкзаки, циклические решетки и эффективные односторонние функции из предположений о наихудшей сложности.] Основы компьютерных наук, 2002. Труды. 43-й ежегодный симпозиум IEEE по. IEEE, 2002.
3. Фукшанский, Ленни и Сюнь Сунь. [О геометрии циклических решеток.] Дискретная и вычислительная геометрия 52.2 (2014): 240–259.
4. Крейг Джентри. Полностью гомоморфное шифрование с использованием идеальных решеток. В 41-й симпозиум ACM по теории вычислений (STOC), 2009.
5. http://web.cse.ohio-state.edu/~lai/5359-aut13/05.Gentry-FHE-concrete-scheme.pdf
6. Пайкерт, Крис. [Десятилетие решетчатой ​​криптографии.] Cryptology ePrint Archive, Report 2015/939, 2015.
7. Пайкерт, Крис и Алон Розен. [Эффективное хеширование, устойчивое к коллизиям, исходя из наихудших предположений о циклических решетках.] Теория криптографии. Springer Berlin Heidelberg, 2006. 145–166.
8. Любашевский, Вадим и др. [SWIFFT: скромное предложение по хешированию FFT.] Быстрое программное шифрование. Springer Berlin Heidelberg, 2008 г.
9. Ланглуа, Аделина и Дамьен Стеле. [Редукции от худшего случая к среднему для решеток модулей.] Проекты, коды и криптография 75.3 (2015): 565–599.