Алгоритм Теруи-Кашивабары-Ханаоки: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Dralles (обсуждение | вклад) |
Dralles (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
=Свойства и структура алгоритма= | =Свойства и структура алгоритма= | ||
==Общее описание алгоритма== | |||
Стойкость многих из существующих на сегодняшний день криптографических схем, устойчивых к атакам с использованием | |||
квантового вычислителя, основана на задачах из теории решеток. | |||
Одной из таких задач является задача поиска кратчайшего вектора в решетке (Shortest Vector Problem или SVP). | |||
Алгоритм Теруи-Кашивабары-Ханаоки <ref>Teruya Tadanori, Kashiwabara Kenji, Hanaoka Goichiro. Fast Lattice Basis Reduction | |||
Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem</ref> | |||
использует параллельные вычисления для приближенного решения задачи SVP. | |||
Для решения поставленной задачи алгоритм строит базис заданной решетки с как можно меньшей суммой квадратов норм базисных векторов | |||
Грамма-Шмидта. | |||
В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>Fukase Masaharu, Kashiwabara Kenji. An Accelerated Algorithm for Solving SVP | |||
Based on Statistical Analysis</ref>. | |||
==Математическое описание алгоритма== | ==Математическое описание алгоритма== | ||
===Обозначения=== | |||
Пусть <math>B = (\vec{b_1}, \ldots, \vec{b_n})</math> - базис решетки. | |||
Соответствующие ортоганальные вектора Грама-Шмидта обозначим | |||
<math>\vec{b_{1}^{*}}, \ldots, \vec{b_{1}^{*}} \in \mathbb{R}^{n}</math>. | |||
Данные вектора определяются следующим образом: | |||
<math>{ \vec{{b}_{i}^{*}} = \vec{b_i} - \sum_{j = 1}^{i - 1} \mu_{B, i, j} \vec{{b}_{j}^{*}} }</math>, где | |||
<math>{ \mu_{B, i, j} = \langle \vec{b_i}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2 }</math>. | |||
Определим отображение | |||
<math>\pi_{B, i} : \mathbb{R}^n \rightarrow \mathscr{L}^{\perp}(\vec{b_1}, \ldots, \vec{b_{i - 1}})</math> | |||
следующим образом: | |||
:<math>\forall \vec{v} \in \mathbb{R}^n ~ \pi_{B, i}(\vec{v}) = \vec{v} - \sum_{j = 1}^{i - 1} v_{ j} \vec{{b}_{j}^{*}}, | |||
\text{ где } v_{ i} = \langle \vec{v}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2.</math> | |||
Через <math>\Lambda_{B, i}</math> будем обозначать следующее множество : | |||
:<math>\Lambda_{B, i} = \pi_{B, i}(\Lambda) = \{ \pi_{B, i}(\vec{v}) ~|~ \vec{v} \in \Lambda \}</math> | |||
===Представление в виде натуральных чисел=== | |||
Пусть <math>B = (\vec{b_1}, \ldots, \vec{b_n})</math> - базис решетки <math>\Lambda</math>. | |||
''Представлением в виде натуральных чисел'' вектора решетки | |||
<math>\vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda</math> в базисе <math>B</math> называется вектор | |||
из неотрицательных целых чисел <math>(\mathfrak{n}_1, \ldots, \mathfrak{n}_n) \in \mathbb{N}^n</math>, такой, что | |||
<math>{-(\mathfrak{n}_i + 1) / 2 < \nu_i \le - \mathfrak{n}_i / 2}</math> или | |||
<math>{\mathfrak{n}_i / 2 < \nu_i \le (\mathfrak{n}_i + 1) / 2}</math>. | |||
Пусть <math>B = (\vec{b_1}, \ldots, \vec{b_n})</math> - базис решетки <math>\Lambda</math> и | |||
<math>{\vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda}</math>. | |||
Для любого <math>\vec{v} \in \Lambda</math> его представление в виде натуральных чисел определено однозначно, | |||
а отображение <math>{\bf{n}}_{B} ~ \Lambda \rightarrow \mathbb{N}^{n}</math>, задающиеся как | |||
<math>{\bf{n}}_{B}(v) = (\mathfrak{n}_1, \ldots, \mathfrak{n}_n)</math>, является биекцией | |||
<ref>Fukase Masaharu, Kashiwabara Kenji. An Accelerated Algorithm for Solving SVP | |||
Based on Statistical Analysis</ref>. | |||
===Индекс вставки=== | |||
Пусть <math>B = (\vec{b_1}, \ldots, \vec{b_n})</math> - базис решетки <math>\Lambda</math>, <math>\vec{v} \in \Lambda</math>. | |||
<math>\delta</math>''-индексом вставки'' вектора <math>\vec{v}</math> для базиса <math>B</math> назовем число | |||
:<math>h_{\delta}(\vec{v}) = \min( \{ i ~ | ~ \| \pi_{B, i}(\vec{v}) \|^2 < \delta \| \vec{{b}^{*}_{i}} \|^2\} \cup \infty)</math> | |||
===Глобальные хранилища векторов=== | ===Глобальные хранилища векторов=== | ||
| Строка 44: | Строка 95: | ||
:<math>\| \vec{b_{j}^{*}} \|^2 - \| \pi_{B, i}(\vec{v_i}) \|^2 \rightarrow \max.</math> | :<math>\| \vec{b_{j}^{*}} \|^2 - \| \pi_{B, i}(\vec{v_i}) \|^2 \rightarrow \max.</math> | ||
Если такой <math>\vec{v_i}</math> не найден, то алгоритм переходит к следующему шагу. | Если такой <math>\vec{v_i}</math> не найден, то алгоритм переходит к следующему шагу. | ||
Иначе к <math>B</math> применяется <math>\delta</math>-LLL алгоритм<ref> | Иначе к <math>B</math> применяется <math>\delta</math>-LLL алгоритм<ref>Lenstra A. K., Lenstra H. W., Lovasz L. Factoring polynomials with rational coefficients</ref> | ||
по индексу <math>j</math> c вектором <math>\vec{v_i}</math>. | |||
Далее обновляются значения <math>\delta'_k, {k = \ell_{\mathrm{lc}} + 1, \ldots, n}</math> по следующим правилам: | Далее обновляются значения <math>\delta'_k, {k = \ell_{\mathrm{lc}} + 1, \ldots, n}</math> по следующим правилам: | ||
:<math>\delta'_{k} = \delta'_{k} - \delta'' \text{ для всех } k = \ell_{\mathrm{lc}} + 1, \ldots, j - 1,</math> | :<math>\delta'_{k} = \delta'_{k} - \delta'' \text{ для всех } k = \ell_{\mathrm{lc}} + 1, \ldots, j - 1,</math> | ||
| Строка 74: | Строка 126: | ||
После чего базис <math>B</math> модифицируется так, чтобы функция <math>\mathrm{Eval}(B, \Theta)</math> | После чего базис <math>B</math> модифицируется так, чтобы функция <math>\mathrm{Eval}(B, \Theta)</math> | ||
достигала на нем своего минимума. | достигала на нем своего минимума. | ||
Чтобы этого достичь, к <math>B</math> применяется алгоритм <math>\delta</math>-LLL<ref> | Чтобы этого достичь, к <math>B</math> применяется алгоритм <math>\delta</math>-LLL<ref>Lenstra A. K., Lenstra H. W., Lovasz L. Factoring polynomials with rational coefficients</ref> | ||
по индексу <math>i</math> с вектором <math>\vec{v}</math>, | |||
где <math>\vec{v}</math> - вектор из глобального хранилища запасных векторов, для которого выполнено | где <math>\vec{v}</math> - вектор из глобального хранилища запасных векторов, для которого выполнено | ||
<math>{h_{\delta_{\mathrm{stock}}}(\vec{v}) = i \le \ell_{\mathrm{fc}}}</math>. | <math>{h_{\delta_{\mathrm{stock}}}(\vec{v}) = i \le \ell_{\mathrm{fc}}}</math>. | ||
| Строка 92: | Строка 145: | ||
=Литература= | =Литература= | ||
<references \> | |||
Текущая версия от 18:14, 21 октября 2019
Свойства и структура алгоритма
Общее описание алгоритма
Стойкость многих из существующих на сегодняшний день криптографических схем, устойчивых к атакам с использованием квантового вычислителя, основана на задачах из теории решеток. Одной из таких задач является задача поиска кратчайшего вектора в решетке (Shortest Vector Problem или SVP).
Алгоритм Теруи-Кашивабары-Ханаоки [1] использует параллельные вычисления для приближенного решения задачи SVP. Для решения поставленной задачи алгоритм строит базис заданной решетки с как можно меньшей суммой квадратов норм базисных векторов Грамма-Шмидта. В основу алгоритма лег алгоритм Фукаши-Кашивабары[2].
Математическое описание алгоритма
Обозначения
Пусть [math]\displaystyle{ B = (\vec{b_1}, \ldots, \vec{b_n}) }[/math] - базис решетки. Соответствующие ортоганальные вектора Грама-Шмидта обозначим [math]\displaystyle{ \vec{b_{1}^{*}}, \ldots, \vec{b_{1}^{*}} \in \mathbb{R}^{n} }[/math]. Данные вектора определяются следующим образом: [math]\displaystyle{ { \vec{{b}_{i}^{*}} = \vec{b_i} - \sum_{j = 1}^{i - 1} \mu_{B, i, j} \vec{{b}_{j}^{*}} } }[/math], где [math]\displaystyle{ { \mu_{B, i, j} = \langle \vec{b_i}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2 } }[/math].
Определим отображение [math]\displaystyle{ \pi_{B, i} : \mathbb{R}^n \rightarrow \mathscr{L}^{\perp}(\vec{b_1}, \ldots, \vec{b_{i - 1}}) }[/math] следующим образом:
- [math]\displaystyle{ \forall \vec{v} \in \mathbb{R}^n ~ \pi_{B, i}(\vec{v}) = \vec{v} - \sum_{j = 1}^{i - 1} v_{ j} \vec{{b}_{j}^{*}}, \text{ где } v_{ i} = \langle \vec{v}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2. }[/math]
Через [math]\displaystyle{ \Lambda_{B, i} }[/math] будем обозначать следующее множество :
- [math]\displaystyle{ \Lambda_{B, i} = \pi_{B, i}(\Lambda) = \{ \pi_{B, i}(\vec{v}) ~|~ \vec{v} \in \Lambda \} }[/math]
Представление в виде натуральных чисел
Пусть [math]\displaystyle{ B = (\vec{b_1}, \ldots, \vec{b_n}) }[/math] - базис решетки [math]\displaystyle{ \Lambda }[/math]. Представлением в виде натуральных чисел вектора решетки [math]\displaystyle{ \vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda }[/math] в базисе [math]\displaystyle{ B }[/math] называется вектор из неотрицательных целых чисел [math]\displaystyle{ (\mathfrak{n}_1, \ldots, \mathfrak{n}_n) \in \mathbb{N}^n }[/math], такой, что [math]\displaystyle{ {-(\mathfrak{n}_i + 1) / 2 \lt \nu_i \le - \mathfrak{n}_i / 2} }[/math] или [math]\displaystyle{ {\mathfrak{n}_i / 2 \lt \nu_i \le (\mathfrak{n}_i + 1) / 2} }[/math].
Пусть [math]\displaystyle{ B = (\vec{b_1}, \ldots, \vec{b_n}) }[/math] - базис решетки [math]\displaystyle{ \Lambda }[/math] и [math]\displaystyle{ {\vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda} }[/math]. Для любого [math]\displaystyle{ \vec{v} \in \Lambda }[/math] его представление в виде натуральных чисел определено однозначно, а отображение [math]\displaystyle{ {\bf{n}}_{B} ~ \Lambda \rightarrow \mathbb{N}^{n} }[/math], задающиеся как [math]\displaystyle{ {\bf{n}}_{B}(v) = (\mathfrak{n}_1, \ldots, \mathfrak{n}_n) }[/math], является биекцией [3].
Индекс вставки
Пусть [math]\displaystyle{ B = (\vec{b_1}, \ldots, \vec{b_n}) }[/math] - базис решетки [math]\displaystyle{ \Lambda }[/math], [math]\displaystyle{ \vec{v} \in \Lambda }[/math]. [math]\displaystyle{ \delta }[/math]-индексом вставки вектора [math]\displaystyle{ \vec{v} }[/math] для базиса [math]\displaystyle{ B }[/math] назовем число
- [math]\displaystyle{ h_{\delta}(\vec{v}) = \min( \{ i ~ | ~ \| \pi_{B, i}(\vec{v}) \|^2 \lt \delta \| \vec{{b}^{*}_{i}} \|^2\} \cup \infty) }[/math]
Глобальные хранилища векторов
Для корректной работы алгоритма требуется два глобальных хранилища векторов, доступ к которым будут иметь все процессы. Первое из них назовем глобальным хранилищем запасных векторов, а второе - глобальным хранилищем соединительных векторов.
Генерация векторов решетки
На вход принимается базис решетки [math]\displaystyle{ B }[/math] и набор представлений в виде натуральных чисел векторов решетки. Далее генерируется набор векторов из данной решетки, которые соответствуют описанным выше представлениям. При этом понятно, что для разных базисов одной и той же решетки при одном и том же наборе представлений в виде натуральных чисел, будут сгенерированы разные вектора.
Редукция базиса
В алгоритме редукции базиса на вход поступают базис решетки [math]\displaystyle{ B }[/math], набор [math]\displaystyle{ S' }[/math] представлений в виде натуральных чисел, целые числа [math]\displaystyle{ \ell_{\mathrm{fc}}, \ell_{\mathrm{lc}} }[/math], вещественные значения [math]\displaystyle{ \delta_{\mathrm{stock}}, \delta, \delta', \delta'' }[/math] и целочисленное значение pui (process-unique information).
До начала работы алгоритма заводится массив переменных [math]\displaystyle{ \delta'_i, i =\ell_{\mathrm{lc}} + 1, \ldots, n }[/math] все элементы которого изначально равны [math]\displaystyle{ \delta' }[/math].
На первом шаге генерируется набор векторов решетки [math]\displaystyle{ V }[/math] по набору [math]\displaystyle{ S' }[/math] и для каждого [math]\displaystyle{ \vec{v} \in V }[/math] вычисляется [math]\displaystyle{ \delta_{\mathrm{stock}} }[/math]-индекс вставки равный [math]\displaystyle{ i }[/math]. Если таковой удовлетворяет условию [math]\displaystyle{ 1 \le i \le \ell_{\mathrm{fc}} }[/math], то вектор [math]\displaystyle{ \vec{v} }[/math] записывается в глобальное хранилище запасных векторов. Далее, по [math]\displaystyle{ V }[/math] строится набор [math]\displaystyle{ V' = (\vec{v_1}, \ldots, \vec{v_N}) }[/math], для всех векторов которого [math]\displaystyle{ \delta }[/math]-индекс вставки больше [math]\displaystyle{ \ell_{\mathrm{lc}} }[/math].
На следующем шаге производится модификация исходного базиса решетки. Исходный базис [math]\displaystyle{ B }[/math] сохраняется в переменной [math]\displaystyle{ B' }[/math]. После чего ищется вектор [math]\displaystyle{ \vec{v_i} \in V' }[/math] для которого выполнены условия:
- [math]\displaystyle{ j = h_{\delta'_{j}}(\vec{v}) \text{ где }\ell_{\mathrm{lc}} \lt j \le n, }[/math]
- [math]\displaystyle{ \| \vec{b_{j}^{*}} \|^2 - \| \pi_{B, i}(\vec{v_i}) \|^2 \rightarrow \max. }[/math]
Если такой [math]\displaystyle{ \vec{v_i} }[/math] не найден, то алгоритм переходит к следующему шагу. Иначе к [math]\displaystyle{ B }[/math] применяется [math]\displaystyle{ \delta }[/math]-LLL алгоритм[4] по индексу [math]\displaystyle{ j }[/math] c вектором [math]\displaystyle{ \vec{v_i} }[/math]. Далее обновляются значения [math]\displaystyle{ \delta'_k, {k = \ell_{\mathrm{lc}} + 1, \ldots, n} }[/math] по следующим правилам:
- [math]\displaystyle{ \delta'_{k} = \delta'_{k} - \delta'' \text{ для всех } k = \ell_{\mathrm{lc}} + 1, \ldots, j - 1, }[/math]
- [math]\displaystyle{ \delta'_{k} = \delta' \text{ для всех } k = j, \ldots, n. }[/math]
Если [math]\displaystyle{ (i + \text{pui}) \bmod N \equiv 0 }[/math], то выполняется переход к шагу 3. В противном случае, к модифицированному базису [math]\displaystyle{ B }[/math] снова применяется шаг 2.
На третьем шаге проверяется условие [math]\displaystyle{ B = B' }[/math]. В случае успеха алгоритм завершает свою работу с результатом [math]\displaystyle{ B }[/math]. В противном случае алгоритм продолжает свою работу с шага 1.
Алгоритм Теруи-Кашивабары-Ханаоки
На вход алгшоритма поступют базис решетки [math]\displaystyle{ B }[/math], наборы [math]\displaystyle{ S }[/math] и [math]\displaystyle{ S' }[/math] представлений в виде натуральных чисел, целые числа [math]\displaystyle{ \ell_{\mathrm{fc}}, \ell_{\mathrm{lc}}, \ell_{\mathrm{link}} }[/math], вещественные значения [math]\displaystyle{ \delta_{\mathrm{stock}}, \delta, \delta', \delta'', \Theta }[/math] и целочисленное значение pui (process-unique information).
На первом шаге алгоритма в переменную [math]\displaystyle{ B' }[/math] сохраняется исходный базис [math]\displaystyle{ B }[/math]. После чего к [math]\displaystyle{ B }[/math] применяется алгоритм редукции базиса. Далее, генерируется набор векторов решетки [math]\displaystyle{ V }[/math] по базису [math]\displaystyle{ B }[/math] и набору представлений в виде натуральных чисел [math]\displaystyle{ S }[/math]. Для каждого [math]\displaystyle{ \vec{v} \in V }[/math] вычисляется [math]\displaystyle{ \delta_{\mathrm{stock}} }[/math]-индекс вставки равный [math]\displaystyle{ i }[/math]. Если таковой удовлетворяет условию [math]\displaystyle{ 1 \le i \le \ell_{\mathrm{fc}} }[/math], то вектор [math]\displaystyle{ \vec{v} }[/math] записывается в глобальное хранилище запасных векторов.
На втором шаге вычисляется следующая оценочная функция:
- [math]\displaystyle{ \mathrm{Eval}(B, \Theta) = \sum_{i = 1}^{n} \Theta^{i} \| \vec{b_{i}^{*}} \|^2. }[/math]
После чего базис [math]\displaystyle{ B }[/math] модифицируется так, чтобы функция [math]\displaystyle{ \mathrm{Eval}(B, \Theta) }[/math] достигала на нем своего минимума. Чтобы этого достичь, к [math]\displaystyle{ B }[/math] применяется алгоритм [math]\displaystyle{ \delta }[/math]-LLL[5] по индексу [math]\displaystyle{ i }[/math] с вектором [math]\displaystyle{ \vec{v} }[/math], где [math]\displaystyle{ \vec{v} }[/math] - вектор из глобального хранилища запасных векторов, для которого выполнено [math]\displaystyle{ {h_{\delta_{\mathrm{stock}}}(\vec{v}) = i \le \ell_{\mathrm{fc}}} }[/math].
На третьем шаге сохраняем базисные вектора с индексами от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ \ell_\mathrm{link} }[/math] в глобальное хранилище соединительных векторов. Далее выгружаем все глобальное хранилище соединительных векторов. Из векторов хранилища и векторов базиса [math]\displaystyle{ B }[/math] собираем наименьший базис решетки [math]\displaystyle{ B'' }[/math] в лексикографическом порядке. Затем заменяем базис [math]\displaystyle{ B }[/math] базисом [math]\displaystyle{ B'' }[/math]. Если существует вектор [math]\displaystyle{ \vec{v} }[/math] из глобального хранилища запасных векторов такой, что [math]\displaystyle{ \| \vec{v} \| \lt 1.05 \cdot (\Gamma(n / 2 + 1) \cdot \det(\Lambda))^{1 / n} / \sqrt{\pi} }[/math], то алгоритм возвращает вектор [math]\displaystyle{ \vec{v} }[/math]. Если [math]\displaystyle{ B' = B }[/math], то алгоритм возвращает базис [math]\displaystyle{ B }[/math]. В противном случае алгоритм продолжает свою работу с шага 1.
Литература
<references \>
- ↑ Teruya Tadanori, Kashiwabara Kenji, Hanaoka Goichiro. Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem
- ↑ Fukase Masaharu, Kashiwabara Kenji. An Accelerated Algorithm for Solving SVP Based on Statistical Analysis
- ↑ Fukase Masaharu, Kashiwabara Kenji. An Accelerated Algorithm for Solving SVP Based on Statistical Analysis
- ↑ Lenstra A. K., Lenstra H. W., Lovasz L. Factoring polynomials with rational coefficients
- ↑ Lenstra A. K., Lenstra H. W., Lovasz L. Factoring polynomials with rational coefficients