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

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

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

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

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

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

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

Пусть $B = (\vec{b_1}, \ldots, \vec{b_n})$ - базис решетки. Соответствующие ортоганальные вектора Грама-Шмидта обозначим $\vec{b_{1}^{*}}, \ldots, \vec{b_{1}^{*}} \in \mathbb{R}^{n}$. Данные вектора определяются следующим образом: ${ \vec{{b}_{i}^{*}} = \vec{b_i} - \sum_{j = 1}^{i - 1} \mu_{B, i, j} \vec{{b}_{j}^{*}} }$, где ${ \mu_{B, i, j} = \langle \vec{b_i}, \vec{{b}_{j}^{*}} \rangle / \| \vec{{b}_{j}^{*}} \|^2 }$.

Определим отображение $\pi_{B, i} : \mathbb{R}^n \rightarrow \mathscr{L}^{\perp}(\vec{b_1}, \ldots, \vec{b_{i - 1}})$ следующим образом:

$\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.$

Через $\Lambda_{B, i}$ будем обозначать следующее множество :

$\Lambda_{B, i} = \pi_{B, i}(\Lambda) = \{ \pi_{B, i}(\vec{v}) ~|~ \vec{v} \in \Lambda \}$

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

Пусть $B = (\vec{b_1}, \ldots, \vec{b_n})$ - базис решетки $\Lambda$. Представлением в виде натуральных чисел вектора решетки $\vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda$ в базисе $B$ называется вектор из неотрицательных целых чисел $(\mathfrak{n}_1, \ldots, \mathfrak{n}_n) \in \mathbb{N}^n$, такой, что ${-(\mathfrak{n}_i + 1) / 2 \lt \nu_i \le - \mathfrak{n}_i / 2}$ или ${\mathfrak{n}_i / 2 \lt \nu_i \le (\mathfrak{n}_i + 1) / 2}$.

Пусть $B = (\vec{b_1}, \ldots, \vec{b_n})$ - базис решетки $\Lambda$ и ${\vec{v} = \sum_{i = 1}^{n} \nu_i \vec{{b}_{i}} \in \Lambda}$. Для любого $\vec{v} \in \Lambda$ его представление в виде натуральных чисел определено однозначно, а отображение ${\bf{n}}_{B} ~ \Lambda \rightarrow \mathbb{N}^{n}$, задающиеся как ${\bf{n}}_{B}(v) = (\mathfrak{n}_1, \ldots, \mathfrak{n}_n)$, является биекцией.

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

Пусть $B = (\vec{b_1}, \ldots, \vec{b_n})$ - базис решетки $\Lambda$, $\vec{v} \in \Lambda$. $\delta$-индексом вставки вектора $\vec{v}$ для базиса $B$ назовем число

$h_{\delta}(\vec{v}) = \min( \{ i ~ | ~ \| \pi_{B, i}(\vec{v}) \|^2 \lt \delta \| \vec{{b}^{*}_{i}} \|^2\} \cup \infty)$

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

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

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

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

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

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

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

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

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

$j = h_{\delta'_{j}}(\vec{v}) \text{ где }\ell_{\mathrm{lc}} \lt j \le n,$

$\| \vec{b_{j}^{*}} \|^2 - \| \pi_{B, i}(\vec{v_i}) \|^2 \rightarrow \max.$

Если такой $\vec{v_i}$ не найден, то алгоритм переходит к следующему шагу. Иначе к $B$ применяется $\delta$-LLL алгоритм по индексу $j$ c вектором $\vec{v_i}$. Далее обновляются значения $\delta'_k, {k = \ell_{\mathrm{lc}} + 1, \ldots, n}$ по следующим правилам:

$\delta'_{k} = \delta'_{k} - \delta'' \text{ для всех } k = \ell_{\mathrm{lc}} + 1, \ldots, j - 1,$

$\delta'_{k} = \delta' \text{ для всех } k = j, \ldots, n.$

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

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

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

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

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

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

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

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

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

2 Литература

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

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

• Шаблон:LLL,

Parallel

NNR

NNR

LLL

LLL