A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

본 논문은 평범한 모델에서 일방향 함수에 기반한 새로운 실용적이며 시뮬레이션-보안 양자 무관심 전송 프로토콜을 제시하며, 이는 동등성과 완화 추출 가능한 양자 비트 약속을 통한 오류 정정을 해결하면서도 실험적 구현의 효율성을 개선합니다.

핵심

마술 쇼에 있다고 상상해 보세요. 앨리스와 밥이라는 두 사람이 '비밀 선택' 게임을 하려고 합니다.

게임: 무지성 전송 (Oblivious Transfer)

이 게임에서 앨리스는 두 개의 비밀 메시지 (이를 메시지 A와 메시지 B라고 부르겠습니다) 를 가지고 있습니다. 밥은 그중 하나를 골라 보고 싶어 합니다.

• 조건 1: 밥은 나머지 다른 메시지를 엿볼 수 없어야 합니다.
• 조건 2: 앨리스는 밥이 어떤 것을 선택했는지 알 수 없어야 합니다.

이를 **무지성 전송 (Oblivious Transfer, OT)**이라고 합니다. 이는 안전한 컴퓨팅의 기본 구성 요소로, 판매자가 당신이 어떤 상자를 열었는지 모르고, 당신은 다른 상자를 열 수 없는 디지털식 '블라인드 박스'와 같습니다.

문제: 기존 프로토콜은 너무 취약했습니다

오랫동안 과학자들은 양자 역학 (광자라고 불리는 아주 작은 빛 입자를 이용) 을 사용하여 이를 수행하는 방법을 알고 있었습니다. 그러나 기존 방법들은 실제 실험실에서 구현하는 것을 불가능하게 만든 세 가지 주요 결함이 있었습니다.

1. 너무 민감함: 테이블이 살짝 흔들리는 것과 같은 미세한 노이즈로 인해 광자가 손실되거나 상태가 뒤집히기만 해도, 게임 전체를 다시 시작해야 했습니다. 이는 허리케인 속에서 카드 집을 짓는 것과 같았습니다.
2. 너무 무거움: 기존 방법은 단일 라운드당 약 **10 조 개 (10¹³)**라는 천문학적 수의 광자를 필요로 했습니다. 가장 빠른 레이저를 사용하더라도 이를 전송하는 데 몇 달이 걸렸습니다.
3. 너무 복잡함: 이들은 표준 상용 기술로 구현하기 어려운 복잡한 수학적 증명에 의존했습니다.

해결책: 실용적이고 '내노이즈' 프로토콜

이 논문의 저자들은 실용적이고 빠르며 견고한 이 게임의 새로운 버전을 구축했습니다. 몇 가지 간단한 비유를 사용하여 그들이 어떻게 했는지 설명해 보겠습니다.

1. '오류 수정 그물' (노이즈 처리)

이전 게임에서는 카드 한 장을 떨어뜨리기만 해도 덱 전체가 망가졌습니다. 이 새로운 게임에서는 앨리스와 밥이 안전 그물을 사용합니다.

• 비유: 앨리스가 종이에 쓴 메시지를 보내지만, 동시에 종이 찢어짐 여부를 알려주는 '체크섬 (비밀 코드)'도 함께 보낸다고 상상해 보세요.
• 작동 원리: 일부 광자가 손실되거나 뒤집히더라도 (노이즈), 프로토콜은 오류 수정 코드 (떨어진 카드를 잡는 그물과 같은) 를 사용하여 오류를 수정합니다. 이는 실험실이 완벽하지 않다고 해서 게임이 중단되지 않음을 의미합니다.

2. '한 번만 쓰는 패스' (효율성)

기존 프로토콜은 단 하나의 '앞면'을 얻기 위해 1 조 번이나 동전을 던져야 하는 게임과 같았습니다.

• 비유: 새로운 프로토콜은 느리고 구불구불한 길이 아닌 고속 열차와 같습니다.
• 결과: 10 조 개의 광자가 필요한 대신, 약 1 천만~3 천만 개만 필요합니다. 이로 인해 소요 시간은 몇 달에서 단 몇 초로 단축됩니다. 이는 배로 편지를 기다리는 것과 이메일을 보내는 것의 차이와 같습니다.

3. '마술 잠금 상자' (기술적 트릭)

게임을 안전하게 만들기 위해 그들은 특별한 유형의 양자 잠금 상자 (비트 커미트먼트라고 함) 를 사용합니다.

• 기존 방식: 잠금 상자가 너무 엄격해서, 만약 사기를 치려고 하면 시스템 전체가 무너졌습니다.
• 새로운 방식: 저자들은 '완화된' 잠금 상자를 발명했습니다.
  • 보통 하나의 변경 불가능한 비밀을 담고 있는 잠금 상자를 상상해 보세요.
  • 새로운 버전은 다음과 같습니다: "모든 잠금 상자가 완벽할 필요는 없습니다. 대부분이 단단히 잠겨 있기만 하면 됩니다."
  • 이 '완화된' 규칙은 기존 프로토콜의 무겁고 반복적인 단계를 건너뛰게 하여, 게임을 안전하게 유지하면서도 막대한 시간과 자원을 절약할 수 있게 합니다.

