New Quantum Internet Applications via Verifiable One-Time Programs

1. 문제 제기 (Problem)

• 양자 인터넷의 현실적 한계: 양자 인터넷은 QKD(양자 키 분배) 및 위치 확인을 넘어 많은 혁신적인 응용을 약속하지만, 대부분의 기존 제안들은 현재 기술로는 구현 불가능한 정교한 양자 자원 (예: 얽힘 상태, 복잡한 양자 회로) 을 요구합니다.
• 단일 큐비트 기반 OTP 의 한계: 최근 BB84 와 같은 단일 큐비트 상태를 기반으로 한 '원회 프로그램 (One-Time Programs, OTP)' 연구가 활발하지만, 단일 큐비트의 결맞음 시간 (coherence time) 이 짧아 프로그램이 매우 짧은 시간 (ephemeral) 만 존재합니다. 이는 수신자가 즉시 온라인 상태여야 한다는 제약을 의미하며, 프로그램의 유효성을 미리 검증할 수 없어 악의적인 발신자가 잘못된 프로그램을 전송할 경우 프로토콜이 실패할 수 있습니다.
• 미리 등록 (Pre-registration) 없는 보안 계산의 부재: 기존 보안 계산 프로토콜은 참여자 등록이나 복잡한 설정 라운드가 필요하여, 실시간으로 참여하는 알 수 없는 다수의 사용자를 수용하는 '오픈' 환경에서의 응용 (예: 경매, 통계 집계) 에 한계가 있었습니다.

2. 방법론 (Methodology)

저자는 두 가지 새로운 암호학적 원시 (Primitive) 를 도입하여 위 문제를 해결합니다.

A. 검증 가능한 원회 프로그램 (Verifiable One-Time Programs, Ver-OTP)

• 개념: 수신자가 프로그램을 실행하기 전에, 해당 프로그램이 공개된 데이터와 관련된 특정 관계 (Relation) 를 만족하는 올바른 형태로 생성되었는지 검증할 수 있는 OTP 입니다.
• 구현 기술:
  • 가려진 회로 (Garbled Circuits) 와 NIZK: 올바른 가려진 회로 생성과 비밀 데이터에 대한 관계를 증명하기 위해 비상호적 영지식 증명 (NIZK) 을 사용합니다.
  • 검증 가능한 원회 메모리 (Verifiable OTM): OTP 의 핵심 구성 요소인 OTM 을 검증 가능하게 만들기 위해 Cut-and-Choose 기법과 비밀 공유 (Secret Sharing) 를 결합합니다.
    • 각 입력 라벨 (wire label) 을 $\zeta$개의 비밀 조각 (shares) 으로 분할합니다.
    • 각 조각을 별도의 단일 비트 입력 OTP 에 저장합니다.
    • 수신자는 무작위로 일부 OTP 를 열어 (Open) 유효성 증명을 확인합니다.
    • 검증이 통과하면 나머지 OTP 를 사용하여 원래 라벨을 재구성합니다.
    • 보안성: 비밀 공유의 임계값 (threshold) 을 설정하여 수신자가 두 가지 가능한 라벨 ($\kappa_0, \kappa_1$) 을 모두 복구하는 것을 물리적으로 불가능하게 만듭니다.

B. 오픈 보안 계산 (Open Secure Computation, OSC)

• 개념: 미리 등록이나 설정 라운드가 필요 없으며, 알려지지 않은 다수의 발신자가 알려진 수신자에게 입력을 보내고, 수신자가 이 입력들에 대해 함수를 계산할 수 있는 단일 라운드 (single-round) 보안 계산 모델입니다.
• 구현 기술:
  • 다중 키 동형 암호 (Multi-Key Homomorphic Encryption, MHE): 각 발신자가 자신의 공개키로 입력을 암호화합니다. 수신자는 여러 공개키로 암호화된 문서를 기반으로 동형 연산을 수행하여 결합된 암호문을 생성합니다.
  • Ver-OTP 와의 결합: 각 발신자는 자신의 비밀키를 사용하여 암호문을 부분적으로 복호화할 수 있는 Ver-OTP 를 생성하여 수신자에게 전송합니다.
  • 작동 방식: 수신자는 Ver-OTP 를 검증한 후, 검증된 입력들만 선택하여 MHE 를 통해 함수를 계산하고, 각 발신자의 Ver-OTP 를 실행하여 부분 복호화값을 받아 최종 결과를 얻습니다.
  • MHE 보안 강화: 기존 MHE 정의를 확장하여 (1) 보조 입력 허용, (2) 키 생성 시 인덱스 비의존성, (3) 부분 집합에 대한 계산 및 부분 복호화 허용, (4) 모든 부분 복호화값을 알지 못할 때의 시뮬레이션 가능성 등을 포함하도록 수정합니다.

