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

Dralles: /* Общее описание алгоритма */

2019-10-21T18:14:51Z

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

← Предыдущая версия		Версия от 18:14, 21 октября 2019
Строка 2:		Строка 2:

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

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

	Алгоритм Теруи-Кашивабары-Ханаоки <ref>Teruya Tadanori, Kashiwabara Kenji, Hanaoka Goichiro. Fast Lattice Basis Reduction		Алгоритм Теруи-Кашивабары-Ханаоки <ref>Teruya Tadanori, Kashiwabara Kenji, Hanaoka Goichiro. Fast Lattice Basis Reduction
	Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem</ref>		Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem</ref>
	использует параллельные вычисления для решения задачи SVP.		использует параллельные вычисления для приближенного решения задачи SVP.
			Для решения поставленной задачи алгоритм строит базис заданной решетки с как можно меньшей суммой квадратов норм базисных векторов
			Грамма-Шмидта.
	В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>Fukase Masaharu, Kashiwabara Kenji. An Accelerated Algorithm for Solving SVP		В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>Fukase Masaharu, Kashiwabara Kenji. An Accelerated Algorithm for Solving SVP
	Based on Statistical Analysis</ref>.		Based on Statistical Analysis</ref>.

	~~На предположении о сложности решения задачи поиска кратчайшего вектора в решетке (Shortest vector problem или SVP)~~
	~~основана стойкость некоторых современных схем, устойчивых к атакам с помощью квантового вычислителя.~~

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

Dralles в 18:02, 21 октября 2019

2019-10-21T18:02:01Z

@@ Строка 3: / Строка 3: @@
 ==Общее описание алгоритма==
-Алгоритм Теруи-Кашивабары-Ханаоки <ref>Parallel</ref> использует параллельные вычисления для решения задачи SVP.
+Алгоритм Теруи-Кашивабары-Ханаоки <ref>Teruya Tadanori, Kashiwabara Kenji, Hanaoka Goichiro. Fast Lattice Basis Reduction
-В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>NNR</ref>.
+Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem</ref>
 На предположении о сложности решения задачи поиска кратчайшего вектора в решетке (Shortest vector problem или SVP)
@@ Строка 41: / Строка 44: @@
 Для любого <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>NNR</ref>.
+<math>{\bf{n}}_{B}(v) = (\mathfrak{n}_1, \ldots, \mathfrak{n}_n)</math>, является биекцией
 ===Индекс вставки===
@@ Строка 87: / Строка 92: @@
 :<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 алгоритм<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>\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>
@@ Строка 117: / Строка 123: @@
 После чего базис <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>\vec{v}</math> - вектор из глобального хранилища запасных векторов, для которого выполнено
 <math>{h_{\delta_{\mathrm{stock}}}(\vec{v}) = i \le \ell_{\mathrm{fc}}}</math>.
@@ Строка 135: / Строка 142: @@
 =Литература=
-*{{статья
+<references \>

Dralles в 14:36, 19 октября 2019

2019-10-19T14:36:25Z

← Предыдущая версия		Версия от 14:36, 19 октября 2019
Строка 1:		Строка 1:
	=Свойства и структура алгоритма=		=Свойства и структура алгоритма=

	==~~Математическое~~ описание алгоритма==		==Общее описание алгоритма==

	Алгоритм Теруи-Кашивабары-Ханаоки <ref>Parallel</ref> использует параллельные вычисления для решения задачи SVP.		Алгоритм Теруи-Кашивабары-Ханаоки <ref>Parallel</ref> использует параллельные вычисления для решения задачи SVP.
	В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>NNR</ref>.		В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>NNR</ref>.

			На предположении о сложности решения задачи поиска кратчайшего вектора в решетке (Shortest vector problem или SVP)
			основана стойкость некоторых современных схем, устойчивых к атакам с помощью квантового вычислителя.

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

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

Dralles: /* Свойства и структура алгоритма */

2019-10-19T14:30:20Z

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

@@ Строка 5: / Строка 5: @@
 Алгоритм Теруи-Кашивабары-Ханаоки <ref>Parallel</ref> использует параллельные вычисления для решения задачи SVP.
 В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>NNR</ref>.
 ===Глобальные хранилища векторов===

Dralles: /* Свойства и структура алгоритма */

2019-10-19T14:14:25Z

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

@@ Строка 3: / Строка 3: @@
 ==Математическое описание алгоритма==
-Алгоритм Теру-Кашивабары-Ханаоки использует параллельные вычисления для решения задачи SVP.
+Алгоритм Теруи-Кашивабары-Ханаоки <ref>Parallel</ref> использует параллельные вычисления для решения задачи SVP.
-В основу алгоритма лег алгоритм Фукаши-Кашивабары.
+В основу алгоритма лег алгоритм Фукаши-Кашивабары<ref>NNR</ref>.
 ===Глобальные хранилища векторов===
@@ Строка 44: / Строка 44: @@
 :<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 алгоритм по индексу <math>j</math> c вектором <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>\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>
@@ Строка 74: / Строка 74: @@
 После чего базис <math>B</math> модифицируется так, чтобы функция <math>\mathrm{Eval}(B, \Theta)</math>
 достигала на нем своего минимума.
-Чтобы этого достичь, к <math>B</math> применяется алгоритм <math>\delta</math>-LLL по индексу <math>i</math> с вектором <math>\vec{v}</math>,
+Чтобы этого достичь, к <math>B</math> применяется алгоритм <math>\delta</math>-LLL<ref>LLL</ref>по индексу <math>i</math> с вектором <math>\vec{v}</math>,
 где <math>\vec{v}</math> - вектор из глобального хранилища запасных векторов, для которого выполнено
 <math>{h_{\delta_{\mathrm{stock}}}(\vec{v}) = i \le \ell_{\mathrm{fc}}}</math>.
@@ Строка 89: / Строка 89: @@
 Если <math>B' = B</math>, то алгоритм возвращает базис <math>B</math>.
 В противном случае алгоритм продолжает свою работу с шага 1.

Dralles: Новая страница: «=Свойства и структура алгоритма= ==Математическое описание алгоритма== Алгоритм Теру-Ка…»

2019-10-19T13:48:29Z

Новая страница: «=Свойства и структура алгоритма= ==Математическое описание алгоритма== Алгоритм Теру-Ка…»

Новая страница

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

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

Алгоритм Теру-Кашивабары-Ханаоки использует параллельные вычисления для решения задачи SVP.
В основу алгоритма лег алгоритм Фукаши-Кашивабары.

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

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

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

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

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

В алгоритме редукции базиса на вход поступают базис решетки <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}} < 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 алгоритм по индексу <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.

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

На вход алгшоритма поступют базис решетки <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 по индексу <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} \| < 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.