격자 문제 SVP를 2^{0.6039n} 시간에 해결하는 알고리즘 등장

Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-Point Hessian

n차원 격자 L에 대한 최단 벡터 문제(SVP)를 고전적으로 2^{0.6039n+o(n)} 시간, 양자적으로 2^{0.5411n+o(n)} 시간에 해결하는 무작위 알고리즘을 제시한다. 공간 복잡도는 2^{0.5n+o(n)}으로, 기존 최고 알고리즘(Aggarwal et al., STOC'15)의 2^{n+o(n)} 시간 및 공간 복잡도를 크게 개선했다. 알고리즘은 주기적 가우시안 함수의 헤시안(Hessian)이 반 최단 벡터에서 갖는 고유벡터 성질을 활용하며, 무작위 부분격자 코셋과 다양한 샘플링 기법으로 최적화했다.