큰 그림

저자들은 이것이 종이 위에서만 작동함을 증명하는 데 그치지 않고, 이를 구축하기 위한 청사진을 제공했습니다.

• 그들은 현재 기술 (이미 도시에서 테스트 중인 양자 키 분배에 사용되는 것과 동일한 기술) 로 이 게임을 오늘날 플레이할 수 있음을 보여주었습니다.
• 그들은 필요한 광자의 수와 소요 시간을 정확히 계산하여, 안전한 다자간 양자 네트워크가 더 이상 먼 꿈이 아니라 실현 가능한 공학 프로젝트임을 입증했습니다.

요약하자면: 그들은 취약하고 느리며 이론적인 양자 게임을 실험실에서 실제로 구축할 수 있는 튼튼하고 빠르며 실용적인 도구로 바꾸었습니다.

기술 요약

기술 요약: 일방향 함수로부터의 양자 무관심 전송을 위한 실용적 프로토콜

1. 문제 제기

양자 무관심 전송 (QOT) 은 양자 환경에서 다자간 계산 (MPC) 을 구축하기 위한 근본적인 원시 연산입니다. 이전 연구들 [6, 7] 은 QOT 을 일방향 함수 (OWF) 와 양자 자원을 기반으로 구축할 수 있음을 입증했으나, 이러한 프로토콜들은 실험적 구현에 상당한 장벽에 직면해 있었습니다. 식별된 주요 문제점은 다음과 같습니다:

• 취약성: 기존 프로토콜들은 실험적 오류 (예: 상태 분배 중 비트 플립) 에 불내성적이었습니다.
• 구현 복잡성: OWF 를 블랙박스 방식으로 사용하지 않는 영지식 증명에 대한 의존성은 SHA 와 같은 실용적 양자 내성 해시 함수와의 통합을 비자명하게 만들었습니다.
• 비효율성: 이전 프로토콜들의 반복적 구조는 비현실적인 수량의 양자 상태 (예: 실행당 약 $10^{13}$ 개의 BB84 상태) 를 요구하여 전송 시간이 수 개월 단위로 소요되었습니다.

저자들은 현재 실험 설정에서 실현 가능한, 평면 모델 (plain model) 기반의 OWF 에 의존하는 잡음 내성 및 효율적인 QOT 프로토콜을 제공하고자 합니다.

2. 방법론 및 기술적 접근

제안된 솔루션은 새로운 암호학적 원시 연산인 동일성 (Equivocal) 및 완화 추출 가능 (Relaxed-Extractable, ERE) 비트 커밋먼트 방식을 도입함으로써 시뮬레이션 안전성을 갖춘 QOT 프로토콜을 구축합니다.

핵심 혁신:

• 완화 추출 가능성: 저자들은 QOT 의 안전성을 증명하는 데 완전한 추출 가능성이 엄격하게 필요하지 않음을 관찰했습니다. 그들은 "완화 추출 가능성"을 도입했는데, 이는 시뮬레이터가 커밋먼트의 대다수에 대해 커밋된 메시지를 추출할 수 있지만, 미미한 비율의 커밋먼트는 추출 불가능할 수 있음을 의미합니다. 이러한 완화는 더 효율적인 프로토콜 구조를 가능하게 합니다.
• 오류 정정을 통한 잡음 내성: 잡음이 없는 장치를 가정하던 이전 연구들과 달리, 본 프로토콜은 선형 오류 정정 코드 (특히 LDPC 와 같은 시ndrome 기반 코드) 를 통합합니다. 송신자는 인코딩된 값의 시ndrome 을 전송하여 수신자 (또는 시뮬레이터) 가 잡음이 존재하는 상황에서도 오류를 정정하고 올바른 시드를 추출할 수 있도록 합니다.
• 효율적인 시드 증류: 프로토콜은 BB84 상태에 프라이버시 증폭 기술 (Leftover Hash Lemma) 을 적용하여 무작위 시드를 증류합니다. 이러한 시드는 동일성 커밋먼트의 키로 사용됩니다. 이 구조는 이러한 시드를 가족 단위로 그룹화하여 병렬 커밋먼트를 가능하게 함으로써 이전 컴파일러에서 발견된 2 차 오버헤드를 피합니다.
• 커밋먼트 구조: ERE-커밋먼트 방식은 다음을 결합합니다:
  1. EqCommitment: 통계적으로 바인딩되는 표준 커밋먼트를 동일성 커밋먼트로 변환하는 컴파일러입니다. 저자들은 원래 컴파일러 [7] 를 수정하여 순차적 반복 횟수를 $\lambda$에서 단일 인스턴스로 줄여, 완전한 바인딩을 "완화 바인딩"과 교환합니다.
  2. ERE-커밋먼트: EqCommitment 방식을 사용하는 상위 수준 프로토콜입니다. 여기에는 송신자가 BB84 상태를 전송하고, 수신자가 측정 결과를 커밋하며, 검증 목적으로 부분 집합을 개방하는 챌린지 단계가 포함됩니다. 나머지 상태는 최종 메시지 암호화를 위한 시드 생성에 사용됩니다.

