AWS 연구원 사이먼, 양자 알고리즘으로 DCP 해결 주장... 암호학계 '강한 회의론'

하지만 2026년 8월 초 현재, 이 예비 논문은 아직 검증되지 않았으며, 증명의 완성도에 의문이 제기되고 있습니다. 표준화된 포스트퀀텀 암호체계(PQC)가 실질적인 위협을 받고 있지도 않습니다 . 이 글에서는 사이먼의 주장 내용, 검증 현황, 그리고 ML-KEM·ML-DSA 같은 실제 배포 표준에 미치는 영향을 상세히 분석합니다.

사이먼의 예비 논문, 무엇을 주장하나

사이먼의 논문은 그동안 격자 기반 암호(lattice-based cryptography)로 가는 '다리' 역할을 할 것으로 알려진 DCP를 푸는 다항시간 양자 알고리즘을 제시합니다 . 주요 주장은 다음과 같습니다:

• DCP의 다항시간 해결. 이 알고리즘은 양자컴퓨터에서 DCP를 다항시간에 해결합니다. 2002년 Oded Regev가 제시한 이면체 부분군 문제(Dihedral Subgroup Problem)와 DCP 간의 연결 고리를 기반으로 합니다 .
• 20년 간극 해소. 만약 정확하다면, Regev의 환원(reduction) 이후 약 2004년부터 지속된 미해결 문제를 해결하는 것입니다 .
• 새로운 기술적 접근법. 기존 접근법에서 사용된 핵심 오라클(oracle)을 '블록 앤드 쿼리(block-and-query)' 기법으로 대체해 은닉 부분군 정보를 추출합니다 .
• 격자 문제에 대한 파생 결과. 논문은 이 알고리즘이 Regev 와 Brakerski, Kirshanova, Stehlé, Wen 의 개선된 환원 기법과 결합되어, 최단 벡터 문제(SVP) 나 LWE(Learning With Errors) 문제에 대한 다항시간 양자 알고리즘을 만들 수 있다고 주장합니다 .

또한 이 알고리즘은 최대 1/O(log n) 비율의 결함 있는 샘플까지 견딜 수 있어, 환원 경로와의 결합을 통해 격자 문제를 효율적으로 해결할 수 있다고 합니다 .

검증 현황: 회의론과 '기다려보고 확인하자'는 분위기

2026년 8월 7~8일 기준, 암호학계의 반응은 신중하고 회의적입니다 .

• 동료 검토 없음. 논문은 '예비 초안(Preliminary Draft)'으로 표시되어 있으며, 2026년 8월 6일 IACR ePrint 서버에 게재되었습니다 . 아직 학술지나 학회에 채택되지 않았습니다.
• 초기 회의적 반응. 여러 전문가 분석에 따르면, 논문의 핵심 증명 여러 개가 스케치 수준이고, 최종 결론 중 SVP와 LWE 파라미터에 관한 부분은 공식 출판된 유도 과정이 아닌 미발표 개인 통신에 부분적으로 의존하고 있습니다 . 한 업계 분석가는 초기 반응을 '강한 회의론(heavy skepticism)'이라고 표현했습니다 .
• 독립적 확인 없음. 예비 논문이 공개된 이후 독립적인 검증이나 반박이 발표되지 않았습니다 . 학계의 지배적인 분위기는 '사실을 먼저 확인하자(facts before reaction)'입니다 .
• 실질적 공격 아님. 보도 자료들은 이것이 표준화된 암호 체계에 대한 구현된 공격이 아닌, DCP에 대한 이론적 주장임을 일관되게 강조합니다 .

ML-KEM과 ML-DSA에 미치는 의미

NIST 표준 포스트퀀텀 암호를 도입하거나 평가 중인 조직에게 즉각적인 결론은 명확합니다. 이 예비 논문 때문에 현재의 계획을 바꿀 이유가 없다는 것입니다 .

• 즉각적인 실질적 위협 없음. 이 논문은 ML-KEM(FIPS 203)이나 ML-DSA(FIPS 204)에 대한 공격을 구현하지 않습니다 . 어떤 NIST 파라미터 세트도 공격받지 않았습니다 .
• 이론적 영향은 간접적. DCP는 알려진 환원 기법을 통해 격자 문제와 연결되지만, 이러한 환원이 ML-KEM과 ML-DSA의 기반인 모듈러 LWE(Module-LWE) 나 모듈러 SIS(Module-SIS) 에 대한 구체적인 공격으로 이어질지는 아직 입증되지 않은 또 다른 이론적 단계입니다 .
• 구조적 우려사항이지 실질적 위협은 아님. 주장이 검증된다면, 양자컴퓨터가 특정 격자 문제를 효율적으로 풀 수 있다는 이론적 근거가 강화될 것입니다. 하지만 '일반적인 격자 문제'는 NIST 표준에 사용된 특정 구조화된 격자 가정보다 훨씬 광범위한 범주입니다 .
• 선행 연구와의 맥락. 2025년, Bai 등의 연구진은 DCP의 제한된 변형(2의 거듭제곱 법(moduli)에 대한 외삽형 DCP, EDCP)에 대한 준다항시간(quasi-polynomial time) 알고리즘을 달성한 바 있습니다 . 사이먼의 완전한 다항시간 주장은 그보다 훨씬 큰 도약이지만, 아직 확인되지 않았습니다.

전문가 커뮤니티 반응: 강한 회의론과 신중한 접근 촉구

암호학 및 포스트퀀텀 보안 커뮤니티는 명확한 메시지를 보내고 있습니다. 기다리고, 확인하고, 과도하게 반응하지 말라는 것입니다 .

• '강한 회의론' 보도. 포스트퀀텀 업계 분석가들은 증명의 스케치 같은 성격과 미발표 참고문헌 의존성을 결론을 내리기 전에 면밀한 조사가 필요한 주요 위험 신호로 지적합니다 .
• 조건부 함의. DCP가 다항시간에 풀리더라도, 격자 기반 PQC에 대한 이론적 함의는 '조건부'입니다. 이는 DCP 자체의 해결 가능성뿐만 아니라 특정 환원 경로에도 의존하기 때문입니다 .
• 주요 기관 공식 입장 없음. NIST, 학계 연구소, 표준화 기구는 아직 공식 입장을 발표하지 않았습니다. 예비 논문이 공개된 지 며칠밖에 되지 않았기 때문에 예상된 상황입니다 .
• 일반적 태도. 학계는 이를 중요한 주장으로 간주하고 신중한 조사가 필요하다고 여기지만, PQC 배포 일정이나 파라미터 세트를 변경해야 할 이유는 없다는 입장입니다 .

요약하자면, Daniel Simon의 예비 논문은 검증될 경우 격자 기반 암호학의 기초에 심대한 영향을 미칠 수 있는 중요한 이론적 주장입니다. 하지만 현재로서는 검증되지 않은 예비 논문이며, 상당한 결함이 지적되고 있습니다. ML-KEM이나 ML-DSA 같은 NIST 표준화된 포스트퀀텀 알고리즘의 실질적인 보안에는 영향을 미치지 않습니다.