Gauss Sieve 반복 동작에서의 비효율성 개선 (Improvement in Inefficient Repetition of Gauss Sieve)

서지정보

· 발행기관 : 한국정보보호학회
· 수록지 정보 : 정보보호학회논문지 / 33권 / 2호 / 223 ~ 233페이지
· 저자명 : 천병호, 이창원, 전찬호, 홍석희, 김수리

초록

Gauss Sieve는 격자 기반 문제 중 하나인 SVP를 풀기 위한 알고리즘으로 지수 시간 및 공간 복잡도를 필요로 한다. 알고리즘의 종료 조건은 공간 복잡도와 관련이 있는 리스트의 크기 및 충돌 횟수에 의해 결정된다. 여기서 충돌이란 샘플링 된 벡터에 대한 축소 연산 뒤 이미 리스트에 존재하는 벡터와 동일한 벡터가 되는 상황을 의미하며 일정 횟수 이상의 충돌이 발생할 경우 알고리즘은 종료된다. 기존 알고리즘으로부터 제시된 공간 복잡도를 기준으로 실제 실행 결과를 확인하였을 때, 가장 짧은 벡터를 발견한 이후에도 불필요한 연산이 지속되는 것을 확인하였다. 이는 기존의 종료 조건이 필요 이상으로 크게 설정되었음을 의미한다. 따라서 본 논문에서는 불필요한 연산이 반복되는 지점을 파악한 뒤 기존에 필요로 하는 연산의 횟수에 대한 최적화를 진행한다. 종료 조건이 되는 충돌의 임계값과 샘플 벡터가 생성되는 분포를 조정하는 방식으로 실험을 진행하였으며 실험 결과 가장 큰 비중을 차지하는 축소 연산은 62.6% 감소하였으며 이에 따른 공간 및 시간 복잡도는 각각 4.3%, 1.6% 감소하였다.

영어초록

Gauss Sieve is an algorithm for solving SVP and requires exponential time and space complexity. The termination condition of the Sieve is determined by the size of the constructed list and the number of collisions related to space complexity. The term ‘collision’ refers to the state in which the sampled vector is reduced to the vector that is already in the list. if collisions occur more than a certain number of times, the algorithm terminates. When executing previous algorithms, we noticed that unnecessary operations continued even after the shortest vector was found. This means that the existing termination condition is set larger than necessary. In this paper, after identifying the point where unnecessary operations are repeated, optimization is performed on the number of operations required. The tests are conducted by adjusting the threshold of the collision that becomes the termination condition and the distribution in which the sample vector is generated. According to the experiments, the operation that occupies the largest proportion decreased by 62.6%. The space and time complexity also decreased by 4.3 and 1.6%, respectively.

참고자료

· 없음