LLL | Lattice Basis Reduction

Crypto

全名是 Lenstra–Lenstra–Lovász Lattice Basis Reduction Algorithm

該演算法是從給定的這些基底中，找出一個最短且、最正交的向量

LLL 通過減去基本向量的整數倍來減少非基本向量，找出合理的正交基底的有效方法

確定該向量是否成為下一個基本向量，以及是否應替換緊接在其之前的基本向量。

取決於是否滿足 Lovasz condition

計算流程：

  1. Reduction step：

    b⃗1′=b⃗1\vec{b}_{1}^{\prime}=\vec{b}_{1}
    b⃗i′=b⃗i−∑j<ici,jb⃗j′,  ci,j=⌊⟨b⃗i,b⃗j′⟩⟨b⃗j′,b⃗j′⟩⌉\vec{b}_{i}^{\prime}=\vec{b}_{i}-\sum_{j<i} c_{i, j} \vec{b}_{j}^{\prime} \quad,\ \ c_{i, j}=\left\lfloor\frac{\left\langle\vec{b}_{i}, \vec{b}_{j}^{\prime}\right\rangle}{\left\langle\vec{b}_{j}^{\prime}, \vec{b}_{j}^{\prime}\right\rangle} \right\rceil

    與 Gram-Schmidt 不同在於，這裡的正射影取的是四捨五入後的結果。


  1. Swap step：

    如果 ∥b⃗i∥>∥b⃗i+1∥\|\vec{b}_{i}\|>\|\vec{b}_{i+1}\|, 那就把兩個交換 b⃗i⇔b⃗i+1\vec{b}_{i} \Leftrightarrow \vec{b}_{i+1}

    [πi(x⃗)=∑j=in⟨x⃗,b⃗j∗⟩⟨b⃗j∗,b⃗j∗⟩b⃗j∗,   14<δ<1]\left[\pi_{i}(\vec{x})=\sum_{j=i}^{n} \frac{\left\langle\vec{x}, \vec{b}_{j}^{*}\right\rangle}{\left\langle\vec{b}_{j}^{*}, \vec{b}_{j}^{*}\right\rangle} \vec{b}_{j}^{*},\ \ \ \frac{1}{4} < \delta < 1\right]

    以確保所有的基底 bib_i 皆滿足 δ∥πi(b⃗i)∥2≤∥πi(b⃗i+1)∥2\delta\|\pi_{i} (\vec{b}_{i} )\|^{2} \leq\|\pi_{i} ( \vec{b}_{i+1} ) \|^{2}


  1. 如果 (2)(2) 的條件有觸發, 那就回到 (1)(1) 重新來過

計算結束後，也就代表著原本的 Lattice (B={b⃗1…b⃗n}∈Rm×n)(B = \{\vec{b}_{1} \ldots \vec{b}_{n}\} \in \mathbb{R}^{m \times n}) 的基底的長度已經減小了，並滿足以下不等式：

  1. ∥c(i,j)∥≤12\|c_{(i, j)}\| \leq \frac{1}{2} for all i>ji>j

  2. 所有的基底 bib_i 皆滿足 δ∥πi(b⃗i)∥2≤∥πi(b⃗i+1)∥2\delta\|\pi_{i} (\vec{b}_{i} )\|^{2} \leq\|\pi_{i} ( \vec{b}_{i+1} ) \|^{2}

    δ∥πi(b⃗i)∥2≤∥πi(b⃗i+1)∥2\delta\|\pi_{i} (\vec{b}_{i} )\|^{2} \leq\|\pi_{i} ( \vec{b}_{i+1} ) \|^{2}

    ⇒δ∥b⃗i∗∥2≤∥b⃗i+1∗+c(i+1,i)∗b⃗i∗∥2\Rightarrow \delta\|\vec{b}_{i}^{*}\|^{2} \leq\|\vec{b}_{i+1}^{*}+c_{(i+1, i)} * \vec{b}_{i}^{*}\|^{2}

    ⇒             =∥b⃗i+1∗∥2+∥c(i+1,i)b⃗i∗∥2\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ = \left\|\vec{b}_{i+1}^{*}\right\|^{2}+\left\|c_{(i_{+1}, i)}\vec{b}_{i}^{*}\right\|^{2}

    ⇒             =∥b⃗i+1∗∥2+(c(i+1,i))2∥b⃗i∗∥2\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ = \left\|\vec{b}_{i+1}^{*}\right\|^{2}+\left(c_{(i+1, i)}\right)^{2}\left\|\vec{b}_{i}^{*}\right\|^{2}

    ⇒             ≤∥b⃗i+1∗∥2+14∥b⃗i∗∥2\Rightarrow\ \ \ \ \ \ \ \ \ \ \ \ \ \leq \left\|\vec{b}_{i+1}^{*}\right\|^{2}+\frac{1}{4}\left\|\vec{b}_{i}^{*}\right\|^{2}

    移項後：

    (δ−14)∥b⃗i∗∥2≤∥b⃗i+1∗∥2\left(\delta-\frac{1}{4}\right)\left\|\vec{b}_{i}^{*}\right\|^{2} \leq \left\|\vec{b}_{i+1}^{*}\right\|^{2}

    ⇒ ∥b⃗i∗∥2≤1(δ−14)∥b⃗i+1∗∥2\Rightarrow\ \left\|\vec{b}_{i}^{*}\right\|^{2} \leq \frac{1}{\left(\delta-\frac{1}{4}\right)}\left\|\vec{b}_{i+1}^{*}\right\|^{2}

    故任一組合  [b(i,j), i≥j ]\ [b_{(i,j)},\ i \geq j\ ], 且令   α=1(δ−14)\ \ \alpha = \frac{1}{\left(\delta-\frac{1}{4}\right)}

    ∥b⃗j∗∥2≤αi−j∥b⃗i∗∥2\left\|\vec{b}_{j}^{*}\right\|^{2} \leq \alpha^{i-j}\left\|\vec{b}_{i}^{*}\right\|^{2}

    Lower bar 的設置也意味著 ∥b1∥\left\|b1\right\| 最多也只會是該 Lattice 中最短向量的 αn−12\alpha^{\frac{n-1}{2}} 倍，故可作為限制，以找出目標值。

演算法：wikipedia
Code : SageMath 已經有實作了可以直接拿來用 xD

  • 版權聲明： 所有文章除特特別聲明外，均採用 CC BY 4.0許可協議。