AWS 암호학자, 격자 기반 후양자 암호 이론 기반 흔드는 다항 시간 양자 알고리즘 발표

이면체 잉여류 문제란 무엇인가

DCP는 컴퓨터 과학에서 '숨겨진 부분군 문제'의 일종으로, 양자 컴퓨터는 특정 수학적 구조에 숨겨진 값을 효율적으로 찾는 데 강점을 보인다. Shor의 인수분해 알고리즘도 이 틀 안에서 설명된다. 그러나 이면체 군(dihedral group)의 경우는 20년 넘게 미해결 난제로 남아 있었다. Greg Kuperberg가 개발한 기존 최선 알고리즘은 준지수(subexponential) 시간 복잡도를 가졌으며, 이는 완전한 지수 시간보다 빠르지만 다항 시간에는 미치지 못했다.

수학자 Oded Regev는 앞서 특정 격자 문제를 DCP로 환원할 수 있음을 증명했으나, 그 과정에서 또 다른 난제인 부분합 오라클(subset-sum oracle)에 의존해야 한다는 한계가 있었다. Simon의 논문은 이 오라클 없이 다항 시간 절차를 제시함으로써 그 공백을 메웠다고 주장한다.

알고리즘의 핵심 구조

알고리즘의 기술적 도전 중 하나는 양자 위상(phase) 정보를 보존하면서 불필요한 정보를 제거하는 것이다. Simon은 다수의 양자 샘플을 그룹으로 나눠 처리하는 방식을 제안한다. 일부 그룹은 불필요한 위상 없이 활용되고, 나머지에서 측정된 정보는 양자 상태의 관련 부분이 균형을 이루도록 분리된다. 이후 숨겨진 값의 한 비트를 인코딩한 위상을 대체 큐비트로 옮기고, 이를 재귀적으로 반복해 나머지 비트를 복원한다. 해당 과정이 올바른 답을 충분히 높은 확률로 보존하는지에 대한 증명이 논문 상당 부분을 차지한다.

또한 Simon은 알고리즘이 결함 있는 샘플에 대한 내성을 갖는다고 주장한다. 허용 가능한 오류율은 문제 크기의 로그 역수(~1/log n) 수준이며, 이는 격자 문제와의 연결에서 중요한 역할을 한다. 격자 문제에서 DCP로의 환원 과정에서 발생하는 오류가 이 범위 안에 들어올 경우 최종 결과에 영향을 주지 않기 때문이다.

격자 암호와의 연결

Simon의 알고리즘을 Regev 및 후속 연구자들이 개발한 기존 환원(reduction)과 결합하면, n차원 격자에서 최단 벡터의 √n × 다중로그(polylogarithmic) 근사치를 다항 시간 내에 구하는 양자 알고리즘이 도출된다고 논문은 주장한다. 최단 벡터 문제(SVP)와 오류 포함 학습(LWE) 문제는 NIST가 채택한 격자 기반 후양자 암호 표준의 이론적 근거를 이루는 두 가지 핵심 난제다.

실제 위협 여부와 해석의 한계

이 논문이 즉각적인 암호 위협을 의미하지는 않는다. 논문 자체가 구체적인 표준 알고리즘에 대한 공격 시나리오나 키 복원 방법을 제시하지 않으며, 암호학적으로 유효한 규모에서 알고리즘을 실행하는 데 필요한 논리 큐비트 수, 양자 게이트 수, 오류 정정 자원도 추산하지 않는다.

다항 시간 알고리즘이라 하더라도 차수가 높거나 상수 인자가 클 경우 현실적으로 실행 불가능할 수 있다. LWE의 최악 사례 복잡도, 암호 구현에서 실제 사용되는 평균 사례 매개변수, 그리고 다양한 LWE 변형 문제들 사이의 관계 또한 별도로 분석해야 한다. 연구 공동체는 확률론적 논거의 정확성과 알고리즘 설계의 세부 사항을 면밀히 검토할 것으로 예상된다.