Isogeny Graphs in Superposition and Quantum Onion Routing

다음은 논문 "Isogeny Graphs in Superposition and Quantum Onion Routing"의 내용을 일상적인 비유를 사용하여 쉬운 언어로 번러한 것입니다.

핵심 아이디어: 익명 메시지를 위한 양자 "비밀 악수"

당신이 친구에게 비밀 편지를 보내고 싶지만, 중간에 있는 사람(예: 우체국이나 이웃)이 당신이 누구인지, 편지가 어디로 가는지 모르게 하고 싶다고 상상해 보세요. 디지털 세상에서 우리는 현재 온ion 라우팅(Tor 네트워크와 같은)이라고 불리는 시스템을 사용합니다.

고전적 방식의 작동 원리:
당신의 메시지를 여러 겹의 플라스틱으로 감싼 편지라고 생각해 보세요.

1. **당신(앨리스)**은 편지를 세 겹으로 감쌉니다. 첫 번째 층은 첫 번째 중계기(relay)를 향하고, 두 번째 층은 중간 중계기를 향하며, 세 번째 층은 당신의 친구(밥)를 향합니다.
2. 중계기 1은 첫 번째 층을 벗깁니다. 그들은 두 번째 중계기로 가는 주소는 볼 수 있지만, 앨리스가 누구인지나 밥이 누구인지는 알 수 없습니다.
3. 중계기 2는 두 번째 층을 벗깁니다. 그들은 밥의 주소는 볼 수 있지만, 앨리스가 누구인지는 모릅니다.
4. 밥은 마지막 층을 벗기고 편지를 읽습니다.

양자 문제:
이 논문의 저자들은 이와 동일한 시스템을 양자 컴퓨터를 위해 구축하려고 노력했습니다. 하지만 여기에는 큰 걸림돌이 있습니다.

• 고전적인 세상에서는 "공개 키(Public Key)" 암호화(누구나 잠글 수는 있지만, 주인만이 열 수 있는 열쇠를 가진 상자 같은 것)를 사용합니다. 이는 온ion 라우팅에 매우 유용합니다. 왜냐하면 아직 주인의 비밀 키를 모르는 상태에서도 층을 쌓아 잠글 수 있기 때문입니다.
• 양자 세상에서는 물리 법칙에 따라 대부분의 연산이 가역적(reversible)이어야 합니다. 이 점이 양자 암호를 온ion처럼 겹겹이 쌓는 것을 매우 어렵게 만듭니다. 보통 양자 암호는 양측이 이미 비밀 키를 공유하고 있어야 하는데, 이는 익명 네트워크의 목적에 어긋납니다.

해결책: 수학의 "마법 정원"

이를 해결하기 위해 저자들은 온ion 층의 "잠금장치"를 만드는 새로운 방법을 제안합니다. 표준적인 자물쇠 대신, 그들은 **아이디얼 클래스 그룹 작용(Ideal Class Group Actions)**이라는 고급 정수론 개념을 사용합니다.

비유: 마법 정원
특정한 수의 독특한 꽃들이 있는 거대한 정원을 상상해 보세요 (실제로는 수십억 개가 있겠지만, 여기서는 11개의 꽃이라고 가정합시다).

• 특별한 "마법 지팡이"(클래스 그룹 작용)가 있습니다.
• 지팡이를 꽃에 휘두르면, 그 꽃은 정원 안에 있는 다른 꽃으로 즉시 변합니다.
• 비밀: 이 지팡이는 가역적입니다. 지팡이를 한 번 휘두르면 꽃 A가 꽃 B가 됩니다. 다시 휘두르거나 "역방향 지팡이"를 사용하면, 꽃 B는 다시 꽃 A로 돌아갑니다.
• 어려운 점: 만약 내가 당신에게 꽃 A를 보여주며 이것이 꽃 B가 되었다고 말한다면, 컴퓨터(심지어 초강력 양자 컴퓨터라도)가 A에서 B로 가기 위해 지팡이를 몇 번 휘둘렀는지, 혹은 어떤 구체적인 방식으로 휘둘렀는지 알아내는 것은 믿을 수 없을 정도로 어렵습니다. 이것이 시스템을 안전하게 유지하는 "어려운 문제"입니다.

"양자 온ion"의 작동 방식

저자들은 온ion 층의 "층"이 이러한 마법 지팡이의 변환이라고 제안하는 프로토콜을 제안합니다.

1. 설정: 모두가 시작하는 꽃 하나(공개된 "j-invariant")에 동의합니다.
2. 체인:
   • **캐롤(수신자)**은 비밀스러운 횟수만큼 지팡이를 휘두릅니다. 그녀는 시작하는 꽃을 변형시켜 밥에게 보냅니다.
   • 밥은 자신만의 비밀스러운 횟수만큼 지팡이를 휘두릅니다. 그는 캐롤의 꽃을 변형시켜 앨리스에게 보냅니다.
   • **앨리사(송신자)**는 자신의 비밀스러운 횟수만큼 지팡이를 휘두릅니다. 그녀는 밥의 꽃을 변형시킵니다.
