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

RSA는 소인수분해의 어려움, ElGamal은 이산 대수의 어려움 위에 서 있다. 그런데 양자 컴퓨터는 이 두 문제를 다항식 시간에 풀 수 있다. 현재 공개키 암호의 기반이 흔들리는 것이다. 동시에 양자역학은 물리 법칙 자체가 보안의 근거가 되는 새로운 암호를 가능하게 한다.

마흐·젠더 간섭계 (Mach–Zehnder Interferometer)

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

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

간섭: 두 경로의 거리($d_1$, $d_2$)를 적절히 조절하면 다음과 같은 일이 일어난다.

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

결과적으로 빛은 한 방향으로만 나아간다. 경로 사이의 미세한 거리 변화가 간섭 패턴을 바꾸므로, 극도로 작은 변위를 측정할 수 있다.

아래 그림은 반투명 거울 두 개로 경로를 갈랐다가 다시 합치는 마흐·젠더 배치다. 뒤에서 볼 양자 폭탄 검출기가 쓰는 것이 이 배치다. LIGO는 반투명 거울 하나로 갈라 거울에 튕겨 되돌아오게 하는 마이켈슨 배치를 쓰지만, 「경로차가 간섭을 바꾼다」는 원리는 같다.

LIGO가 검출하는 값은 길이가 아니라 변형률(strain), 곧 길이의 상대 변화 $h = \Delta L / L$이다. 대표적으로 $h \sim 10^{-21}$ 수준이다. 팔 길이가 $L = 4$ km이므로 실제 길이 변화는

\Delta L = h L pprox 10^{-21} imes 4 imes 10^3 \ ext{m} = 4 imes 10^{-18}\ ext{m}

로, 양성자 반지름의 약 $1/200$이다. $10^{-21}$을 미터로 읽으면 세 자리가 어긋난다.

양자 폭탄 검출기 (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 확률) 중 실험과 일치하는 쪽이 참이다.”

양자 컴퓨터

고전 컴퓨터의 비트가 0 또는 1인 반면, 양자 비트(qubit)는 0과 1의 중첩 상태에 있다. $n$개의 qubit가 이루는 상태는 $2^n$개의 기저 상태 각각에 진폭(amplitude) 이라는 복소수를 붙인 것이다.

계산은 이 진폭들을 한꺼번에 회전시키는 유니터리 변환의 연속이다. 측정하면 기저 상태 하나가 나오는데, 그 확률은 진폭의 절댓값 제곱이다.

비결정적 튜링 머신에 빗대는 설명이 흔하지만 오해를 부른다. NTM은 갈래를 모두 탐색하고 하나라도 성공하면 받아들인다. 양자 컴퓨터에는 그런 「하나라도」가 없다. 측정은 진폭 분포에서 하나를 뽑을 뿐이라 정답 갈래의 진폭이 작으면 사실상 나오지 않는다. 그래서 양자 알고리즘이 하는 일은 탐색이 아니라 간섭이다. 오답의 진폭들이 서로 상쇄되고 정답의 진폭이 보강되도록 회전을 설계한다.

클래스 BQP: 양자 컴퓨터로 다항식 시간에 풀되 답이 틀릴 확률이 $1/3$ 이하인 문제들의 집합이다. 이 문턱은 같은 계산을 여러 번 되풀이해 다수결을 취하면 얼마든지 낮출 수 있어서, 어디로 잡든 같은 클래스가 나온다.

$\text{BQP}$와 $\text{NP}$의 관계는 알려져 있지 않다. 어느 쪽도 다른 쪽을 포함한다고 밝혀지지 않았다.

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: 유지된 비트(sifted key) 가운데 일부를 표본으로 골라 공개 비교해 오류율(QBER) 을 추정한다. 추정값이 미리 정한 문턱을 넘으면 그 세션을 버린다.

Step 5: 문턱 아래라면 남은 비트로 오류 정정(reconciliation) 을 수행해 두 쪽의 비트열을 일치시킨다. 이 과정에서 오간 정보는 Eve도 듣는다.

Step 6: 비밀 증폭(privacy amplification) 으로 Eve가 가졌을 수 있는 정보량만큼 키를 줄인다. 여기서 나온 짧은 키가 최종 키다.

전제도 하나 밝혀 둔다. 고전 채널은 인증되어 있어야 한다. 기저와 표본을 주고받는 채널이 인증되지 않으면 Eve가 양쪽에 각각 다른 사람인 척하는 중간자 공격이 가능하고, 그러면 양자 채널의 성질과 무관하게 프로토콜이 깨진다.

도청 검출

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

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

이 보안은 수학적 어려움이 아니라 양자역학의 법칙, 즉 관측이 상태를 변화시킨다는 물리적 사실에 기반한다. 계산이 아무리 빨라져도 이 근거는 약해지지 않는다. 소인수분해가 쉬워진다고 해서 관측이 상태를 바꾸지 않게 되지는 않기 때문이다.

다만 「양자 컴퓨터로도 깰 수 없다」는 표현은 조건을 지운다. 안전성 증명은 모형 안에서 성립한다. 광원이 한 번에 광자 하나만 내보내고, 검출기가 명세대로 동작하며, 고전 채널이 인증되어 있고, 난수가 예측 불가능하다는 전제 위에서다.

실제 장비는 이 전제에서 벗어난다. 광원이 두 광자를 함께 내보내면 Eve가 하나를 몰래 가져가는 공격이 가능하고(그래서 미끼 상태 기법을 쓴다), 검출기에 강한 빛을 쏘아 눈멀게 하는 공격이나 장치의 타이밍·전력 소모를 재는 부채널 공격도 보고되어 있다. QKD가 지우는 것은 계산 가정이지 구현의 허점이 아니다.

광케이블을 통한 양자 키 분배(QKD)는 상용화되어 운용 중이다.