Kannan’s Embedding

Kannan’s Embedding

Kannan’s Embedding은 CVP를 푸는 또 다른 방법으로 target vector를 lattice basis로 Embedding하여 CVP를 SVP로 환원한다. lattice basis $B = \lbrace b_1, \cdots, b_n\rbrace$와 target vector $t = (t_1, \cdots, t_n)$가 있다고 하자. CVP의 해가 integers $c=(c_1, \cdots, c_n)$ 이라 하면, target vector를 다음과 같이 표현할 수 있다.

\[\begin{align} t &\approx \sum_{i=1}^n c_i b_i \\ t &= \sum_{i=1}^n c_i b_i + e \end{align}\]

이때 $\lVert e \rVert$는 매우 작다. embedding technique의 아이디어는 short vector인 $e$를 포함하는 $n + 1$ dimensional lattice $L^{\prime}$을 만드는 것이며 basis는 다음과 같이 구성된다.

\[\mathbf{B}^{\prime} = \begin{vmatrix} \mathbf{B} & 0 \\ \mathbf{t} & q \end{vmatrix}\]

$\mathbf{B}^{\prime}$을 풀어서 쓰면 다음과 같다.

\[\mathbf{B} = \begin{bmatrix} b_1 & & & & 0 \\ & b_2 & & & 0 \\ & & \ddots & & \vdots \\ & & & b_n & 0 \\ t_1 & t_2 & \cdots & t_n & q \end{bmatrix} = \begin{bmatrix} \begin{array}{c|c} \mathbf{B} & \begin{array}{c} 0 \\ \vdots \\ 0 \end{array} \\ \hline t_1 \;\; t_2 \;\; \cdots \;\; t_n & q \end{array} \end{bmatrix}\]

이렇게 만들어진 lattice $L^{\prime}$은 $v=(-c_1, \cdots, -c_n, 1)$와의 linear combination을 통해 short vector $(e, q)$를 포함한다.

\[v \mathbf{B}^{\prime} = (-c, 1) \begin{vmatrix} \mathbf{B} & 0 \\ \mathbf{t} & q \end{vmatrix}= (-c_1, \cdots, -c_n, 1) \begin{vmatrix} (b_1, 0) \\ \vdots \\ (b_n, 0) \\ (t, q) \end{vmatrix} = (t - c\mathbf{B}, q) = (e, q)\]

따라서 lattice $L^{\prime}$에 대한 SVP를 해결한다면, $e$를 찾는것이 가능하고 $t-e$를 계산하여 CVP를 해결할 수 있다.

Kannan’s Embedding에서 integer $q$는 embedding factor로 $L^{\prime}$에 대한 LLL이 얼마나 성공적으로 이루어지는가에 영향을 준다. 특히 이후에 나올 lattice attack의 공격 성공률은 Kannan embedding factor에 매우 민감하다. 따라서 $q$는 결과로 나올 $e$의 크기 $\lVert e \rVert$혹은 some norm of $B$ $q = \max_{1 \leq i \leq n} \lVert b_i \rVert$에 맞춰 적절한 값을 택해야 하며, 너무 크거나 작아선 안된다.

만약 Kannan embedding factor가 너무 크다면, submatrix $B$에 LLL reduction을 이미 적용한 상태라고 했을 때, $\mathbf{B}^{\prime}$의 LLL reduction에서 Lovász condition $(\delta - \mu_{i+1, i}^2) \lVert b_i^* \rVert^2 \leq \lVert b_{i+1}^* \rVert^2$ 을 바로 만족해버릴 가능성이 크다. 이렇게 되면 basis vector간 swap이 일어나지 않고, LLL 알고리즘이 빠르게 종료된다. 이 때문에 충분한 size reduction도 이루어지지 않아 success rate가 급격하게 낮아지게 된다. 일반적으로 basis vector swap이 많이 발생해야 size reduction도 많이 수행된다.

반대로 Kannan embedding factor가 너무 작다면, 마지막 행의 Gram–Schmidt norm이 매우 작아진다. 이렇게 되면 row swap이 일어난 뒤에 size reduction $b_ i \gets b_ i - \lfloor \mu_ {i,j} \rceil b_ j$ 을 할 때 target vector $v$의 너무 많은 곱이 다른 basis에 더해질 가능성이 높다. 결국 최종 reduced basis의 모든 vector가 target $v$에 대해 매우 큰 coefficient 갖게 되고 원래 찾으려던 short vector가 reduced basis에 잘 나타나지 않을 가능성이 크다.

이제 실제로 Kannan’s Embedding을 활용해 CVP를 해결하는 예시를 살펴보자. 다음과 같은 basis matrix가 있다고 하자.

