Алгоритм Теруи-Кашивабары-Ханаоки: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
 
(не показаны 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>.
  
 
==Математическое описание алгоритма==
 
==Математическое описание алгоритма==
  
Алгоритм Теруи-Кашивабары-Ханаоки <ref>Parallel</ref> использует параллельные вычисления для решения задачи SVP.
+
===Обозначения===
В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>NNR</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>LLL</ref> по индексу <math>j</math> c вектором <math>\vec{v_i}</math>.
+
Иначе к <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>LLL</ref>по индексу <math>i</math> с вектором <math>\vec{v}</math>,
+
Чтобы этого достичь, к <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 \>
  | автор = Tadanori Teruya and
 
              Kenji Kashiwabara and
 
              Goichiro Hanaoka
 
  | заглавие = Fast Lattice Basis Reduction Suitable for Massive Parallelization
 
              and Its Application to the Shortest Vector Problem
 
  | оригинал = Public-Key Cryptography - {PKC} 2018 - 21st {IACR} International Conference
 
              on Practice and Theory of Public-Key Cryptography, Rio de Janeiro,
 
              Brazil, March 25-29, 2018, Proceedings, Part {I}
 
  | страницы = 437--460
 
  | год      = 2018
 
  | ref = Parallel
 
}}
 
 
 
*{{статья
 
  | автор    = Masaharu Fukase and
 
              Kenji Kashiwabara
 
  | заглавие    = An Accelerated Algorithm for Solving {SVP} Based on Statistical Analysis
 
  | том    = 23
 
  | выпуск  = 1
 
  | страницы    = 67--80
 
  | год      = 2015
 
  | ref = NNR
 
 
 
}}
 
 
 
*{{LLL,
 
    | автор = A. K. Lenstra and H. W. Lenstra and L. Lovasz
 
    | заглавие = Factoring polynomials with rational coefficients
 
    | год = 1982
 
    | том = 261
 
    | страницы = 515--534
 
    | ref = LLL
 
}}
 

Текущая версия на 21:14, 21 октября 2019

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Стойкость многих из существующих на сегодняшний день криптографических схем, устойчивых к атакам с использованием квантового вычислителя, основана на задачах из теории решеток. Одной из таких задач является задача поиска кратчайшего вектора в решетке (Shortest Vector Problem или SVP).

Алгоритм Теруи-Кашивабары-Ханаоки [1] использует параллельные вычисления для приближенного решения задачи SVP. Для решения поставленной задачи алгоритм строит базис заданной решетки с как можно меньшей суммой квадратов норм базисных векторов Грамма-Шмидта. В основу алгоритма лег алгоритм Фукаши-Кашивабары[2].

1.2 Математическое описание алгоритма

1.2.1 Обозначения

Пусть [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]

1.2.2 Представление в виде натуральных чисел

Пусть [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 \lt \nu_i \le - \mathfrak{n}_i / 2}[/math] или [math]{\mathfrak{n}_i / 2 \lt \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], является биекцией [3].

1.2.3 Индекс вставки

Пусть [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 \lt \delta \| \vec{{b}^{*}_{i}} \|^2\} \cup \infty)[/math]

1.2.4 Глобальные хранилища векторов

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

1.2.5 Генерация векторов решетки

На вход принимается базис решетки [math]B[/math] и набор представлений в виде натуральных чисел векторов решетки. Далее генерируется набор векторов из данной решетки, которые соответствуют описанным выше представлениям. При этом понятно, что для разных базисов одной и той же решетки при одном и том же наборе представлений в виде натуральных чисел, будут сгенерированы разные вектора.

1.2.6 Редукция базиса

В алгоритме редукции базиса на вход поступают базис решетки [math]B[/math], набор [math]S'[/math] представлений в виде натуральных чисел, целые числа [math] \ell_{\mathrm{fc}}, \ell_{\mathrm{lc}} [/math], вещественные значения [math]\delta_{\mathrm{stock}}, \delta, \delta', \delta''[/math] и целочисленное значение pui (process-unique information).

До начала работы алгоритма заводится массив переменных [math]\delta'_i, i =\ell_{\mathrm{lc}} + 1, \ldots, n[/math] все элементы которого изначально равны [math]\delta'[/math].

На первом шаге генерируется набор векторов решетки [math]V[/math] по набору [math]S'[/math] и для каждого [math]\vec{v} \in V[/math] вычисляется [math]\delta_{\mathrm{stock}}[/math]-индекс вставки равный [math]i[/math]. Если таковой удовлетворяет условию [math]1 \le i \le \ell_{\mathrm{fc}}[/math], то вектор [math]\vec{v}[/math] записывается в глобальное хранилище запасных векторов. Далее, по [math]V[/math] строится набор [math]V' = (\vec{v_1}, \ldots, \vec{v_N})[/math], для всех векторов которого [math]\delta[/math]-индекс вставки больше [math]\ell_{\mathrm{lc}}[/math].

