Алгоритм Теруи-Кашивабары-Ханаоки: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Dralles (обсуждение | вклад) (Новая страница: «=Свойства и структура алгоритма= ==Математическое описание алгоритма== Алгоритм Теру-Ка…») |
Dralles (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
==Математическое описание алгоритма== | ==Математическое описание алгоритма== | ||
| − | Алгоритм | + | Алгоритм Теруи-Кашивабары-Ханаоки <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{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 алгоритм по индексу <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, {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: | Строка 74: | ||
После чего базис <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 по индексу <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>\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>. | ||
| Строка 89: | Строка 89: | ||
Если <math>B' = B</math>, то алгоритм возвращает базис <math>B</math>. | Если <math>B' = B</math>, то алгоритм возвращает базис <math>B</math>. | ||
В противном случае алгоритм продолжает свою работу с шага 1. | В противном случае алгоритм продолжает свою работу с шага 1. | ||
| + | |||
| + | =Литература= | ||
| + | |||
| + | *{{статья | ||
| + | | автор = 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 | ||
| + | }} | ||
Версия 17:14, 19 октября 2019
Содержание
1 Свойства и структура алгоритма
1.1 Математическое описание алгоритма
Алгоритм Теруи-Кашивабары-Ханаоки [1] использует параллельные вычисления для решения задачи SVP. В основу алгоритма лег алгоритм Фукаши-Кашивабары[2].
1.1.1 Глобальные хранилища векторов
Для корректной работы алгоритма требуется два глобальных хранилища векторов, доступ к которым будут иметь все процессы. Первое из них назовем глобальным хранилищем запасных векторов, а второе - глобальным хранилищем соединительных векторов.
1.1.2 Генерация векторов решетки
На вход принимается базис решетки [math]B[/math] и набор представлений в виде натуральных чисел векторов решетки. Далее генерируется набор векторов из данной решетки, которые соответствуют описанным выше представлениям. При этом понятно, что для разных базисов одной и той же решетки при одном и том же наборе представлений в виде натуральных чисел, будут сгенерированы разные вектора.
1.1.3 Редукция базиса
В алгоритме редукции базиса на вход поступают базис решетки [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 алгоритм[3] по индексу [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.1.4 Алгоритм Теруи-Кашивабары-Ханаоки
На вход алгшоритма поступют базис решетки [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[4]по индексу [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.
