양자컴퓨터도 풀기 어렵다? 격자 기반 암호와 양자내성암호(PQC) 쉽게 알아보기

작성자: 슬기로운 오늘과 내일 편집부 · 발행일: 2026-09-29

최근 양자컴퓨터 관련 뉴스를 보다 보면 이런 생각이 들 수 있습니다.

“양자컴퓨터가 충분히 발전하면 지금 사용하는 인터넷 암호가 전부 풀리는 것 아닐까?”

이 질문 때문에 이번에는 양자컴퓨터 시대에 주목받고 있는 ‘격자 기반 암호’를 살펴보려고 합니다. 실제로 각국 정부와 보안업계는 미래의 양자컴퓨터에 대비해 양자내성암호(Post-Quantum Cryptography, PQC)로 전환하는 작업을 이미 시작했습니다. NIST는 2024년 첫 PQC 표준 3종을 확정했고, 한국에서도 2025년에 이어 2026년 통신·금융·교통·국방·우주 등 주요 분야를 대상으로 시범전환 사업이 진행되고 있습니다.

양자컴퓨터가 나오면 기존 암호는 모두 위험할까?

그렇지는 않습니다.

특히 문제가 되는 것은 RSA와 ECC 같은 일부 공개키 암호입니다. 충분히 큰 오류보정 양자컴퓨터가 구현된다면 쇼어(Shor) 알고리즘을 이용해 RSA가 의존하는 소인수분해나 ECC가 의존하는 이산로그 문제를 현재보다 훨씬 효율적으로 풀 가능성이 있기 때문입니다.

그렇다고 AES 같은 대칭키 암호까지 똑같은 방식으로 무너지는 것은 아닙니다. 그로버(Grover) 알고리즘은 무차별 대입 탐색을 이론적으로 빠르게 만들 수 있지만, NIST는 AES 같은 대칭키 암호에 미치는 영향은 공개키 암호와 다르게 평가하고 있습니다. 따라서 “양자컴퓨터가 나오면 모든 암호가 한꺼번에 무력화된다”는 설명은 지나치게 단순합니다.

그래서 등장한 양자내성암호

PQC는 양자컴퓨터를 이용해 암호화하는 기술이 아닙니다.

현재의 일반 컴퓨터와 통신망에서도 사용할 수 있으면서, 알려진 고전 컴퓨터와 양자컴퓨터의 공격에 모두 견디는 것을 목표로 설계한 암호기술입니다. 양자의 물리적 특성을 이용해 별도의 통신 방식으로 키를 전달하는 양자키분배(QKD)와는 다른 개념입니다.

그리고 PQC 안에는 여러 수학적 접근법이 있는데, 그중 대표적인 기술군이 바로 격자 기반 암호입니다.

격자 기반 암호에서 ‘격자’란 무엇일까?

먼저 바둑판 위에 일정한 간격으로 점이 찍혀 있다고 생각해 보겠습니다.

2차원 그림에서는 가까운 점을 찾는 일이 쉬워 보입니다. 하지만 실제 격자 기반 암호에서는 이런 공간이 수백 차원 수준의 매우 복잡한 수학적 공간으로 확장됩니다.

그 안에서 특정 조건을 만족하는 짧은 방향이나 가까운 점, 또는 원래의 값을 찾아내는 문제는 계산하기 매우 어려워질 수 있습니다.

이 설명은 이해를 돕기 위한 비유이며 실제 암호 알고리즘은 훨씬 복잡합니다.

왜 격자 문제는 풀기 어려울까?

대표적인 개념 가운데 하나가 LWE(Learning With Errors)입니다.

쉽게 말하면 일정한 규칙에 따라 만들어진 정보에 작은 ‘오차’를 섞어 놓고, 결과만 보고 원래의 비밀값을 찾아내도록 하는 문제라고 생각할 수 있습니다.

NIST의 ML-KEM은 이 계열의 Module-LWE 문제와 관련된 계산 난이도를 보안의 기반으로 사용합니다. 차원이 높아지고 적절한 매개변수가 적용되면 현재 알려진 효율적인 고전·양자 알고리즘으로 이를 해결하기 어렵다고 평가됩니다.

양자컴퓨터도 쉽게 풀지 못한다고 보는 이유

여기서 중요한 표현은 “절대 풀 수 없다”가 아니라 “현재 알려진 효율적인 방법이 없다”입니다.

쇼어 알고리즘은 RSA와 ECC에는 큰 위협이지만, 격자 기반 암호가 의존하는 문제를 같은 방식으로 효율적으로 해결하지는 못합니다.

그래서 격자 기반 암호가 PQC의 중요한 후보로 자리 잡았습니다. 다만 암호기술은 새로운 수학적 공격이나 구현 취약점이 발견되면 언제든 다시 평가될 수 있습니다. NIST 역시 여러 후보를 장기간 공개 검증한 뒤 표준을 선정하고 추가 알고리즘도 계속 평가하고 있습니다.

NIST가 선택한 양자내성암호

NIST는 2024년 8월 세 가지 PQC 표준을 확정했습니다.

  • FIPS 203 ML-KEM: 안전하게 공통 비밀키를 설정하기 위한 격자 기반 KEM
  • FIPS 204 ML-DSA: 전자서명을 위한 격자 기반 알고리즘
  • FIPS 205 SLH-DSA: 해시 함수에 기반한 전자서명 알고리즘

