Future Cryptography — 양자역학이 바꾸는 암호의 미래

RSA는 소인수분해의 어려움, ElGamal은 이산 대수의 어려움 위에 서 있다. 그런데 양자 컴퓨터는 이 두 문제를 다항식 시간에 풀 수 있다. 현재 암호학의 기반이 통째로 흔들리는 것이다. 하지만 양자역학은 암호를 파괴하기만 하는 것이 아니라, 물리 법칙 자체가 보안을 보장하는 새로운 암호를 가능하게 한다.

마이켈슨 간섭계 (Michelson Interferometer)

양자 암호학을 이해하려면 빛의 파동-입자 이중성부터 시작해야 한다. 간섭계는 이 성질을 가장 직관적으로 보여주는 장치다.

구조: 광원에서 나온 빛이 반투명 거울(beam splitter)에서 두 경로로 나뉜다. 각 경로의 끝에 있는 거울에서 반사되어 다시 반투명 거울에서 합쳐진다.

간섭: 두 경로의 거리($d_1$, $d_2$)를 적절히 조절하면:

• 한 방향으로는 두 파동의 위상이 일치해 보강 간섭(constructive interference) — 파동이 더 강해진다
• 다른 방향으로는 위상이 반대가 되어 상쇄 간섭(destructive interference) — 파동이 사라진다

결과적으로 빛은 한 방향으로만 나아간다. 경로 사이의 미세한 거리 변화가 간섭 패턴을 바꾸므로, 극도로 작은 변위를 측정할 수 있다. LIGO 중력파 관측소는 이 원리로 $10^{-21}$ m 수준의 시공간 왜곡을 검출했다.

양자 폭탄 검출기 (Elitzur-Vaidman Bomb Tester)

정상적으로 작동하는 폭탄인지 확인하려면 터뜨려봐야 한다. 하지만 터진 폭탄은 사용할 수 없다. 양자역학은 이 딜레마를 해결한다 — 광자 하나도 건드리지 않고 폭탄의 상태를 알아낼 수 있다.

설정: 간섭계의 경로 ①에 폭탄을 놓는다. 폭탄이 정상이면 광자를 감지하는 Detector 역할을 한다.

불발탄인 경우: Detector가 없으므로 광자는 **확률(파동)**로 두 경로를 동시에 통과한다. 간섭이 정상적으로 발생해 상쇄 방향(D₂)에서는 검출되지 않고, 보강 방향(D₁)에서만 검출된다.

정상 폭탄인 경우: Detector가 경로 ①에 존재하므로 광자가 입자로 확정된다.

• 경로 ①으로 가면 (50%): 폭탄이 폭발한다
• 경로 ②로 가면 (50%): 경로 ①이 차단되어 간섭이 사라지고, D₁ 또는 D₂에서 각각 50%로 검출된다

핵심: D₂에서 광자가 검출되면 — 간섭이 깨졌다는 뜻이고, 이는 경로 ①에 Detector(정상 폭탄)가 있다는 의미다. 광자는 경로 ②를 통과했으므로 폭탄에 닿지 않았지만, 폭탄이 정상임을 확인했다. 전체 성공 확률은 25%다.

암호학적 함의: 이 원리를 통신에 적용하면, 도청자가 광자를 관측하는 순간 간섭 패턴이 깨진다. 따라서 수신자는 도청이 있었는지 검출할 수 있다 — 고전 통신에서는 불가능한 일이다.

EPR 역설

1935년, 아인슈타인·포돌스키·로젠(Einstein-Podolsky-Rosen)은 양자역학의 완전성에 도전하는 사고 실험을 제시했다.

Spin: 전자는 고유한 각운동량(spin)을 가진다. 측정하면 특정 방향의 위 또는 아래 중 하나만 나온다. 측정 전에는 둘 다의 중첩(superposition) 상태에 있다.

실험: spin이 0인 입자가 두 개로 분리되면, 각운동량 보존에 의해 한쪽이 위이면 다른 쪽은 반드시 아래다. 두 입자를 빛의 속도로도 도달할 수 없는 거리에 놓고 한쪽을 측정하면, 즉시 다른 쪽의 상태가 결정된다.

아인슈타인의 주장: 입자가 정말로 측정 전까지 확률로 존재한다면, 한쪽의 측정 결과가 다른 쪽에 빛보다 빠르게 전달되어야 한다. 이것은 특수 상대성 이론에 위배된다. 따라서 입자는 처음부터 상태가 정해져 있었고, 양자역학이 이를 기술하지 못하는 것일 뿐이다 — 즉 “숨은 변수(hidden variable)“가 존재한다.

보어의 반론: 무언가 “전달”되는 것은 맞지만, 이를 통해 정보를 전송할 수는 없다. 한쪽의 측정 결과는 랜덤이므로, 다른 쪽의 관측자가 그 결과를 사전에 예측하거나 조작할 수 없다.

