Deterministic and Efficient Ideal Arithmetic via Two-Element Representations

기술 요약: 두 요소 표현을 통한 결정론적이고 효율적인 아이디얼 산술

문제 정의
수론 및 양자 내성 암호(특히 Ring Learning-With-Errors, 또는 RLWE)에서 효율적인 아이디얼 산술은 필수적이다. 임의의 분수 아이디얼(fractional ideal)이 수체 $K$의 정수 환 $\mathcal{O}_K$ 위에서 두 개의 요소에 의해 생성될 수 있다는 것은 이미 알려진 이론적 사실이지만, 그러한 표현을 찾는 것은 계산적으로 매우 까다롭다. 기존 알고리즘들은 무작위성을 띠거나, 아이디얼 노름(norm) 또는 정의 다항식의 판별식에 대한 값비싼 소인수분해에 의존하기 때문에 암호학적 크기의 입력값에 대해서는 비실용적이다.

본 논문이 다루는 구체적인 문제는 다음과 같다: $\mathbb{Z}/N\mathbb{Z}$ 상의 다항식에 대한 생성 집합(종종 $\mathbb{Z}$-기저 또는 튜플 $(N, a(\alpha), b(\alpha))$에서 유도됨, 여기서 $N$은 큰 합성 정수임)으로 정의된 $\mathcal{O}_K$의 아이디얼이 주어졌을 때, 해당 아이디얼이 $M\mathcal{O}_K + c(\alpha)\mathcal{O}_K$에 의해 생성되도록 하는 두 요소 $M, c(\alpha)$를 찾는 것이다. 저자들은 $N$이 작은 소인수가 없는 커다란 합성수인 어려운 경우에 집중하는데, 이 경우 인수분해는 난해하다.

본 논문이 해결하고자 하는 구체적인 문제는: 주어진 아이디얼이 $M\mathcal{O}_K + c(\alpha)\mathcal{O}_K$에 의해 생성된다면, 두 요소 $M, c(\alpha)$를 찾는 것이다.

방법론
본 논문은 소수 아이디얼 인수분해와 무작위성에 의존하지 않는 결정론적 다항 시간 알고리즘을 제안한다. 이 접근 방식은 $\mathbb{Z}/N\mathbb{Z}$ 상의 다항식 산술과 일반화된 데데킨트 판정법(Dedekind criterion)에 크게 의존하며 세 단계로 나뉜다.

1. 1단계: 아이디얼 인수분해 및 정규화
   알고리즘은 $\mathbb{Z}/N\mathbb{Z}$ 상의 다항식에 대해 유클리드 스타일의 알고리즘을 사용하여 입력 아이디얼 $(N, a(\alpha), b(\alpha))$을 축약하려고 시도한다.

• 만약 선행 계수들이 $\mathbb{Z}/N\mathbb{Z}$의 단원(unit)이라면, 알고리즘은 다항식의 최대공약수(GCD)를 계산하여 아이디얼을 두 요소 형태인 $(N, c(\alpha))$로 축약한다.
• 만약 비자명한 영인자(zero divisor)가 발견되면($N$이 합성수임을 나타냄), 알고리즘은 $N$을 서로소인 성분들로 인수분해하고 결과로 나온 아이디얼들을 재귀적으로 처리한다.
• $N$이 완전 거듭제곱($N = N_0^e$)인 경우, 알고리즘은 유클리드 알고리즘을 실행하여 $(N^e, a_1(x), N d_1(x), \dots)$ 형태의 아이디얼을 생성하는 퇴화된 사례를 처리한다. 그 후, $a_1(x)$가 모듈로 $N$에 대해 $f(x)$의 인수가 되도록 정의 다항식 $f(x)$를 활용한다.
• 이 단계의 출력은 "특수한 형태"의 아이디얼들의 곱이다: 즉, 단순한 두 요소 아이디얼 $(N_i, a_i(\alpha))$이거나, $N$의 거듭제곱과 여러 생성자를 포함하는 특정 구조를 가진 아이디얼들이다.

2. 2단계: 특수 형태 처리 및 곱셈
   이 단계는 $N$이 완전 거듭제곱이 아닌 경우의 아이디얼 형태인 $(N^e, a(\alpha), N I)$를 다룬다.

• 일반화된 데데킨트 판정법: 핵심적인 기술적 기여는 일반화된 데데킨트 판정법(보조정리 5 및 정리 3)이다. 이를 통해 알고리즘은 $(\tilde{a}(x), \tilde{f}_1(x), N) = 1$인 공약성 조건을 만족하면서 $f(x) = \tilde{f}_1(x)N + \tilde{a}(x)A(x)$를 만족하는 단항식 $\tilde{a}(x)$를 찾을 수 있다.
• 아이디얼 나눗셈 및 곱셈: 이 형태를 사용하여, 알고리즘은 $\tilde{a}(\alpha)\bar{a}(\alpha) \equiv N \pmod{N^s}$를 만족하는 원소 $\bar{a}(\alpha)$를 구성한다. 이 성질은 두 요소 표현에서의 효율적인 아이디얼 나눗셈과 곱셈을 가능하게 한다. 구체적으로, 생성자들이 일반화된 데데킨트 조건을 만족할 경우 $(N, \tilde{a}_1(\alpha))(N, \tilde{a}_2(\alpha)) = (N^2, \tilde{a}_1(\alpha)\tilde{a}_2(\alpha))$임을 증명한다.
• 알고리즘은 복잡한 아이디얼을 단순한 두 요소 아이디얼 $(N_i, \tilde{a}_i(\alpha))$들의 곱으로 반복적으로 축약한다.

