Lattice and SVP, CVP

Lattice

Definition (Lattice). An $n-dimensional \ lattice \ \mathcal{L}$ is a discrete, (additive) subgroup of $\mathbb{R}^n$.

격자(Lattice)는 선형 독립인 벡터 $\lbrace b_1, b_2, \cdots, b_m \vert b_i \in \mathbb{R}^n\rbrace$로 이루어진 basis $B$로 표현할 수 있다. basis를 구성하는 벡터의 수 $m$을 Lattice의 $rank$라 하고, 우리는 rank와 basis의 dimension이 동일한($n=m$) $full-rank$인 케이스를 주로 살펴볼 것이다. 격자는 이러한 basis의 integer linear combination들의 집합이다. 이제 부터 basis vector는 행렬의 행(row)로 표현할 것이다.

\[\mathcal{L} = \mathcal{L}(B) = \lbrace \sum_{i=1}^m a_ib_i \vert a_i \in \mathbb{Z} \rbrace\]

아래 그림은 2차원 Lattice 예시이다. Lattice 상의 모든 Lattice Point들은 basis의 linear combination으로 구해질 수 있다.

그림을 보면 Lattice의 기저(basis)는 유일하지 않음을 알 수 있다. 위처럼 두 개의 다른 basis는 돌일한 Lattice를 생성한다. Lattice는 기본적으로 무한한 basis들을 가질 수 있지만 이 중에는 특정한 문제해결에 좋은 basis가 존재한다.

그렇다면 왜 서로 다른 basis가 같은 Lattice를 만드는지, 이러한 Lattice의 basis가 되기위한 조건은 무엇인지 알아보자.

Definition (Fundamental Parallelepiped). Let $B=\lbrace b_1, b_2, \cdots, b_m\rbrace$ be a basis. The $fundamental \ parallelepiped$ of $B$ is defined as

\[\mathcal{P} = \lbrace \sum_{i=1}^m a_i b_i \vert a_i \in [0,1) \rbrace\]

위 그림은 basis의 lattice와 그 basis의 fundamental parallelepiped를 보여준다. 앞서 정의의 $a_i \in [0,1)$에서 알 수 있듯이 fundamental parallelepiped의 영역이 half-open이기 때문에 non-zero lattice points를 포함하지 않는다. 이는 매우 중요한데, Lattice의 basis들의 기하학적 특성은 fundamental parallelepiped가 Lattice의 non-zero lattice points 포함해서는 안된다는 것이다. 즉 $B$가 Lattice $\mathcal{L}$의 basis라 한다면 $\mathcal{P}(B) \cap \mathcal{L} = \lbrace 0 \rbrace$를 만족해야 한다.

왼쪽을 보면 basis의 fundamental parallelepiped가 non-zero lattice point를 포함하고 있기 때문에 격자의 basis가 될 수 없다. 이유는 매우 간단한데, non-zero lattice point를 포함하게 되면 해당 점을 basis의 integer linear combination으로 표현할 수 없게 되기 때문이다. 다른 말로 오른쪽 그림과 같이 만약 fundamental parallelepiped가 오직 zero vector만 포함한다면, $\mathbb{R}^n$ 상에서 각각의 parallelepiped들은 정확히 하나의 lattice point만을 포함하게 되며 Lattice의 basis가 된다.

다시 돌아와서 이처럼 non-zero lattice point를 포함하지 않는 basis의 종류는 무한히 많을 수 있다. 그리고 이러한 조건을 만족하는 각각의 basis들은 서로 다른 fundamental parallelepiped를 갖지만, 같은 Lattice를 만들어낸다. 여기서 중요한 점은 이러한 basis들의 fundamental parallelepiped의 $volume$은 모두 같다는 것이다. 이 $volume$을 Lattice의 $determinant$라 한다.

Definition (Determinant). Let $B$ be a basis for the full-rank lattice $\mathcal{L} = \mathcal{L}(B)$. The Determinant of $\mathcal{L}$, denoted by $\det(\mathcal{L})$is the n-dimensional volume of $\mathcal{P}(B)$.

\[\det(\mathcal{L}) = vol(\mathcal{P}(B)) = \vert \det(B) \vert\]

왜 서로 다른 basis의 fundamental parallelepiped의 determinant가 같은 값을 갖는지 살펴보기 전에 Lattice 기저들의 대수적 특징을 살펴보자.

full-rank Lattice의 두 개의 basis $B = \lbrace b_1, \cdots, b_n \rbrace$와 $B^{\prime} = \lbrace b_1^{\prime}, \cdots, b_n^{\prime} \rbrace$가 있다고 하자. 각각의 vector $b_1^{\prime}, \cdots, b_n^{\prime}$는 Lattice에 속해있으므로, basis vector인 $b_1, \cdots, b_n$의 integer linear combinations으로 다음과 같이 나타낼 수 있다.

\[\begin{align} b_1^{\prime} &= a_{11}b_1 + \cdots + a_{1n}b_n \\ &\vdots \\ b_n^{\prime} &= a_{n1}b_1 + \cdots + a_{nn}b_n \end{align}\]

이를 행렬 곱으로 표현하면 $B^{\prime} = AB$가 되고 $A$는 system의 integer coefficient matrix이다. 반대로 $b_i$역시 $b_i^{\prime}$의 integer linear combinations으로 표현될 수 있고 이는 $B=A^{-1}B^{\prime}$이다. $A^{-1}$역시 integer matrix이므로 다음이 성립한다.

\[\det(AA^{-1}) = \det(A)\det(A^{-1}) = \det(I) = 1\]