프로토콜 흐름 (프로토콜 1):

1. 양자 전송: Alice 는 Bob 에게 $2\lambda_{OT}$ 개의 BB84 상태를 전송합니다.
2. 커밋먼트: Bob 은 측정하고 ERE-커밋먼트 방식을 사용하여 자신의 기저 선택과 결과를 커밋합니다.
3. 챌린지: Alice 는 커밋먼트의 무작위 부분 집합 $T$에 챌린지를 보냅니다. Bob 은 실험적 오류 $\alpha$를 고려하여 Alice 가 보낸 상태와 일관성을 검증하기 위해 이를 개방합니다.
4. 키 생성: Alice 는 도전받지 않은 집합 $\bar{T}$에 대한 기저 정보를 전송합니다. Bob 은 일치하는 기저에 따라 $\bar{T}$를 집합 $I_0$와 $I_1$로 분할합니다.
5. 암호화: Alice 는 오류 정정 시ndrome 을 전송하고, 도전받지 않은 상태로부터 유도된 시드와 의사난수 생성기 (PRG) 를 사용하여 메시지 $m_0, m_1$을 암호화합니다.
6. 복호화: Bob 은 시ndrome 을 사용하여 오류를 정정하고 자신의 선택 비트 $b$에 해당하는 메시지를 복호화합니다.

3. 주요 기여

• 새로운 원시 연산: OWF 기반의 동일성 및 완화 추출 가능 (ERE) 비트 커밋먼트 방식의 정의 및 구축.
• 잡음 내성 QOT: 시ndrome 기반 오류 정정을 통해 실험적 오류 (비트 플립 및 다중 광자 사건) 를 명시적으로 처리하는 QOT 프로토콜로, 이는 이전 이론적 구축에는 없던 기능입니다.
• 효율성 개선: 커밋먼트 구조를 최적화하고 오류 정정을 활용함으로써, BB84 상태의 필요 수량을 [7] 의 약 $10^{13}$개에서 약 $10^7$개로 줄였습니다.
• 다중 OT 증류: 프로토콜의 단일 실행으로부터 여러 OT 키 ($n_{OT}$) 를 증류할 수 있게 하여, 효율적인 MPC 구현에 필수적입니다.
• 분석적 프레임워크: 물리적 오류율 ($\alpha$) 과 누출 ($\vartheta$) 을 고려하여 목표 보안 매개변수 (추적 거리 $\Delta$) 에 대한 필요한 양자 자원을 벤치마크하기 위한 분석적 식을 제공합니다.

4. 결과 및 성능

저자들은 목표 추적 거리 $\Delta \le 10^{-15}$에 대해 [7] 및 [21] 과 비교한 성능 벤치마크 (표 1) 를 제공합니다:

• 자원 감소: 필요한 BB84 상태 수 ($N_{BB84}$) 는 [7] 의 프로토콜인 $2.27 \times 10^{13}$개에 비해 이상적인 경우 약 $1.43 \times 10^6$개, 현실적인 잡음 환경에서는 $3.33 \times 10^7$개로 감소했습니다.
• 시간 효율성: 이러한 감소는 (1 MHz 속도를 가정할 때 1.43 초에서 43.6 초) 초 단위의 획득 시간 ($T_{acq}$) 으로 이어지는 반면, 이전 연구 [7] 는 약 8.6 개월이 소요될 것입니다.
• 보안성: 이 프로토콜은 평면 모델에서 악의적인 당사자에 대해 시뮬레이션 안전성이 증명되었으며, 양자 내성 일방향 함수의 존재에만 의존합니다.

5. 중요성 및 주장

이 논문은 이론적 양자 암호학과 실용적 구현 사이의 간극을 메운다고 주장합니다. 잡음이 없는 장치에 대한 요구 사항을 제거하고 양자 자원 오버헤드를 극적으로 줄임으로써, 저자들은 현재 기술로 QOT (및 더 나아가 양자 MPC) 의 실험적 구현이 가능하다고 주장합니다.

저자들은 그들의 구축이 랜덤 오라클 모델 (ROM) 기반 프로토콜 [21] 과 비교 가능한 BB84 비용을 달성하지만, ROM 대신 OWF 를 사용하는 평면 모델과 같이 엄격하게 더 약한 계산적 가정 하에 작동한다고 강조합니다. 그들은 명시적으로 "실용적 구현"을 목표로 하며, ROM 기반 커밋먼트의 고전적 효율성과 일치한다고 주장하는 것이 아니라, 현실 세계의 양자-안전 OT 를 위한 실현 가능한 경로를 제공한다고 명시합니다. 또한 이 작업은 MPC 에 필요한 시뮬레이션 기반 보안 보장을 훼손하지 않으면서 효율성 향상을 가능하게 하는 기술적 통찰인 완화 추출 가능성 속성이 안전성에 충분함을 강조합니다.