Алгоритм базисного преобразования криптографической решётки

Алгоритм базисного преобразования криптографической решётки (LLL) — это алгоритм уменьшения решётки за полиномиальное время, изобретенный Арьеном Ленстра, Хендриком Ленстра и Ласлом Ловасом в 1982. Задан базис $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ с n-мерными натуральными координатами для рёшетки L, являющаяся дискретной подгруппой Rⁿ с $\ d\leq n$. Алгоритм LLL рассчитывает LLL-уменьшенный базис решётки за время

$O(d^{5}n\log ^{3}B)\,$

где$B$ является наибольшей длинной из $\mathbf {b} _{i}$ в соответствии с евклидовой нормой, то есть

$B=max\left(||\mathbf {b} _{1}||_{2},||\mathbf {b} _{2}||_{2},...,||\mathbf {b} _{d}||_{2}\right)$.

Первоначальные приложения должны были предоставить алгоритмы полиномиального времени для факторизации полиномов с рациональными коэффициентами, для нахождения одновременных рациональных приближений к действительным числам и для решения задачи целочисленного линейного программирования в фиксированных измерениях.

LLL reduction

Точное определение LLL-уменьшенного выглядят следующим образом : Учитывая базис

$\mathbf {B} =\{\mathbf {b} _{0},\mathbf {b} _{1},\dots ,\mathbf {b} _{n}\},$

определить его ортогональный базис процесса Грама – Шмидта

$\mathbf {B} ^{*}=\{\mathbf {b} _{0}^{*},\mathbf {b} _{1}^{*},\dots ,\mathbf {b} _{n}^{*}\},$

и коэффициенты Грамма-Шмидта

$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}$, for any $1\leq j<i\leq n$.

Тогда базис $B$ есть LLL-уменьшение, если существует параметр $\delta$ принадлежащий интервалу (0.25,1] такой, что имеют место следующий условия:

1. (уменьшенный размер) Для $1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5$. По определению это свойство гарантирует уменьшение длины упорядоченного базиса.
2. (Условие Л. Ласло) k = 1,2,..,n $\colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}$.

Здесь, оценивая величину параметра $\delta$,можно сделать вывод, насколько хорошо базис уменьшается. Большие значения параметра $\delta$ приводят к более сильным сокращениям основания. Первоначально А. Ленстра, Х. Ленстра и Л. Ловас продемонстрировали алгоритм LLL-уменьшения для $\delta ={\frac {3}{4}}$.Обратите внимание, что хотя LLL-уменьшение хорошо определено для $\delta =1$, сложность за полиномиальное время гарантируется только для параметра $\delta$ принадлежит $(0.25,1)$.

Алгоритм LLL вычисляет LLL-уменьшенные базисы. Не существует известного эффективного алгоритма для вычисления базиса, в котором векторы базисов настолько коротки, насколько это возможно, для решёток с размерами, превышающими 4. Однако базис с уменьшенной LLL является настолько коротким, насколько это возможно, в том смысле, что абсолютные границы $c_{i}>1$ таким образом, что первый базисный вектор не более чем в $c_{1}$ раз меньше самого короткого вектора в решётке, второй базисный вектор также находится в пределах $c_{2}$ второго последовательного минимума и так далее.

Алгоритм LLL

Описание данного алгоритма основано на( Hoffstein, Pipher & Silverman 2008 , теорема 6.68).

На вход:

$\triangleright$ базис решётки $b_{0},b_{1},\dots ,b_{n}\in Z^{m}$,

$\triangleright$ параметр $\delta$ , так что ${\frac {1}{4}}<\delta <1$, наиболее частая величина которого, есть $\delta ={\frac {3}{4}}$

Действия:

Выполните Грам-Шмидта, но не производите нормировку: $ortho:=\mathrm {gramSchmidt} (\{b_{0},\dots ,b_{n}\})=\{b_{0}^{*},\dots ,b_{n}^{*}\}$ Определить $\scriptstyle \mu _{i,j}:={\frac {\langle b_{i},b_{j}^{*}\rangle }{\langle b_{j}^{*},b_{j}^{*}\rangle }}$, который всегда должен использовать самые актуальные значения $\scriptstyle b_{i},b_{j}^{*}$. Пусть $k=1$ пока $k\leq n$ делать для j от $k-1$ до 0 делать if $|\mu _{k,j}|>{\frac {1}{2}}$ do $b_{k}=b_{k}-\lfloor \mu _{k,j}\rceil b_{j}$ Обновить "орто" величины и и связанные с ними$\scriptstyle \mu _{i,j}$ по мере необходимости. (Собственный метод состоит в том, чтобы пересчитывать всегда $\scriptstyle ortho:=\mathrm {gramSchmidt} (\{b_{0},\dots ,b_{n}\})=\{b_{0}^{*},\dots ,b_{n}^{*}\}$ при любых изменениях $\scriptstyle b_{i}$ changes.) конец если конец для если $\langle b_{k}^{*},b_{k}^{*}\rangle \geq (\delta -(\mu _{k,k-1})^{2})\langle b_{k-1}^{*},b_{k-1}^{*}\rangle$ тогда $k=k+1$ иначе Поменять местами $\scriptstyle b_{k}$ и $\scriptstyle b_{k-1}$. Обновить "орто" величины и связанные с ними $\scriptstyle \mu _{i,j}$по мере необходимосит. $k=\max(k-1,1)$ конец если конец пока