3. 3단계: 중국인의 나머지 정리를 통한 재조립
   입력 아이디얼이 서로소인 두 요소 아이디얼 $(N_i, a_i(\alpha))$들의 곱으로 인수분해되면, 알고리즘은 중국인의 나머지 정리(보조정리 2)를 사용하여 이들을 하나의 두 요소 표현 $(M, c(\alpha))$으로 다시 곱하여 결합한다.

주요 기여

• 결정론적 다항 시간 알고리즘: 본 논문은 노름의 소인수분해를 요구하지 않고 모노제닉 필드(monogenic fields, 그리고 인덱스 $[\mathcal{O}_K : \mathbb{Z}[x]/(f)]$와 아이디얼 노름이 서로소인 비모노제닉 필드)에서 아이디얼의 두 요소 표현을 찾는 최초의 결정론적 알고리즘을 제시한다.
• 일반화된 데데킨트 판정법: 저자들은 합성 모듈러스 $N$에 대해서도 작동하는 일반화된 버전의 데데킨트 판정법을 도입하였다. 이를 통해 $N$의 소인수를 알지 못해도 효율적인 아이디얼 곱셈과 나눗셈을 용이하게 하는 적절한 다항식 생성자를 식별할 수 있다.
• 합성 모듈러스 처리: 소수 노름에 의존했던 기존 방식(예: Pohst-Zassenhaus)과 달리, 이 방법은 합성수 $N$을 직접 처리한다. 이 방법은 $N$의 인수를 찾는 것이 불필요할 뿐만 아니라, 단순히 표현을 찾는 것이 목적이라면 오히려 과정을 늦춘다는 것을 보여준다.
• 효율성: 알고리즘은 정수 행렬(격자)에 대한 값비싼 연산을 다항식 산술으로 대체하여, 대규모 입력에 대한 공간 및 시간 복잡도를 크게 줄인다.

결과 및 복잡도
주요 결과(정리 1)는 차수가 $n$인 모노제닉 필드에 대해, 두 요소 표현 문제가 $\text{poly}(n, \log N)$ 시간에 해결될 수 있음을 명시한다.

• $N$이 제곱 자유(square-free)인 경우, 복잡도는 $O(n^2 \log N \cdot \omega(N))$이며, 여기서 $\omega(N)$은 서로 다른 소인수의 개수이다. $\omega(N)$이 평균적으로 $\log \log N$이므로, 복잡도는 무작위 알고리즘과 유사하지만 결정론적이다.
• 이 알고리즘은 격자 기반 암호(예: NewHope, Crystals-Kyber)에서 널리 사용되는 원분 다항식(cyclotomic polynomials)을 포함한 모노제닉 다항식에 대해 실용적이다.
• 만약 알고리즘이 표현을 생성하는 데 실패하면, 해당 필드가 모노제닉이 아니거나(또는 인덱스 조건이 충족되지 않음)에 대한 증명(certificate)을 제공한다.

의의 및 주장
본 논문은 소인수분해와 무작위성에 대한 의존성을 제거함으로써 아이디얼 산술의 오랜 비효율성을 해결했다고 주장한다.

• 암호학적 관련성: 본 연구는 아이디얼 격자에 기반한 포스트 양자 암호 스킴, 특히 원분체를 사용하는 스킴의 구현을 직접적으로 지원한다.
• 이론적 발전: 소수 노름에 국한되었던 Pohst-Zassenhaus 알고리즘을 임의의 합성 정수로 일반화하였다.
• 겸손함: 저자들은 알고리즘이 모든 모노제닉 필드의 아이디얼에 대해 작동하지만, 비모노제닉 필드로 확장하려면 아이디얼 노름이 인덱스와 서로소여야 한다고 언급한다. 또한, 주어진 수체에 대한 모노제닉 다항식 표현을 다항 시간 내에 찾는 것은 현재 불필요한 판별식 인자(inessential discriminant divisors)로 인해 가로막혀 있는 미해결 과제임을 밝히며, 이는 본 논문의 한계임을 명시한다. 본 논문은 거대한 정수를 인수분해하거나 일반적인 주 아이디얼 문제(principal ideal problem)를 해결한다고 주장하는 것이 아니라, 아이디얼 표현이라는 특정 작업을 위해 이러한 어려운 문제들을 우회하는 방법을 제시하는 것이다.