\[\mathbf{B} = \begin{vmatrix} 35 & 72 & -100 \\ -10 & 0 & -25 \\ -20 & -279 & 678 \end{vmatrix}\]

CVP의 target vector가 $v=(100, 100, 100)$이라 할 때, Kannan’s Embedding을 적용한 lattice $L^{\prime}$은 다음과 같다. 여기선 Kannan embedding factor를 1로 설정하였다.

\[\mathbf{B}^{\prime} = \begin{vmatrix} 35 & 72 & -100 & 0 \\ -10 & 0 & -25 & 0 \\ -20 & -279 & 678 & 0 \\ 100 & 100 & 100 & 1 \end{vmatrix}\]

lattice $L^{\prime}$에 대해 LLL algorithm을 적용한 reduced basis는 다음과 같다.

\[\begin{vmatrix} 0 & 1 & 0 & 1 \\ 5 & 0 & 1 & 0 \\ 0 & 5 & 1 & -4 \\ 5 & 5 & -21 & -4 \end{vmatrix}\]

first row $(e, q)=(0, 1, 0, 1)$에서 $e=(0, 1, 0)$임을 알 수 있다. 이제 $e$를 얻었으므로 $t-e$를 계산하여 CVP를 해결한다. $v = (100, 100, 100) - (0, 1, 0) = (100, 99, 100)$ 따라서 $(100, 99, 100)$가 CVP의 해이고 이는 lattice 상의 point이다.

마지막으로 CVP(Closest Vector Problem)을 SVP(Shortest Vector Problem)로 바꾸는 Kannan’s Embedding 기법이 왜 정당한지 살펴보자. 여기선 $(e, q)$가 Embedding lattice $L^{\prime}$에서 shortest non-zero vector임을 증명할 것이다.

그전에 참고로 $\lVert e \rVert$는 lattice의 successive minima $\lambda_n$보다 클 수는 있지만, 이러한 경우 embedding technique은 CVP를 해결하는데 좋은 방법이 아니다.

Lemma. Let $\lbrace b_1, \cdots, b_n\rbrace$ be a basis for a lattice $L \subseteq \mathbb{Z}^n$ and denote by $\lambda_1$ the shortest Euclidean length of a non-zero element of $L$. Let $t \in \mathbb{R}^n$ and let $s in L$ be a closest lattice point to $t$. Define $e = t - s$. Suppose that $\lVert e \rVert < \lambda_1/2$ and let $q = \lVert e \rVert$. Then $(e, q)$ is a shortest non-zero vector in the lattice $L^{\prime}$ of the embedding technique.

Proof. 가정에 의해 $\lVert e \rVert < \lambda_1/2$이고, $q = \lVert e \rVert$이다. 우리가 증명하고자 하는 건 embedding lattice $L^{\prime}$에서 $(e, q)$가 shortest non-zero vector라는 것이다.

lattice $L^{\prime}$상의 모든 vector는 다음과 같이 표현이 가능하다.

\[l_{n+1}(e, q) + \sum_{i=1}^n l_i (b_i, 0)\]

1. $l_{n+1}=0$

$L^{\prime}$의 모든 vector는 $\sum l_i b_i$형태로 lattice $L$의 벡터와 동일하므로 norm은 $\geq \lambda_1$이다. 하지만 $(e, q)$를 따져보면,

\[\lVert (e, q) \rVert^2 = \lVert e \rVert^2 + q^2 = 2q^2 < 2 \cdot \frac{\lambda_1^2}{4}\]

이므로 vector $(e, \pm q)$의 최대 norm은 $\lambda_1/ \sqrt{2}$이다. $s$가 $t$의 closest vector이므로 모든 $x \in L$에 대해 $\lVert e \rVert \leq \lVert e + x \rVert$이다. 따라서 모든 다른 vector $(u, q) \in L^{\prime}$은 $(e, q)$보다 클 수밖에 없다.

2. $\vert l_{n+1} \vert \geq 2$

\[\lVert (u, l_{n+1} q) \rVert^2 \geq \lVert (0, l_{n+1} q) \rVert^2 \geq (2q)^2\]

이므로 $\lVert (u, l_{n+1} q) \rVert \geq 2 \lVert (e, q) \rVert$이다.

결론적으로 어떤 $(u, l_{n+1} q) \in L^{\prime}$도 $(e, q)$보다 짧을 수 없다. 따라서 $(e, q)$는 $L^{\prime}$의 shortest non-zero vector이다.

Reference

1. https://tches.iacr.org/index.php/TCHES/article/view/9302/8868
2. https://crypto.stackexchange.com/questions/88854/understanding-unique-svp-and-kannans-embedding
3. https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pdf
4. https://eprint.iacr.org/2023/032.pdf