3. 돌아오는 길:
   • 앨리스는 꽃을 밥에게 다시 보냅니다. 밥은 자신의 "역방향 지팡이"를 사용하여 자신의 휘두름을 되돌립니다. 그는 그것을 캐롤에게 보냅니다.
   • 캐롤은 자신의 "역방향 지팡이"를 사용하여 자신의 휘두름을 되돌립니다.
4. 결과: 마법 지팡이는 "가환적(commutative)"이기 때문에(지팡이를 휘두르는 순서는 중요하지 않고, 총 휘두른 횟수만 중요함), 캐롤은 앨리스의 비밀스러운 휘두름에 의해서만 변형된 꽃을 갖게 됩니다.
5. 메시지: 앨리스는 이 최종적인 꽃을 자신이 꽃과 함께 보낸 양자 메시지를 여는 "키"로 사용합니다. 캐롤은 이 꽃을 사용하여 메시지를 풉니다.

왜 이것이 특별한가?
이 과정의 중간에서, "꽃"은 단순한 하나의 물체가 아닙니다. 그것은 양자 중첩(Quantum Superposition) 상태입니다.

• 꽃이 단 하나의 특정 종류가 아니라, 동시에 존재하는 모든 가능한 꽃들의 일렁이는 구름이라고 상상해 보세요.
• 메시지가 네트워크를 통과할 때, 메시지는 이 구름으로서 이동합니다.
• 만약 스파이(밥이나 해커)가 꽃이 무엇인지 보기 위해 들여다보려고 하면, 구름은 하나의 무작위한 꽃으로 붕괴됩니다. 그들은 송신자가 누구인지나 메시지가 어디로 가는지에 대한 어떤 단서도 얻을 수 없습니다. 그들은 오직 무작위한 꽃만을 보게 되며, 이는 메시지의 경로 나 비밀 키에 대한 아무런 힌트도 주지 않습니다.

"마법 지팡이"를 만드는 두 가지 방법

이 논문은 실제로 컴퓨터에서 이 시스템을 구축하는 두 가지 방법을 제안합니다.

1. 유니버설 오라클 (The "Black Box"): 마법 기계를 상상해 보세요. 이 기계에 꽃과 비밀 숫자를 입력하면, 즉시 새로운 꽃을 보여줍니다. 저자들은 표준 양자 게이트를 사용하여 이 기계처럼 작동하는 양자 회로를 구축하는 방법을 보여줍니다.
2. 연속적 워크 (The "Quantum Stroll"): 기계 대신, 꽃이 정원을 따라 "걷는" 것을 상상해 보세요. 저자들은 **연속 시간 양자 워크(Continuous-Time Quantum Walks)**를 사용하는 것을 제안합니다. 이것은 꽃이 정원 전체를 동시에 탐험하며 퍼져나가는 파동처럼 움직이는 것과 같습니다. 이것은 더 "네이티브"한 양자 접근 방식이며, 저자들은 별도의 논문에서 이를 탐구하고 있습니다.

"온ion" 예시 (5인 데모)

이것이 작동함을 증명하기 위해, 저자들은 앨리스, 밥, 캐롤, 데이브, 이브라는 5명의 인물이 등장하는 작은 컴퓨터 프로그램(Qiskit 사용)을 작성했습니다.

• 앨리스는 이브에게 메시지를 보내고 싶어 합니다.
• 밥, 캐롤, 데이브는 중간 전달자 역할을 합니다.
• 그들은 수학을 단순하게 유지하기 위해 꽃이 11개뿐인 아주 작은 버전의 "마법 정원"을 사용합니다.
• 프로그램은 꽃의 "구름"이 체인을 따라 위아래로 이동하는 것을 시뮬레이션합니다.
• 결과: 이브는 밥, 캐롤, 데이브가 최종 키가 무엇인지 전혀 알지 못함에도 불구하고, 성공적으로 비밀 키(앨리스가 만든 특정 꽃)를 수신합니다. 그들은 오직 무작위한 꽃이나 꽃의 구름만을 보았습니다.

이 논문이 중요한 이유

• 보안성: "마법 지팡이" 뒤에 숨겨진 수학은 미래의 양자 컴퓨터로도 깨뜨릴 수 없다고 믿어집니다. 이는 "포스트 양자(Post-Quantum)" 암호화의 후보가 됩니다.
• 익명성: 데이터가 중첩 상태로 이동하기 때문에, 단일 중계기는 송신자와 수신자를 연결할 수 없습니다.
• 단순성: 전체 시스템은 단 한 가지 유형의 수학 문제(클래스 그룹 작용)에 의존하므로, 다양한 암호 유형을 혼합하는 것보다 구축하기 쉽고 오류가 적습니다.

요약하자면, 이 논문은 양자 물리학과 고급 수학을 사용하여 낯선 이들의 네트워크를 통해 비밀 메시지를 보내는 새로운 방법을 발명했습니다. 이는 오늘의 "자물쇠와 열쇠"를, 경로가 가능성의 구름 속에 숨겨져 있어 누군가 훔쳐보려 해도 무작위한 꽃만을 보게 되는 "마법 정원"으로 대체합니다.