Learning with errors (LWE) problem is an well-known problem for lattice cryptography. After Lindner and Peikert suggested an attack using bounded distance decoding (BDD) problem [LP11], it has been studied as one of the most practical ways to solve the LWE problem. We revisit the numerical optimization [GNR10] to optimize the BDD approach with pruned enumeration for solving LWE problem. Numerical minimization also takes the lattice reduction, enumeration radius, and subdimension into consideration.
Learning with errors (LWE) 문제는 격자 기반 암호에서 잘 알려진 문제 중 하나이다. Lindner와 Peikert가 bounded distance decoding (BDD) 문제로의 환원을 통한 공격을 처음 제시한 이후 [LP11], 이 공격은 LWE문제를 가장 효율적으로 푸는 방법 중 하나로 연구가 되었다. 우리는 Gama외 2명이 제시한 pruned enumeration의 최적화를 [GNR10] 다시 살펴보고 LWE문제를 풀기 위한 BDD 공격 방법에 적용시켰다. 수치적 최적화는 격자 축소 알고리즘, enumeration 반경, 그리고 subdimension까지 고려했다.