3. 주요 기여 (Key Contributions)

1. Ver-OTP 의 도입: BB84 와 같은 단순한 단일 큐비트 상태와 하드웨어 가정 (수신자의 양자 자원) 만으로 구현 가능한, 검증 가능한 OTP 를 최초로 제안했습니다. 이는 양자 메모리가 짧더라도 유효한 프로그램을 제공할 수 있게 합니다.
2. 단일 라운드 OSC 프레임워크: 사전 등록이 불필요한 새로운 보안 계산 모델인 OSC 를 정의하고, Ver-OTP 와 MHE 를 결합하여 이를 구성했습니다.
3. 실용적인 양자 응용 사례 제시: OSC 를 활용하여 다음과 같은 단일 라운드 프로토콜을 구성했습니다:
   • 단일 라운드 밀봉 입찰 경매 (Sealed-bid Auctions): 입찰자들의 비밀을 유지하면서 한 번의 라운드로 승자와 가격을 결정합니다.
   • 정직한 다수결 단일 라운드 원자적 제안 (Honest-majority Atomic Proposals): 합의 프로토콜 (Consensus) 의 핵심 구성 요소로, 다수의 참여자가 동의한 값에 대한 서명을 한 번에 생성합니다.
   • 미리 등록 없는 차분 프라이버시 통계 집계: 사전 등록 없이 알 수 없는 참여자들이 데이터를 제출하고, 차분 프라이버시 (Differential Privacy) 를 보장하는 통계치를 한 번에 집계합니다.
   • 공정 교환 (Fair Exchange): 블록체인과 Ver-OTP 를 결합하여 신뢰할 수 있는 제 3 자 없이 디지털 자산을 교환하는 프로토콜을 제안했습니다.

4. 결과 및 성능 (Results)

• 양자 자원의 최소화: 복잡한 양자 상태가 아닌, 수백 미터 거리 전송이 가능한 단일 큐비트 (Single-qubit) 상태만 필요로 합니다. 이는 근미래 양자 기술 (Near-term quantum technology) 로 구현 가능함을 의미합니다.
• 보안성: 시뮬레이션 기반 보안 (Simulation-based security) 을 증명했습니다. 발신자가 악의적일 경우 검증 단계에서 걸러지며, 수신자가 악의적일 경우에도 MHE 와 Ver-OTP 의 보안성에 의해 입력 데이터가 유출되지 않습니다.
• 효율성: 양자 연산은 최소화하고, 다중 키 동형 암호, NIZK, 가려진 회로 등 고도로 최적화된 고전 암호학적 기술을 활용하여 전체 프로토콜의 실용성을 높였습니다.

5. 의의 및 의의 (Significance)

• 양자 인터넷의 실용화: 현재 기술 수준으로 접근 가능한 단순한 양자 상태 (BB84) 를 활용하여 기존에는 불가능했거나 복잡했던 보안 응용 (경매, 합의, 통계 등) 을 가능하게 함으로써 양자 인터넷의 실용적인 도입을 가속화합니다.
• 새로운 암호학적 원시: Ver-OTP 는 그 자체로 독립적인 가치가 있으며, 소프트웨어 라이선싱, Pay-to-use 프로그램 등 다양한 분야에서 활용될 수 있는 잠재력을 가집니다.
• 개방형 보안 컴퓨팅의 패러다임 전환: 사전 등록이 필요 없는 '오픈' 환경에서의 보안 계산을 가능하게 하여, 블록체인, 분산 시스템, 실시간 데이터 분석 등 동적인 네트워크 환경에 적합한 새로운 보안 프레임워크를 제시합니다.
• 향후 연구 방향 제시: CRS(공통 참조 문자열) 제거, UC(범용 구성) 보안 달성, 양자 입력/출력 지원, MHE 정의의 표준화 등 해결해야 할 중요한 과제를 제시하며 향후 연구의 방향성을 제시했습니다.

결론적으로, 이 논문은 복잡한 양자 기술 없이도 단순한 양자 상태를 활용하여 검증 가능한 보안 프로그램을 만들고, 이를 통해 단일 라운드로 다양한 보안 응용을 실현할 수 있는 새로운 프레임워크를 제시함으로써 양자 인터넷의 실용적 발전에 중요한 기여를 했습니다.