양자 컴퓨팅 7 - Quantum Key Distribution

양자 컴퓨팅 포스트 보러가기

0. Introduction

지난 포스트에서는 양자 얽힘이 무엇인지에 대해 알아보았다.

이 얽힘이라는 것을 이용하면 감청을 피하여 정보를 전달할 수 있다. 이에 대한 알고리즘이 BB84이다.

1. Key Distribution(키 분배)

키 분배란, 양측에서 외부 노출에 취약한 공개 채널을 통해 공통의 암호 키를 교환하는 것이다.

이를 암호화를 통해 진행하면 도청자는 키를 얻어낼 수 없다. 하지만 이 도청자가 존재하는지는 알 수 없다.

그런 의미에서 양자 키 교환은 감청의 여부까지 알 수 있다는 장점이 있다.

2. BB84

BB84의 핵심 아이디어는 이것이다. 큐비트를 측정하면 상태가 변하기 때문에, 큐비트를 전송해서 키 교환을 진행하면 누군가가 감청할 때마다 그 사실을 항상 알 수 있게 된다.

방법은 아래 네 가지의 순서대로 진행된다.

1. 엘리스와 밥은 두 종류의 기저를 사용한다. 그리고 아래 2번과 3번을 총 \(4n\)번 진행한다.(이때 사용되는 기저는 아래 이미지를 참고, \(n\)은 키의 크기이다.)
2. 엘리스는 둘 중 하나의 기저를 선택해서 큐비트를 보낸다. 이때 큐비트의 상태는 엘리스가 원하는 대로 결정된 상태이다.(0이나 1)
3. 밥은 둘 중 하나의 기저를 선택해서 측정한 뒤 그 결과를 기록한다.
4. 엘리스와 밥은 공개 채널을 통해 서로가 사용한 기저를 비교한다.

두 기저 중 전자를 \(+\), 후자를 \(\times\)라고 하고, 파란 색을 0, 오렌지 색을 1이라 하자.

2-1. 결과 분석

엘리스와 밥이 같은 기저를 선택했을 때는 같은 측정 결과를 얻게 된다.

엘리스와 밥이 다른 기저를 선택했을 때는 두 상태의 측정 결과가 \(\frac{1}{2}\)확률로 동일하게 나타난다.

따라서 키로 사용될 것은 같은 기저로 측정한 비트가 된다.

총 \(2n\)비트의 같은 기저로 측정된 비트를 얻을 수 있지만, 우리는 감청을 고려해야한다.

이브가 엘리스와 밥의 키 교환 채널을 감청한다고 가정해보자.

이브가 둘의 기저와 같은 기저를 사용한다면 둘은 동일한 비트를 얻을 수 있다. 하지만 이브가 다른 기저를 사용했을 때는 둘이 같은 비트를 얻을 확률은 \(\frac{1}{2}\)이다.

따라서, 감청이 없을 때는 \(2n\)개의 같은 기저로 측정된 비트가 \(100\%\) 같은 결과를 얻을 수 있고,
감청이 있을 때는 \(2n\)개의 같은 기저로 측정된 비트가 \(75\%\) 만큼 같은 결과를 얻을 수 있다.

이 결과를 바탕으로 키 교환을 할 때 채널의 오염 여부를 판단할 수 있게 된다.

3. Ekert Protocol(E91)

BB84에서는 \(n\)비트의 키를 교환하기 위해서는 \(4n\)개의 큐비트가 필요하다.

이번 장에서는 얽힘을 사용하여 \(3n\)개의 큐비트로 \(n\)비트의 키를 교환할 수 있는 ekert protocol을 소개한다.

Ekert protocol는 아래의 네 단계로 진행된다.

1. 엘리스와 밥은 얽힌 두 큐비트를 하나씩 나눈다. (예를 들어 엘리스가 얽힌 큐비트를 생성하고 그 중 하나를 밥에게 보낸다.)
2. 앨리스와 밥은 사전에 정의된 세 개의 기저 중 하나를 랜덤하게 선택한다. 그리고 측정한다.(예를들어 벨의 실험에서 사용된 기저, 그리고 이때 랜덤은 고전적인 컴퓨터에서 구현된 psuedo가 아닌 real quantum random을 말한다.)
3. 2번을 \(3n\)회 반복한다.
4. 최종적으로, 서로가 사용한 기저를 공개하고 기록한다.

3-1. 결과 분석

엘리스와 밥이 사용한 기저가 동일한 비트는 키로써 사용하고, 사용한 기저가 다른 비트는 감청 탐지용으로 사용한다.

우선 수학적으로 \(2n\)개의 탐지용 비트가 있을 것이다.

만약 감청되지 않았다면, 벨의 실험 결과에 따라 두 비트가 같을 확률은 \(\frac{1}{4}\)일 것이다.

그리고 만약 감청되었다면, 그 결과는 아래와 같다.

큐비트를 측정할 기저는 사전에 정해져 있기 때문에 감정자 이브도 세 기저 중 하나를 사용할 것이다.
이브가 엘리스 또는 밥이 사용한 기저 중 하나를 사용한다면(그 확률은 \(\frac{2}{3}\)), 그 결과 엘리스와 밥이 같은 결과를 얻을 확률은 \(\frac{1}{4}\)이다.
이브가 엘리스 또는 밥이 사용한 기저가 아닌 다른 하나를 사용한다면(그 확률은 \(\frac{1}{3}\)), 그 결과 앨리스와 밥이 같은 결과를 얻을 확률은 \(\frac{1}{4}\times \frac{1}{4} + \frac{3}{4}\times \frac{3}{4}\)이다.

따라서, 엘리스와 밥이 같은 결과를 얻을 확률은 \(\frac{2}{3}\times \frac{1}{4}+\frac{1}{3}\times (\frac{1}{4}\times \frac{1}{4} + \frac{3}{4}\times \frac{3}{4}) = \frac{3}{8}\)이다.

이브가 엘리스 또는 밥이 사용한 기저가 아닌 다른 하나를 사용한 것은 셋이 다른 기저를 사용한 것과 같다.
그렇다면 엘리스와 밥이 같은 비트를 얻게되는 경우는 1. 엘리스와 이브가 같고 이브와 밥이 같은 경우, 2. 엘리스와 이브가 다르고 이브와 밥이 다른경우이다.
전자는 \(\frac{1}{4}\times \frac{1}{4}\), 후자는 \(\frac{3}{4}\times \frac{3}{4}\)이다.

결과를 보면 알겠지만 감청이 되지 않은 경우(\(\frac{1}{4}\))와 감청된 경우(\(\frac{3}{8}\))이 다르다. 이를 통해 채널의 오염여부를 판단하게 된다.

후기) 이번엔 양자의 성질을 이용한 키 분배 알고리즘을 알아봤습니다. 실제로 BB84는 사용되고 있는 프로토콜이다. 다음 포스트에서도 이와 비슷하게 얽힘을 이용한 초고밀도코딩과 양자 순간이동에 대해서 다루도록 하겠습니다.

오타 혹은 잘못된 정보가 있다면 댓글 이메일 등등으로 알려주시면 감사하겠습니다. (꾸벅)