На выход: LLL уменьшенный базис $b_{0},b_{1},\dots ,b_{n}$

Свойства LLL-уменьшенного базиса

Пусть $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\}$ является $\delta$-LLL-уменьшенным базисом в решётке ${\mathcal {L}}$.Из определения LLL-уменьшенного базиса мы можем получить несколько других полезных свойств о{\ displaystyle \ mathbf {B}} $\mathbf {B}$.

1. Первый вектор в базе не может быть намного больше самого короткого ненулевого вектора :{\ displaystyle || \ mathbf {b} _ {1} || \ leq (2 / ({\ sqrt {4 \ delta -1}})) ^ {n-1} \ cdot \ lambda _ {1} ( {\ mathcal {L}})}: $||\mathbf {b} _{1}||\leq (2/({\sqrt {4\delta -1}}))^{n-1}\cdot \lambda _{1}({\mathcal {L}})$. В частности, для $\delta =3/4$, это даёт$||\mathbf {b} _{1}||\leq 2^{(n-1)/2}\cdot \lambda _{1}({\mathcal {L}})$.
2. Первый вектор в базисе также ограничен определителем решётки: $||\mathbf {b} _{1}||\leq (2/({\sqrt {4\delta -1}}))^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}$. In particular, for $\delta =3/4$, в частности для $||\mathbf {b} _{1}||\leq 2^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}$.
3. Произведение норм векторов в базисе не может быть намного больше, чем определитель решетки: пусть$\delta =3/4$, тогда $\prod _{i=1}^{n}||\mathbf {b} _{i}||\leq 2^{n(n-1)/4}\cdot \det({\mathcal {L}})$.

Пример

Ниже приведён пример из W. Bosma.

На вход:

Пусть дан базис решётки $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in Z^{3}$,с заданными столбцами

${\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}$

Тогда по алгоритму LLL получаем следующее:

1. $b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix}},B_{1}=\langle b_{1}^{*},b_{1}^{*}\rangle ={\begin{bmatrix}1\\1\\1\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}=3$
2. Для $i=2$ делать:
   1. Для $j=1$ положить $\mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}-1\\0\\2\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {1}{3}}\left(<{\frac {1}{2}}\right)$ а так же $b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}-1\\0\\2\end{bmatrix}}-{\frac {1}{3}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}.$
   2. $B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}{\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}={\frac {14}{3}}.$
3. $\mathbf {k} :=2$
4. Здесь шаг 4 алгоритма LLL пропускается, поскольку свойство уменьшенного размера выполняется для $\mu _{2,1}$
5. Пока $k\leq 3$ делать
   1. Уменьшить длину $b_{3}$, не забывая корректировать при этом $\mu _{3,1}$ и $\mu _{3,2}$ согласно подпрограмме сокращения в шаге 4: для $\mid \mu _{3,1}\mid >{\frac {1}{2}}$ ВЫПОЛНИТЬ подпрограмму сокращения RED(3,1):
      1. $r=\lfloor 0.5+\mu _{3,l}\rfloor =5$ а также $b_{3}=b_{3}-5b_{1}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}5\\5\\5\end{bmatrix}}={\begin{bmatrix}-2\\0\\1\end{bmatrix}}$
      2. $\mu _{3,1}=\mu _{3,l}-r\mu _{1,1}={\frac {-1}{3}}\left(<{\frac {1}{2}}\right)$
      3. Положить $\mu _{3,1}=\mu _{3,1}-r={\frac {14}{3}}-5={\frac {-1}{3}}$

      Для $\mid \mu _{3,2}\mid >{\frac {1}{2}}$ ВЫПОЛНИТЬ подпрограмму сокращения RED(3,2):

      1. $r=\lfloor 0.5+\mu _{3,2}\rfloor =1$ and $b_{3}=b_{3}-b_{2}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}-1\\0\\2\end{bmatrix}}={\begin{bmatrix}4\\5\\4\end{bmatrix}}$
      2. Положить $\mu _{3,2}=\mu _{3,2}-r\mu _{2,2}={\frac {13}{14}}-1={\frac {-1}{14}}$
      3. $\mu _{3,2}=\mu _{3,2}-1={\frac {-1}{14}}\left(<{\frac {1}{2}}\right)$
   2. Если $B_{3}<\left({\frac {3}{4}}-\mu _{3,2}^{2}\right)B_{2}$, то
      1. Заменить $b_{3}$ и $b_{2}$
      2. $k:=2$

