Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

기술 요약: 소수 거듭제곱 모듈리에 대한 사이클로토믹 코셋, 숨겨진 부분군, 그리고 양자 시빙(Sieving)

1. 문제 배경 및 동기

LWE(Learning With Errors) 문제는 양자 내성 암호의 기초가 되는 가정입니다. Regev는 LWE에서 디헤드럴 코셋 문제(DCP)로의 양자 환원(reduction)을 확립했으며, 이후 Brakerski 등은 EDCP(Extrapolated Dihedral Coset Problem)를 도입하여 LWE와의 동등성을 증명했습니다. 그러나 일반적인 EDCP에는 중요한 구조적 한계가 존재합니다. 즉, 평행 이동(translation) 집합이 부분군을 형성하지 않기 때문에 DCP와 달리 정확한 숨겨진 부분군(hidden-subgroup) 구조를 갖지 않습니다. 이러한 한계는 모듈러스가 2의 거듭제곱이 아닌 경우, 효율적인 숨겨진 부분군 기법을 직접 적용하는 것을 방해합니다.

최근 Bai 등의 연구(CRYPTO 2025)는 2-adic 아이디얼 체인을 활용하여 2의 거듭제곱 모듈러스($q=2^t$)에 대해 EDCP 및 가우시안 $S|LWE\rangle$를 해결하는 준다항 시간(quasi-polynomial-time) 양자 알고리즘을 달성했습니다. 그러나 임의의 소수 거듭제곱 모듈러스($q=p^t$)로 이를 일반화하는 것은 매우 어려웠는데, 이는 차수가 $2q$인 디헤드럴 군이 $q$가 2의 거듭제곱일 때만 멱질(nilpotent)이기 때문입니다. 결과적으로, 표준 멱질 군 시빙 기법(Imran 및 Ivanyos의 방식 등)을 2의 거듭제곱이 아닌 모듈러스를 가진 EDCP나 DCP에 직접 적용할 수 없었습니다.

2. 방법론 및 핵심 구성

2.1 사이클로토믹 코셋 문제 (CCP)

일반적인 소수 거듭제곱에 대해 EDCP가 갖는 숨겨진 부분군 구조의 부재를 극복하기 위해, 저자들은 **사이클로토믹 코셋 문제(Cyclotomic Coset Problem, CCP)**를 도입합니다. 이 문제는 사이클로토믹 링 $R_q = \mathbb{Z}_q[\zeta_p]$($p$는 소수, $q=p^t$, $\zeta_p$는 원시 $p$제곱근) 위에서 정의됩니다.

저자들은 세미다이렉트 곱(semidirect product) 군 $G_{n,q,p} = R_q^n \rtimes \mathbb{F}_p$를 정의합니다. 이 군이 멱질수(nilpotency class) $t(p-1)$를 갖는 멱질 군임을 증명합니다. 이 군 내에서, 저자들은 비밀 벡터 $s$에 의해 생성되는 $(s, 1)$로부터의 숨겨진 부분군 $H_s$를 식별합니다. 이 부분군과 관련된 코셋 상태(coset states)는 다음과 같은 형태를 취합니다:
$$|\phi_{x,s}\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} |j\rangle |x + \lambda_j s \rangle$$
여기서 $\lambda_j = \sum_{i=0}^{j-1} \zeta_p^i$입니다. $p=2$인 경우, 이 구성은 정확히 표준 DCP로 축소됩니다.

2.2 사이클로토믹 링에 대한 양자 푸리에 변환 (QFT)

핵리 기술적 요소는 링 $R_L = R/\pi^L R$ (여기서 $\pi = \zeta_p - 1$)에 대한 양자 푸리어 변환(QFT)의 정의와 효율적인 구현입니다. 필드 트레이스(field trace)와 아이디얼 $(p) = (\pi)^{p-1}$의 $\pi$-adic 분해를 사용하여, 저자들은 CCP 샘플을 **위상 상태(phase states)**로 매핑하는 QFT를 구축합니다.

이 변환은 $s$를 코셋 상태로부터 복구하는 문제를, 비밀값이 양자 상태의 위상에 인코딩된 **위상 상태 문제(Phase-State Problem, PSP)**로 변환합니다:
$$|\psi_y\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} \chi_y(\lambda_j s) |j\rangle$$
여기서 $\chi_y$는 링의 가법 군(additive group)에 대한 캐릭터(character)입니다.

2.3 양자 시빙 알고리즘

저자들은 "Simon-meets-Kuperberg" 프레임워크를 사이클로토믹 환경에 맞게 조정했습니다. 알고리즘은 $\pi$-adic 아이디얼 체인을 사용하여 모듈러스 레벨을 반복적으로 감소시키며 작동합니다:
$$R_q \cong R_{\pi^L} \to R_{\pi^{L-1}} \to \dots \to R_{\pi} \cong \mathbb{F}_p$$

시빙 과정은 다음과 같습니다:

