[crypto] 양자 내성 암호(PQC)

김민주·2026년 6월 3일

security

목록 보기

14/14

서론

소모임 암호 세션에서 1학기 마지막 세션에는 각자 15분 발표를 진행하기로 하였다. 그중에서 나는 PQC로 주제를 잡고 발표하기 위해 정리해보고자 한다.

양자 암호라는 말은 많이 들어봤다. 요즘 양자가 뜨고 있다는 것도 많이 들었다. 그러나, "양자가 뭐야?"라는 질문에는 명확하게 대답할 수 없는 것 같다. 양자(quantum)란 물질을 구성하는 원자와, 원자를 구성하는 극소 물질을 총칭하는 용어이다. 이러한 미시 시계에서는 우리 눈에 보이는 세계에서 적용되는 물리법칙과는 다른 양자 역학(quantum mechanics)이 적용된다.

양자 역학의 특징에는 양자 중첩(quantum superposition)과 양자 얽힘(quantum entanglement) 특징이 있다. 양자 중첩은 양자 입자가 두개의 가능한 값을 동시에 가지고 있는 상태를 말하고, 양자 얽힘은 서로 얽힌 상태의 둘 이상의 양자 입자들이 아무리 떨어져 있어도 한 입자에 생긴 변화가 다른 입자의 상태에 즉각적으로 영향을 주는 것을 의미한다. 이 두 개의 특징에 정보기술을 결합한 것을 우리는 양자정보기술이라고 부른다.

양자 정보기술에는 3가지의 종류가 있다. 이중에서 이 포스트에서는 양자 암호 통신에 대해 살펴볼 것이다.

양자 내성 암호(Post-Quantum Cryptography, PQC)

양자 내성 암호는 미래 양자 컴퓨터의 공격을 견딜 수 있도록 설계된 차세대 암호화 알고리즘을 제공한다. 미국 국립표준기술연구소(NIST)는 일련의 PQC 알고리즘을 표준화하여 PQC가 널리 채택될 수 있는 길을 열었다.

양자내성암호는 양자컴퓨터의 공격에도 안전한 새로운 암호화 방식이다. 그러면 이제 양자컴퓨터가 정확하게 뭔지도 궁금해진다. 양자컴퓨터란 양자 역학의 고유한 특성을 활용하여 기존의 컴퓨터의 능력을 뛰어넘는 문제를 해결하는 컴퓨터이다.

등장 배경

기존에는 RSA와 ECC가 소인수분해와 이산 로그 문제를 기반으로 보안을 유지해왔다. 이러한 문제들은 고전 컴퓨터로는 해결하는 데 오랜 시간이 걸리기 때문에 안전하다고 여겨져 왔다. 하지만 양자 컴퓨터는 기존 컴퓨터로는 해결 불가능한 속도로 문제를 해결할 수 있는 잠재력을 가지고 있다.

양자 알고리즘인 쇼어 알고리즘(Shor's Algorithm)은 RSA, ECC등을 빠르게 해독할 수 있다. 따라서 양자내성암호는 다양한 수학적 구조를 활용하여 보안성을 확보한다.

양자내성암호에서 사용하는 수학적 구조는 다음과 같다

격자 기반 암호(Lattice-based Cryptography)
: 다차원 공간에서 규칙적으로 배열된 격자(Lattice)구조의 수학적 난제를 활용한 암호화 방식

다변수 다항식 기반 암호(Multivariate Polynomial Cryptography)
: 다변수 이차 연립 방정식을 푸는 것이 어렵다는 수학적 난제를 이용한 공개키 암호화 방식

코드 기반 암호(Code-based Cryptography)
: 오류 수정 코드의 디코딩(복호화) 난제를 기반으로 한 공개키 암호화 방식

해시 기반 암호(Hash-based Cryptography)
: 기존 해시 함수의 충돌 불가능성에 의존하는 암호화 방식

양자내성암호 종류(1)-격자 기반 암호

다차원 격자(Lattice)라는 수학적 구조에 기반한다.

격자란 n-차원 공간에서 일정한 규칙으로 형성된 이산적인 점들의 집합이다. 쉽게 생각하면, 바둑판 위의 교차점들을 떠오릴 수 있다. 바둑판 위의 교차점들은 2차원 격자이다.

위 사진에 있는 검은 점들은 하나하나가 격자점이다.
원점을 기준점이라고 해보자.
격자에서는 이 기준점에서 어떤 방향으로 몇 번 이동하는지에 따라 따른 격자점에 도달할 수 있다.
$b_1$ 과 $b_2$ 는 격자를 설명하는 기본 방향, 기저 벡터라고 부른다. $b_1$ 과 $b_2$ 을 이용해서 여러 격자점에 도달할 수 있다.
즉, 격자는 기저 벡터들을 정수 번 조합해 갈 수 있는 모든 점들의 모음이다.
같은 격자여도 어느 기저로 설명하는지에 따라 쉬워 보이기도 하고 어려워 보이기도 한다. 빨간 화살표는 길고 멀리 돌아가는 방향(좋은기저)이라면, 파란 화살표는 짧고 직관적인 방향(나쁜 기저)이다.

격자 기반 암호는 이 점들 중에서 가장 가까운 점을 찾는 문제를 이용한다. 2차원 격자는 눈으로 보면 금방 찾을 수 있지만, 차원이 높아진 수백 차원의 공간에서는 이 문제가 매우 어려워진다. 격자 기반 암호는 이 어려움을 이용한다.

비밀키를 가진 사람은 가까운 점을 금방 찾을 수 있지만, 복잡하게 뒤틀린 지도만 가진 사람은 같은 문제를 풀기 매우 어려울 것이다.
이 어려움 때문에 양자컴퓨터가 등장해도 비교적 안전한 암호 후보로 연구되고 있다.

대표 알고리즘으로는 Kyber, Dilithium이 있다.

양자내성암호 종류(2)-다변수 다항식 기반 암호

다변수 다항식 연립방정식을 푸는 것이 어렵다는 것을 이용한다.

다변수 다항식의 예시를 보면, $x_1$ 부터 $x_{20}$ 까지 여러 개의 미지수가 있고, 이 미지수들이 서로 곱해진 2차식들이 여러 줄로 나열되어 있다.
다변수다항식 기반 암호는 이런 복잡한 2차 방정식들을 공개해 놓고, 이 방정식을 만족하는 해를 찾는 것이 어렵다는 점을 이용한다.

처음에 이 식을 봤을 때, 중국인의 나머지 정리(CRT)가 생각이 이 났다.
'CRT랑 생긴게 비슷해 보이는데 뭐가 다른가?'에 대해 생각해 봤다.
하지만 자세히 보면 다르다. 애초애 변수 개수 부터가 다르고, modular하는 값 또한 모두 동일하다. 그냥 형태만 비슷하게 생긴거였다.