Применить SWAP, продолжить алгоритм с базой решетки, которая задается столбцами

${\begin{bmatrix}1&4&-1\\1&5&0\\1&4&2\end{bmatrix}}$

Реализовать алгоритм шагов снова.

1. $b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix}},B_{1}=3$
2. $\mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}4\\5\\4\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {13}{3}}\left(>{\frac {1}{2}}\right)$
3. $b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\frac {13}{3}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}{\frac {-1}{3}}\\{\frac {2}{3}}\\{\frac {-1}{3}}\end{bmatrix}}$.
4. $B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\frac {2}{3}}$.
5. Для $\mid \mu _{2,1}\mid >{\frac {1}{2}}$ ВЫПОЛНИТЬ подпрограмму сокращения RED(2,1):
   1. $r=\lfloor 0.5+\mu _{2,l}\rfloor =4$ and $b_{2}=b_{2}-4b_{1}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\begin{bmatrix}4\\4\\4\end{bmatrix}}={\begin{bmatrix}0\\1\\0\end{bmatrix}}$
   2. Положить $\mu _{2,1}=\mu _{2,1}-4\mu _{1,1}={\frac {13}{3}}-4={\frac {1}{3}}\left(<{\frac {1}{2}}\right)$
6. Если $B_{2}<\left({\frac {3}{4}}-\mu _{2,1}^{2}\right)B_{1}$, то
7. Заменить $b_{2}$ и $b_{1}$

ВЫХОД: LLL уменьшенный базис

${\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}}$

Использование алгоритма LLL

Алгоритм LLL нашел множество других применений в алгоритмах обнаружения MIMO и криптоанализе схем шифрования с открытым ключом : криптосистемы ранцев , RSA с конкретными настройками, NTRUEncrypt и так далее. Алгоритм может быть использован для поиска целочисленных решений многих задач.

В частности, алгоритм LLL образует ядро одного из алгоритмов целочисленных отношений . Например, если считается, что r = 1.618034 является (слегка округленным) корнем неизвестного квадратного уравнения с целыми коэффициентами, можно применить LLL-сокращение к решетке в $R^{4}$ натянутый на $[1,0,0,10000r^{2}],[0,1,0,10000r],$ и $[0,0,1,10000]$. Первый вектор в сокращенном базисе будет представлять собой целочисленную линейную комбинацию этих трех, поэтому обязательно имеет вид $[a,b,c,10000(ar^{2}+br+c)]$; но такой вектор «короткий», только если a, b, c малы и $ar^{2}+br+c$ ещё меньше. Таким образом, первые три записи этого короткого вектора, вероятно, будут коэффициентами целочисленного квадратичного полинома, у которого r является корнем. В этом примере алгоритм LLL находит самый короткий вектор как [1, -1, -1, 0.00025], действительно $x^{2}-x-1$ имеет корень, равный золотому сечению , 1.6180339887....

Другие области применения алгоритма LLL

LLL применятеся в

• Arageli как функция lll_reduction_int
• fpLLL как отдельная реализация
• GAP как функция LLLReducedBasis
• Macaulay2 как функция LLL в пакете LLLBases
• Magma как функции LLL and LLLGram (используя грамм-матрицу)
• Maple как функция IntegerRelations[LLL]
• Mathematicaкак функция LatticeReduce
• Number Theory Library (NTL) как функцияLLL
• PARI/GP как функцияqflll
• Pymatgen как функция analysis.get_lll_reduced_lattice
• SageMath как метод LLL driven by fpLLL and NTL

См. также

• Coppersmith method

Ссылки

• Napias, Huguette A generalization of the LLL algorithm over euclidean rings or orders (англ.) // J. The. Nombr. Bordeaux : journal. — 1996. — Vol. 8. — С. 387—396. — DOI:10.5802/jtnb.176
• Cohen, Henri A course in computational algebraic number theory. — Springer, 2000. — Т. 138. — (GTM). — ISBN 3-540-55640-0.
• Borwein, Peter^[en] Computational Excursions in Analysis and Number Theory. — 2002. — ISBN 0-387-95444-9.
• Luk, Franklin T.; Qiao, Sanzheng A pivoted LLL algorithm (неопр.) // Lin. Alg. Appl.. — 2011. — Vol. 434. — № 11. — С. 2296—2307. — DOI:10.1016/j.laa.2010.04.003
• Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. An Introduction to Mathematical Cryptography. — Springer, 2008. — ISBN 978-0-387-77993-5.