벨의 정리 (Bell’s Theorem)

1964년, 존 벨(John Bell)은 “숨은 변수”가 존재하는지 실험적으로 판별할 수 있는 부등식을 유도했다.

실험: EPR과 동일하게 입자를 두 개로 나누되, 두 측정기의 방향을 다르게 설정한다. 예를 들어 하나는 수직, 다른 하나는 45도로 기울인다.

• 숨은 변수가 존재한다면: 입자는 생성 시점에 모든 방향의 결과가 이미 정해져 있다. 이 경우 두 측정 결과의 상관관계는 벨 부등식을 만족한다.
• 양자역학이 옳다면: 측정 전까지 확률로 존재하며, 측정 순간 상태가 결정된다. 이 경우 상관관계는 벨 부등식을 위반한다.

실제 실험 결과(Aspect, 1982): 벨 부등식이 위반되었다. 양자역학이 옳고, 숨은 변수는 존재하지 않는다. 입자는 정말로 측정 전까지 확률로 존재한다.

이것은 이전 글에서 다룬 과학적 원리의 적용이다 — “실험으로 구별할 수 없는 두 이론(숨은 변수 vs 확률) 중 실험과 일치하는 쪽이 참이다.”

양자 컴퓨터

양자 컴퓨터는 비결정적 튜링 머신(NTM)과 유사한 방식으로 동작한다. 고전 컴퓨터의 비트가 0 또는 1인 반면, 양자 비트(qubit)는 0과 1의 중첩 상태에 있다. $n$개의 qubit는 $2^n$개의 상태를 동시에 표현한다.

클래스 QP: 양자 컴퓨터로 다항식 시간에 풀 수 있는 문제들의 집합이다.

$\text{QP} = \text{NP}$인지는 알려져 있지 않다. NTM처럼 모든 경로를 동시에 탐색하지만, 결과를 측정하는 순간 하나의 상태만 남고 나머지는 사라진다. 따라서 단순히 “모든 경우의 수를 동시에 계산”하는 것이 아니라, 정답을 증폭(amplification) 시켜 측정 시 높은 확률로 나오게 하는 알고리즘이 필요하다.

Shor의 알고리즘

Peter Shor(1994) 는 양자 컴퓨터로 소인수분해를 다항식 시간 $O((\log n)^3)$에 수행하는 알고리즘을 발표했다.

이것이 암호학에 미치는 영향은 심대하다:

• RSA: $n = pq$ 소인수분해가 어렵다는 가정 → Shor로 다항식 시간에 해결 → 파괴
• ElGamal/DH: 이산 대수 문제(DLP)도 Shor의 변형으로 다항식 시간에 해결 → 파괴
• ECC: 타원곡선 이산 대수도 동일하게 취약 → 파괴

현재의 공개키 암호 체계 전체가 충분히 큰 양자 컴퓨터 앞에서 무력화된다. 이것이 후양자 암호(Post-Quantum Cryptography) 연구의 동기다.

양자 키 교환 (BB84)

양자역학이 암호를 파괴하기만 하는 것은 아니다. BB84 프로토콜(Bennett & Brassard, 1984) 은 물리 법칙 자체가 보안을 보장하는 키 교환 방법이다.

핵심 원리: 양자 상태는 관측하면 변한다. 도청자가 광자를 관측하는 순간, 광자의 상태가 교란되어 수신자가 이를 감지할 수 있다.

프로토콜

Step 1: Alice가 랜덤 비트열을 생성하고, 각 비트를 두 기저(+: 상하/좌우, ×: 대각선) 중 랜덤으로 선택해 편광된 광자로 전송한다.

Step 2: Bob은 각 광자를 랜덤 기저로 측정한다. 기저가 맞으면 올바른 비트를 얻고, 기저가 틀리면 무작위 결과가 나온다.

Step 3: Alice와 Bob은 공개 채널로 기저만 공개한다(측정값은 비공개). 기저가 일치하는 위치의 비트만 유지한다.

Step 4: 유지된 비트의 절반을 공개적으로 비교한다. 일치하면 도청이 없었다고 판단하고, 나머지 절반을 비밀 키로 사용한다.

도청 검출

Eve가 중간에서 광자를 관측하면:

1. Eve는 Alice의 기저를 모르므로 랜덤 기저로 측정한다
2. 잘못된 기저로 측정하면 광자의 편광 방향이 변한다
3. Bob이 이 변형된 광자를 측정하면, 기저가 맞더라도 Alice의 원래 비트와 다른 결과가 나올 수 있다
4. Step 4의 비교에서 불일치가 발견된다 → 도청 감지

이 보안은 수학적 어려움이 아니라 양자역학의 법칙 — 관측이 상태를 변화시킨다는 물리적 사실 — 에 기반한다. 양자 컴퓨터로도 깰 수 없다. 실제로 광케이블을 통한 양자 키 분배(QKD)가 상용화되어 운용 중이다.