여기서 ML-KEM은 과거 CRYSTALS-Kyber라는 이름으로 알려졌던 알고리즘을 기반으로 하며, ML-DSA는 CRYSTALS-Dilithium을 기반으로 합니다. 따라서 Kyber와 ML-KEM, Dilithium과 ML-DSA를 완전히 별개의 기술로 생각할 필요는 없습니다.

또 하나 알아둘 점은 PQC 전체가 격자 기반인 것은 아니라는 것입니다. 예를 들어 SLH-DSA는 해시 기반이고, NIST가 2025년 추가 표준화 대상으로 선정한 HQC는 오류정정부호 계열입니다. HQC는 ML-KEM을 보완할 두 번째 KEM으로 선정됐으며 최종 표준은 아직 개발 중입니다.

FALCON을 기반으로 한 FN-DSA 역시 FIPS 206으로 개발 중이며, 2026년 9월 현재 최종 FIPS로 확정된 상태는 아닙니다.

기존 공개키 암호와 격자 기반 PQC 비교

구분기존 공개키 암호격자 기반 양자내성암호
대표 기반소인수분해·이산로그LWE·Module-LWE 등 격자 관련 난제
대표 기술RSA, ECCML-KEM, ML-DSA
양자컴퓨터 영향충분히 강력한 양자컴퓨터 등장 시 일부 방식이 큰 영향현재 알려진 효율적 고전·양자 공격에 대한 내성을 목표
주요 활용키교환·전자서명·인증키설정·전자서명
현재 상황인터넷 전반에 널리 사용표준화 후 실제 전환·도입 진행

우리는 지금 당장 무엇을 해야 할까?

일반 사용자가 인터넷뱅킹을 중단하거나 직접 자신의 암호 알고리즘을 교체할 필요는 없습니다.

문제는 장기간 비밀을 유지해야 하는 정부기관, 금융사, 의료기관, 클라우드 기업처럼 데이터를 오랫동안 보호해야 하는 조직입니다.

지금 암호화된 데이터를 누군가 저장해 두었다가 미래에 더 강력한 양자컴퓨터가 등장했을 때 해독을 시도하는 이른바 ‘Harvest Now, Decrypt Later’ 위험이 있기 때문입니다. 그래서 양자컴퓨터가 실제로 기존 공개키 암호를 해독할 수 있는 시점보다 훨씬 앞서 전환 준비가 필요합니다.

한국에서도 이런 준비가 현실적인 단계로 이동하고 있습니다. 과학기술정보통신부와 KISA는 2026년 통신·금융·교통·국방·우주 등 국가 핵심 산업을 대상으로 PQC 시범전환을 확대했고, 기업과 공공기관 담당자를 위한 실무 교육도 진행하고 있습니다.

이미 인터넷에서도 사용되고 있을까?

일부 영역에서는 이미 시작됐습니다.

예를 들어 Cloudflare는 기존 X25519 방식과 ML-KEM-768을 함께 사용하는 X25519MLKEM768 하이브리드 키 합의를 TLS에 적용하고 있습니다. 기존 방식과 PQC를 함께 사용하는 이유는 전환 기간 동안 호환성을 유지하면서 새로운 암호기술의 보호 효과도 추가하기 위해서입니다.

앞으로도 인터넷 전체가 어느 날 갑자기 새 암호로 교체되는 것이 아니라 이런 하이브리드 방식과 단계적 업그레이드를 거쳐 이동할 가능성이 큽니다.

앞으로 무엇이 달라질까?

앞으로는 웹브라우저와 서버 사이의 보안 연결, VPN, 클라우드, 전자서명, 소프트웨어 서명, 금융·공공 시스템 등 다양한 영역에서 PQC가 점차 확대될 것으로 보입니다.

NIST도 현재 조직들이 암호 사용 현황을 파악하고 취약한 공개키 알고리즘을 찾아 단계적인 PQC 전환을 준비하도록 안내하고 있습니다. 기존 시스템 전체를 한 번에 바꾸는 일이 쉽지 않기 때문에 ‘암호 민첩성’, 즉 필요할 때 암호 알고리즘을 빠르게 교체할 수 있는 구조도 중요해지고 있습니다.

결국 중요한 것은 “양자컴퓨터가 내일 모든 암호를 풀어버린다”는 자극적인 이야기가 아닙니다.

실제로는 아직 현재의 인터넷 공개키 암호를 실용적으로 무력화할 수준의 암호해독용 양자컴퓨터가 등장한 것은 아니지만, 전환에는 오랜 시간이 걸립니다. 그래서 NIST와 각국 기관들은 위험이 현실화되기 전에 준비를 시작하고 있습니다.

격자 기반 암호는 그 변화의 중심에 있는 중요한 기술 가운데 하나입니다. 앞으로 인터넷뱅킹과 전자서명, 클라우드와 정부 시스템의 보안이 어떻게 바뀌는지를 이해하려면 기억해 둘 만한 개념입니다.

#양자컴퓨터도 풀기 어렵다? 격자 기반 암호와 양자내성암호(PQC) 쉽게 알아보기