Future Cryptography

이번 포스팅은 양자를 이용한 암호 이야기를 적었습니다. 약간의 물리 내용이 포함되어 있습니다.

The Interferometer

• 위 그림과 같이 4개의 거울 (half, full)을 모퉁이에 설치 후 좌측 아래에서 오른쪽 방향으로 빛 레이저를 쏜다고하자
• Half 거울은 빛을 받았을 때 굴절될 확률 50%, 그냥 통과될 확률 50% 이다. (full 거울은 100% 굴절)
• 빛은 튕길 때 파장이 뒤집히는 특성이 있다.
• 오른쪽 위 거울에서 빛이 위쪽 방향으로 올라갈 확률이 있지만, 파장이 서로 간섭을 일으켜서 상쇄됨
• 따라서 오른쪽 위 거울에선 오른쪽으로만 100% 나옴

Bomb Tester

• 빛이 지나면 터지는 폭탄
• 폭탄이 정상일 때는 관찰자가 존재하는 것과 같은 효과이다 = 빛이 입자의 성질을 가짐
• 폭탄이 고장난 경우에는 빛이 파동의 성질을 가짐
• 빛이 파동인 경우에는 오른쪽 위 거울에서 반드시 오른쪽 방향으로만 빛이 나와야 한다
  • 위쪽방향으로 광자가 나오는 경우가 있다면, 폭탄이 고장나지 않았다는 의미이다.
• 폭탄이 고장나지 않았을 때, 테스터에 의해 폭탄이 터질 확률은 50%이다.
  • 역시 폭탄이 고장났는지 확인하는 방법은 실제로 터트리는 방법이..

A Crytosystem Using Interferometer

• 정보를 광자로 보낸다고 하자
• 누가 듣고 있는 사람이 있으면 위쪽으로 튀어나온다.
  • 빛이 입자의 성질을 가지게 되므로
• 이 방법으로 제3자가 정보를 엿듣고 있는지 검사할 수 있다.

Spin of Particles

• 전자가 돌면(spin) 작성의 성질을 갖게된다.
• 따라서 두 자석 사이에 spin 전자를 통과시키면 전자가 휜다.
• 실험결과 도착지점을 보니 정확히 2개다.
• 의미: 회전 방향이 확률적으로 존재하는데, 자석을 설치(detector)하는 순간 방향이 2개로만 정해진다.
• 전자를 측정하지 않을 때는 스핀 방향이 동시에 겹쳐있다. → NFA가 가능하다.

Quantum Computer

• NFA를 만들 수 있다
  • NFA는 Yes인 경우가 하나라도 있으면 Yes임
  • 관찰하는 순간 상태가 하나로 결정되는데, 이때 Yes가 높은 확률로 관찰되도록 증폭시키는 작업이 필요함 → 따라서 모든 NP 문제를 풀 수 있는지 없는지 모른다.
• Class QP: Quantum computer로 Polynomial Time에 풀 수 있는 문제
  • $P \subseteq QP \subseteq NP$
• 소인수분해는 QP 클래스 문제

Quantum Key Exchange

1. Sender는 입자에 4가지(상하좌우)에 스핀을 건다.(디텍터만 있으면 쉬움)
2. Receiver는 2가지 스핀 방향(가로, 세로)으로 읽는다.
   • 이때 receiver은 스핀 방향을 잘못읽었는지, 정확히 읽었는지 모른다
3. Sender는 실제로 자신이 어떤 방향(2가지, 가로 세로)로 스핀을 걸었는지 공유한다.
4. Receiver는 정확한 방향으로 읽은 원자 중 절반을 Sender와 스핀 상세 방향을 비교한다.
5. 비교한 비트가 모두 맞으면, 나머지 1/4 비트를 key로 사용한다.
   • 올바른 방향으로 읽은 비트(확률1/2) 중 sender와 스핀 상세 방향을 공유하지 않은 비트만 key로 사용

• 만약 중간에 엿듣는 사람이 있다고 하자.
  • 이 사람도 결국 특정 스핀 방향으로 디텍터한다.
• 엿듣는 사람이 입자를 디텍터하면 그 방향으로 스핀이 바뀐다.
• Receiver가 올바른 방향으로 읽었다고 하더라도, 중간에 엿듣는 사람 때문에 스핀이 바뀐 상태였다면 상세 정보가 틀릴 확률이 1/2이다.
• 상세 정보가 하나라도 틀리면 정보가 노출된 것이므로 key로 사용하지 않는다.