$A$와 $A^{-1}$가 matrix of integers이므로 $\det(A)$와 $\det(A^{-1})$의 결과는 integer이다. 따라서 integer끼리의 곱이 1이므로 $\vert \det(A) \vert = 1$임을 알 수 있다.

다시 돌아와서 $\vert \det(A) \vert = 1$인 integer matrix $A$에 대해 $B=AB^{\prime}$를 만족한다. 이 경우 $B$의 각 vector는 $B^{\prime}$의 vector들의 integer linear combination으로 표현이 된다. 따라서 $\mathcal{L}(B) \subseteq \mathcal{L}(B^{\prime})$이다. 또한 같은 argument에 대해 $B^{\prime} = A^{-1}B$도 성립한다. 따라서 $\mathcal{L}(B^{\prime}) \subseteq \mathcal{L}(B)$이다. 그러므로 $\mathcal{L}(B)=\mathcal{L}(B^{\prime})$가 성립하고 이는 다음의 정리로 이어진다.

Theorem. Let $B$ and $B^{\prime}$ be bases. Then, $\mathcal{L}(B)=\mathcal{L}(B^{\prime})$ if and only if $B=UB^{\prime}$ for some integer matrix $U$ with $\vert \det(U) \vert = 1$.

lattice $\mathcal{L}$의 basis로 $B$와 $B^{\prime}$이 있다고 하자. $B=UB^{\prime}$이므로 $\det(B) = \det(UB^{\prime}) = \det(U) \det(B^{\prime}) = \det(B^{\prime})$이다. 이제 위 정리를 통해 우리는 Lattice의 determinant가 불변함을 알 수 있다.

lattice의 또 다른 중요한 불변값은 계승 최소값(successive minima)이다. successive minima는 격자 $\mathcal{L}$안에서 선형독립인 $i$개의 vector를 찾을 수 있는 최소 반지름 $r$을 의미한다. first successive minimum을 보통 $\lambda(\mathcal{L})$ 또는 그냥 $\lambda$로 표현하고 이는 lattice에서 가장 짧은 non-zero vector의 길이와 같다. 일반적으로 rank $n$의 lattice는 $n$개의 successive minima를 갖고, 다음과 같이 정의된다.

Definition (Successive Minima). Let $\mathcal{L}$ be a lattice of rank $n$. For $i \in \lbrace 1, \cdots, n \rbrace$, the $i$ th successive minimum of $\mathcal{L}$, denoted by $\lambda_i(\mathcal{L})$,is the smallest $r$ such that $\mathcal{L}$ has $i$ linearly independent vectors of length at most $r$.

일반적으로 $\lambda_i(\mathcal{L})$는 $i$ linearly independent vectors를 포함하는 origin으로부터의 최소 반지름이라 할 수 있다. 위 그림은 lattice의 first successive minimum을 보여준다.

흥미롭게도 lattice의 successive minima를 구하는 효율적인 알고리즘은 존재하지 않지만 다음 정리를 따르는 upper bound는 존재한다.

Theorem (Minkowski’s First Theorem). Let $\mathcal{L}$ be a full-rank $n$ dimensional lattice. Then

\[\lambda_1(\mathcal{L}) \leq \sqrt{n} \vert \det(\mathcal{L}) \vert^{1/n}\]

first successive minimum은 lattice 내의 vector길이를 판단할 때 기준이 되는 값이기 때문에 중요하게 다뤄진다.

Lattice Problems

이제 몇가지 중요한 $lattice \ problem$들을 다뤄볼 것이다. 정의는 다음과 같다.

Definition (Shortest Vector Problem (SVP)). Given a basis $B$ of a lattice $\mathcal{L}=\mathcal{L}(B)$, find a non-zero lattice vector $v$ that satisfies $\lVert v \rVert = \lambda_1 (\mathcal{L})$.

Definition (Closest Vector Problem (CVP)). Given a basis $B$ of a lattice $\mathcal{L}=\mathcal{L}(B)$, and a target vector $t$ (not necessarily in $\mathcal{L}$), find a lattice vector $v$ that satisfies $\lVert v-t \rVert = \min_{w \in \mathcal{L}} \lVert w-t \rVert$.

이 문제들은 NP-Hard로 알려져 있다. 하지만 이러한 문제들을 특정 파라미터에 대해 효율적으로 풀 수 있는 완화 버전을 만들 수 있고, 암호해독에 더 유용하게 사용할 수 있다. 정의는 다음과 같다.

Definition (Approximate Shortest Vector Problem (SVP ${}_{\gamma}$ )). Given a basis $B$ of a lattice $\mathcal{L}=\mathcal{L}(B)$ and an approximation factor $\gamma$, find a non-zero lattice vector $v$ that satisfies $\lVert v \rVert \leq \gamma \cdot \lambda_1(\mathcal{L})$.

Definition (Approximate Closest Vector Problem (CVP ${}_{\gamma}$ )). Given a basis $B$ of a lattice $\mathcal{L}=\mathcal{L}(B)$, a target vector $t$ and an approximation factor $\gamma$, find a lattice vector $v$ that satisfies $\lVert v-t \rVert \leq \gamma \cdot \min _{w \in \mathcal{L}} \lVert w-t \rVert$.

이 문제를 풀기 위해서는 $lattice \ reduction$을 해야한다. 이는 임의의 lattice basis를 더 나은 basis로 변환하는 과정으로 더 짧고, 수직에 근접한 basis를 찾는 것이 목표다. 다음에는 lattice reduction을 다항시간 안에 근사하여 해결할 수 있는 LLL algorithm에 대해 알아볼 것이다.

Reference

https://eprint.iacr.org/2023/032.pdf