Babai’s Algorithm

Solving CVP

LLL lattice reduction은 결과로 나온 첫 번째 vector를 취함으로써 shortest vector problem의 근사 해를 구할 수 있었다. Lattice reduction은 SVP뿐만 아니라 closest vector problem에도 사용될 수 있다. CVP를 해결하기 위한 대표적인 방법으로 Babai’s Nearest plane Algorithm, Kannan’s Embedding 등이 있다. 이 글에선 Babai’s Nearest Plane Algorithm에 대해 다룰 것이다.

Babai’s Nearest Plane Algorithm

Babai’s nearest plane algorithm은 greedy 알고리즘으로 lattice reduction을 거친 basis $B = \lbrace b_1, \cdots, b_n \rbrace$에서 시작한다. $t$(lattice point가 아니어도 됨)가 target vector라고 할 때, $n$-dim 공간을 두 부분으로 나누는 hyperplane($span(b_1, \cdots, b_{n-1}))$을 첫 $n-1$개의 lattice vector로 설정한다. 이후 $t^{\prime} = t - c_n b_n$을 계산하는데, 여기서 $c_n$은 $c_nb_n$으로 변환된 hyperplane과 target인 $t$와의 거리가 최대한 가깝도록 하는 정수로 $c_n = \lfloor \frac{\langle t, b_n^* \rangle}{\langle b_n^* , b_n^* \rangle} \rceil$ 으로 계산된다. 그리고 이 과정을 나머지 $n-1$개의 lattice vector와 새로운 translated target vecto인 $t^{\prime}$에 대해서도 반복한다. 알고리즘의 최종 결과는 $c_ib_i$의 합으로 나타나는 lattice point로 이 lattice point가 target $t$와 가장 가까운 근사 해가 된다.

위 그림은 지금까지의 Babai’s Nearest Plane Algorithm과정을 two dimensional case로 보여주는 예시이다.

Babai’s Nearest Plane Algorithm의 시간 복잡도는 lattice reduction에 의해 결정된다. 따라서 LLL을 사용하는 경우 babai 알고리즘은 다항시간 내에 실행된다. LLL을 통해 Babai’s algorithm을 사용한다면 CVP ${}_{\gamma}$를 지수적 근사 오차(exponential approximation factor)내에서 해결할 수 있다.

Algorithm Babai’s Nearest Plane Algorithm
 function BABAI(Basis $\lbrace b_1, \cdots, b_n\rbrace$, target vector $t$)
  Perform lattice reduction on $B$
   $b_i^* \gets$ Gram-Schmidt $(b_1, \cdots, b_n)$
   $b \gets t$
  for $i=n$ to $1$ do
    $c_i \gets \lfloor \frac{\langle t, b_i^* \rangle}{\langle b_i^* , b_i^* \rangle} \rceil$
    $b \gets b - c_ib_i$
   return $t-b$

Reference

1. https://eprint.iacr.org/2023/032.pdf
2. https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pdf