Analysis of the Evaluation Attack on PLWE Problem

Abstract

Ring-learning with errors(RLWE) 문제는 LWE 문제의 변형으로 일반적인 유클리드 공간과 정수 격자 위에서 정의되는 LWE 문제와 달리 수체와 그 정수환 위에서 정의되는 문제이다. LWE 문제는 전통적인 격자 문제로 환원이 가능하며 따라서 그 어려움을 보장 받고 있다. RLWE 문제 또한 원분체 위에서 정의된 경우 그 원분체 위에서의 격자 문제로 환원이 가능하나 그 어려움이 증명되었다고는 할 수 없다. RLWE 문제는 LWE 기반 암호의 비효율성을 해결하기 위한 방안으로 다양한 분야에서 사용되고 있다. Poly-LWE(PLWE) 문제는 RLWE 문제와 유사하나 오차 분포를 어떻게 선택하느냐에 차이가 있으며, 특정한 원분체의 경우 이 두 문제는 동등하다.<br/> <br/> 한 편으로 다른 여러 수체 위에서 정의된 RLWE 및 PLWE 문제는 어려울 것인가에 대한 물음이 자연스럽게 생길 수 있으며 최근 몇 년 사이에 Eisentr{\"a}ger 등과 Elias 등에 의해 특정한 경우의 수체에 대하여 RLWE, PLWE 문제의 공격이 가능함이 알려지게 되었다. 한편 Castryck 등은 이러한 공격을 함수값 공격이라 부르고, 앞에서 제시된 수체의 경우 PLWE 문제에서 RLWE 문제로 변환할 때 함수값 공격보다 더 간단한 공격이 존재함을 보였다. 이후 Chen 등은 Castryck 등의 공격에 약하지 않으면서 함수값 공격이 가능한 다른 약한 수체들을 제시하였다.<br/> <br/> 본 연구는 함수값 공격을 분석하고, 그 공격에 취약한 수체들이 추가로 존재하는지 알아보고자 시작되었다. 우선 분석을 통하여 Elias 등이 제시한 공격성공 조건에 대해 오류를 찾아내었다. PLWE 문제는 그 몫환을 정의하는 다항식의 동반행렬과 계수 벡터를 이용하여 나타낼 수 있으며, 몫환의 원소가 특정한 일차식을 인수로 가질 때 이를 이용하여 쌍대격자 공격을 적용할 수 있다. 우리는 이러한 관찰로부터 함수값 공격과 유사한 다른 방법을 찾았다. 함수값 공격은 쌍대격자 공격과 유사성을 갖고 있으며, 이로부터 함수값 공격은 쌍대격자 공격의 응용으로 볼 수 있다. 또한 이러한 접근을 통해 기존의 함수값 공격 알고리즘을 약간 수정하였으며 위에서 지적한 함수값 공격의 성공 조건을 다시 구할 수 있었다. 그 공격복잡도는 기존의 것과 크게 다르지 않다.