На следующем шаге производится модификация исходного базиса решетки. Исходный базис [math]B[/math] сохраняется в переменной [math]B'[/math]. После чего ищется вектор [math]\vec{v_i} \in V'[/math] для которого выполнены условия:

[math]j = h_{\delta'_{j}}(\vec{v}) \text{ где }\ell_{\mathrm{lc}} \lt j \le n,[/math]
[math]\| \vec{b_{j}^{*}} \|^2 - \| \pi_{B, i}(\vec{v_i}) \|^2 \rightarrow \max.[/math]

Если такой [math]\vec{v_i}[/math] не найден, то алгоритм переходит к следующему шагу. Иначе к [math]B[/math] применяется [math]\delta[/math]-LLL алгоритм[4] по индексу [math]j[/math] c вектором [math]\vec{v_i}[/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' \text{ для всех } k = j, \ldots, n.[/math]

Если [math](i + \text{pui}) \bmod N \equiv 0[/math], то выполняется переход к шагу 3. В противном случае, к модифицированному базису [math]B[/math] снова применяется шаг 2.

На третьем шаге проверяется условие [math]B = B'[/math]. В случае успеха алгоритм завершает свою работу с результатом [math]B[/math]. В противном случае алгоритм продолжает свою работу с шага 1.

1.2.7 Алгоритм Теруи-Кашивабары-Ханаоки

На вход алгшоритма поступют базис решетки [math]B[/math], наборы [math]S[/math] и [math]S'[/math] представлений в виде натуральных чисел, целые числа [math]\ell_{\mathrm{fc}}, \ell_{\mathrm{lc}}, \ell_{\mathrm{link}}[/math], вещественные значения [math]\delta_{\mathrm{stock}}, \delta, \delta', \delta'', \Theta[/math] и целочисленное значение pui (process-unique information).

На первом шаге алгоритма в переменную [math]B'[/math] сохраняется исходный базис [math]B[/math]. После чего к [math]B[/math] применяется алгоритм редукции базиса. Далее, генерируется набор векторов решетки [math]V[/math] по базису [math]B[/math] и набору представлений в виде натуральных чисел [math]S[/math]. Для каждого [math]\vec{v} \in V[/math] вычисляется [math]\delta_{\mathrm{stock}}[/math]-индекс вставки равный [math]i[/math]. Если таковой удовлетворяет условию [math]1 \le i \le \ell_{\mathrm{fc}}[/math], то вектор [math]\vec{v}[/math] записывается в глобальное хранилище запасных векторов.

На втором шаге вычисляется следующая оценочная функция:

[math]\mathrm{Eval}(B, \Theta) = \sum_{i = 1}^{n} \Theta^{i} \| \vec{b_{i}^{*}} \|^2.[/math]

После чего базис [math]B[/math] модифицируется так, чтобы функция [math]\mathrm{Eval}(B, \Theta)[/math] достигала на нем своего минимума. Чтобы этого достичь, к [math]B[/math] применяется алгоритм [math]\delta[/math]-LLL[5] по индексу [math]i[/math] с вектором [math]\vec{v}[/math], где [math]\vec{v}[/math] - вектор из глобального хранилища запасных векторов, для которого выполнено [math]{h_{\delta_{\mathrm{stock}}}(\vec{v}) = i \le \ell_{\mathrm{fc}}}[/math].

На третьем шаге сохраняем базисные вектора с индексами от [math]1[/math] до [math]\ell_\mathrm{link}[/math] в глобальное хранилище соединительных векторов. Далее выгружаем все глобальное хранилище соединительных векторов. Из векторов хранилища и векторов базиса [math]B[/math] собираем наименьший базис решетки [math]B''[/math] в лексикографическом порядке. Затем заменяем базис [math]B[/math] базисом [math]B''[/math]. Если существует вектор [math]\vec{v}[/math] из глобального хранилища запасных векторов такой, что [math]\| \vec{v} \| \lt 1.05 \cdot (\Gamma(n / 2 + 1) \cdot \det(\Lambda))^{1 / n} / \sqrt{\pi}[/math], то алгоритм возвращает вектор [math]\vec{v}[/math]. Если [math]B' = B[/math], то алгоритм возвращает базис [math]B[/math]. В противном случае алгоритм продолжает свою работу с шага 1.

2 Литература

<references \>

  1. Teruya Tadanori, Kashiwabara Kenji, Hanaoka Goichiro. Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem
  2. Fukase Masaharu, Kashiwabara Kenji. An Accelerated Algorithm for Solving SVP Based on Statistical Analysis
  3. Fukase Masaharu, Kashiwabara Kenji. An Accelerated Algorithm for Solving SVP Based on Statistical Analysis
  4. Lenstra A. K., Lenstra H. W., Lovasz L. Factoring polynomials with rational coefficients
  5. Lenstra A. K., Lenstra H. W., Lovasz L. Factoring polynomials with rational coefficients