QUBO Modeling of Module Learning With Errors: Stability and Scaling in Post-Quantum Cryptography

기술 요약: 모듈 학습 오차(Module Learning With Errors)의 QUBO 모델링

문제 정의
격자 기반 양자 내성 암호(PQC), 특히 MLWE(Module Learning With Errors) 문제에 의존하는 스킴은 양자 공격으로부터 시스템을 보호하기 위한 유력한 후보이다. MLWE의 핵심 난제는 공개 행렬 $A$와 작은 오차 벡터 $e$로부터 숨겨진 비밀 벡터 $s$를 복구하는 것($b = As + e \pmod q$)이다. 고전적인 격자 축소 알고리즘(예: BKZ)과 양자 강화 탐색 방법은 광범위하게 연구되어 왔으나, 비밀 변수와 오차 변수 모두를 양자 어닐링에 적합한 통합 최적화 프레임워크로 명시적으로 인코딩하는 방법에 대해서는 이해가 부족한 상태이다. 기존의 방식들은 주로 결정 출력에 집중하거나 노이즈 변수를 제거하며, 이는 섭동(perturbation) 하에서의 솔루션 지형(solution landscape)의 안정성을 분석하기 위한 투명한 표현력이 결여되어 있다.

방법론
저자들은 작은 규모의 MLWE 인스턴스를 이차 무제약 이진 최적화(QUBO) 모델로 인코딩하기 위한 구성적 프레임워크를 제안한다. 본 방법론은 다음 단계들을 포함한다:

1. 결합 인코딩(Joint Encoding): 노이즈를 마진화(marginalize)하는 기존 방식과 달리, 본 연구는 비밀 계수($s$)와 오차 성분($e$)을 단일 이진 벡터 $z$로 명시적으로 인코딩한다. 정수 값은 유한 비트 이진 확장(예: $s_i = \sum 2^k x_{ik}$)을 통해 표현된다.
2. 목적 함수 정식화: MLWE 복구 문제는 잔차 최소화(residual minimization) 문제로 변환된다. 노이즈가 존재하는 경우, 목적 함수는 다음과 같이 정의된다:
   $$\min_{s,e} \|As + e - b\|^2_2 + \lambda\|e\|^2_2$$
   여기서 $\lambda$는 정규화 매개변수이다. 이진 인코딩을 대입하면 이는 표준 QUBO 형태인 다음으로 변환된다:
   $$\min_{z \in \{0,1\}^{N_{logical}}} z^\top Q z + c^\top z$$
3. 행렬 구조: 결과적인 상호작용 행렬 $Q$는 다음과 같은 블록 구조를 나타낸다:
   $$Q = \begin{bmatrix} Q_{ss} & Q_{se} \\ Q_{es} & Q_{ee} \end{bmatrix}$$
   여기서 $Q_{ss}$는 비밀 변수 간의 상호작용을, $Q_{ee}$는 노이즈 정규화를, $Q_{se}$는 비밀과 노이즈 사이의 결합을 인코딩한다.
4. 안정성 분석: 논문은 최적화 지형의 안정성 분석을 전개한다. 저자들은 허용 가능한 섭동(노이즈)의 영역을 경쟁하는 후보 비밀들의 하프스페이스(half-spaces) 교집합으로 정의되는 **볼록 다면체(convex polytope)**로 규정함으로써 이를 특성화한다. 이러한 기하학적 관점은 바닥 상태(ground state)와 첫 번째 들뜬 상태(first excited state) 사이의 에너지 갭($\Delta E = E_2 - E_1$)과 연결된다.

주요 결과
저자들은 정확한 시뮬레이션(전수 조사)을 사용하여 저차원 벤치마크 인스턴스(구체적으로 모듈러스 $q=4$인 $3 \times 3$ 시스템)에 대해 수치 실험을 수행하였다:

• 정확한 복구: 노이즈가 없는 경우($e=0$)와 노이즈가 있는 경우($e \neq 0$) 모두에서, QUBO 정식화는 심어진(planted) 비밀 벡터와 이산화된 오차 벡터를 유일한 전역 최솟값으로 성공적으로 식별하였다.
• 안정성 검증: 수치 결과는 기하학적 안정성과 에너지적 거동 사이의 이론적 연결을 확인해주었다. 에너지가 양의 갭을 유지하는 영역은 기하학적으로 도출된 허용 가능한 섭동의 볼록 다면체와 일치하였다.
• 스케일링 분석: 연구는 논리 변수의 스케일링($N_{logical} = n\lceil \log_2 q \rceil + m\lceil \log_2 q_e \rceil$)을 정량화하였다. 암호학적으로 유의미한 인스턴스(예: $n=256, m=512$인 Kyber 유사 파라미터)의 경우, 논리 변수 개수는 약 5,120개에 달한다.
• 하드웨어 제약: 분석 결과, 논리 변수의 수는 차원에 따라 선형적으로 증가하지만, $A$의 구조로 인한 QUBO의 조밀한 연결성(dense connectivity)이 상당한 임베딩 오버헤드를 발생시킨다는 점을 강조한다. 이는 암호학적으로 유의미한 인스턴스들이 현재의 양자 어닐링 하드웨어 용량을 훨씬 초과함을 의미한다.

의의 및 주장
본 논문은 자신의 기여를 실질적인 암호 해독 위협이라기보다 방법론적인 것으로 규정한다. 저자들은 현재의 하드웨어가 관련 파라미터 크기를 감당하기에 불충분하다는 점을 들어, 본 연구가 표준화된 양자 내성 스킴에 대한 실질적인 공격을 의미하지 않는다고 명시적으로 밝히고 있다.

본 연구의 주요 의의는 다음과 같다:

1. 통합 표현: 비밀과 오차를 공동으로 모델링하여, 단일 최적화 지형 내에서 이들의 상호작용을 연구할 수 있는 투명한 프레임워크를 제공한다.
2. 강건성 프레임워크: MLWE 문제와 양자 최적화를 연결하는 체계적인 방법을 구축하고, 기하학적(다면체) 및 에너지적(갭) 관점을 통해 QUBO 정식화의 강건성을 분석할 수 있는 도구를 제공한다.
3. 벤치마킹: 양자 최적화 환경에서 격자 기반 문제를 연구하기 위한 구조화된 기초를 마련하며, 향후 하이브리드 양자-고전 휴리스틱 또는 희소(sparse) QUBO 변형 연구를 위한 참조 모델 역할을 한다.

결론적으로, 본 연구는 격자 기반 암호 모델링과 하드웨어 인지적 이진 최적화 사이의 가교 역할을 하며, QUBO로의 MLWE 인코딩에 대한 이론적 타당성을 명확히 하는 동시에 현재의 양자 어닐링 아키텍처가 갖는 실질적인 한계를 규명한다.