1. 제로-섬 탐색 (Zero-Sum Search): 레이블 $y_i$를 가진 위상 상태 샘플 집합이 주어졌을 때, 알고리즘은 $\sum y_i \equiv 0 \pmod \pi$를 만족하는 부분 수열을 찾습니다. 이는 $\pi$에 대한 잔여(residue)에 대해 적용되는 결정론적 제로-섬 탐색 알고리즘(Imran 및 Ivanyos 기반)을 통해 수행됩니다.
2. 상태 결합 (State Combination): 해당 양자 상태들을 텐서 곱하고 특정 기저 변환 및 측정을 수행함으로써, 알고리즘은 더 낮은 링 $R_{\pi^{L-1}}$의 레이블을 가진 새로운 위상 상태 샘플을 생성합니다.
3. 반복 (Iteration): 이 과정은 $L-1$번 반복되어 문제를 $\mathbb{F}_p$ 위의 기저 케이스로 감소시키며, 여기서 선형 대수를 통해 비밀값 $s$를 복구합니다.
4. 리프팅 (Lifting): $s \pmod p$가 발견되면, 알고리즘은 $p$의 높은 거듭제곱들에 대해 재귀적으로 문제를 풀어 전체 비밀 $s \in \mathbb{Z}_q^n$를 복구합니다.

3. 주요 기여

1. CCP 및 CyLWE 도입: 본 논문은 사이클로토믹 코셋 문제(CCP)와 사이클로토믹 LWE(CyLWE)를 정의합니다. 저자들은 이 문제들이 고전적 대응물(DCP 및 LWE)과 동등하며, 일반적인 EDCP와 달리 멱질 군 위에서 숨겨진 부분군 구조를 가짐을 입증합니다.
2. 사이클로토믹 QFT 및 위상 상태: 저자들은 사이클로토믹 링 $R_q$에 대한 QFT를 엄밀하게 정의하고, CCP 샘플을 위상 상태로 변환하여 시빙 기법을 적용할 수 있음을 입증합니다.
3. 준다항 시간 시빙 알고리즘: 저자들은 CCP를 준다항 시간($2^{O(\log n \log q)}$) 내에 해결하는 양자 알고리즘(Algorithm 1)을 제시하며, 이는 다항 시간의 양자 공간을 사용합니다 (단, 샘플 수가 준다항 시간일 때).
4. 기존 결과의 일반화: 본 연구는 Bai 등의 결과($q=2^t$로 제한됨)를 임의의 소수 거듭제곱 모듈러스 $q=p^t$로 확장했습니다.
5. 동등성 증명: 저자들은 다음의 양자 환원을 제공합니다:
   • 임의의 소수 거듭제곱 모듈러스에 대한 균등(uniform) EDCP 및 가우시안 $S|LWE\rangle$는 CCP로 환원될 수 있습니다.
   • 결과적으로, $q=p^t$인 경우 균등 EDCP 및 가우시안 $S|LWE\rangle$에 대해 준다항 시간 양자 알고리즘이 존재합니다.

4. 결과 및 복잡도

• 복잡도: 제안된 알고리즘은 다항 양자 공간을 사용하여 CCP를 $2^{O(\log n \log q)}$의 시간 및 샘플 복잡도로 해결합니다.
• 범위: 결과는 고정된 소수 $p$에 대해 임의의 모듈러스 $q = p^t$에 적용됩니다.
• 환원: 본 논문은 CCP를 해결하는 것이 동일한 파라미터 제약 조건 하에서 균등 EDCP 및 가우시안 $S|LWE\rangle$를 해결할 수 있음을 보여줍니다.

5. 의의 및 한계

저자들은 본 연구가 소수 거듭제곱 모듈러스에 대한 격자 문제의 양자 알고리즘 이해를 크게 진전시켰으나, 표준 LWE에 대한 준다항 시간 알고리즘을 도출한 것은 아니라고 강조합니다.

한계는 다음과 같은 환원 체인에서 발생합니다:

1. 표준 LWE는 DCP(또는 EDCP)로 환원됩니다.
2. DCP/EDCP는 CCP로 환원됩니다.
3. CCP 해결사는 준다항 개수의 샘플을 요구합니다.

LWE에서 DCP/EDCP로의 알려진 환원은 오직 제한된(다항식 개수의) 근사 상태만을 생성합니다. CCP 해결사에 필요한 샘플 수가 LWE 환원에서 제공되는 샘플 수를 초과하기 때문에, 표준 LWE를 해결하기 위한 전체 복잡도는 여전히 지수 시간(exponential)으로 남습니다.

따라서, 이 논문의 주요 기여는 이론적입니다: 멱질 군 시빙의 능력을 더 넓은 범위의 모듈러스 클래스로 확장하고, 사이클로토믹 링 상의 코셋 문제에 대한 통합된 프레임워크를 제공하는 것입니다. 동시에 표준 LWE 보안에 대한 즉각적인 위협에 대해서는 신중한 입장을 유지하고 있습니다.