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

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

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

Алгоритм Теруи-Кашивабары-Ханаоки <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>.

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

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

===Обозначения===
Пусть <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>

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

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

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

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

=Литература=

<references \>