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

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

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

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

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

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], является биекцией.

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 алгоритм по индексу [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по индексу [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 Литература

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:LLL,

Parallel

NNR

NNR

LLL

LLL