양자 불투명 전송을 이용한 비트 커밋먼트 기반 실험적 안전 다자간 연산

배경 및 학술적 계보

기원 및 학술적 계보

본 논문에서 다루는 안전 다자간 연산(MPC) 문제는 1980년대 초 암호학 분야에서 처음 등장했다. 1982년과 1986년 Andrew Yao의 선구적인 연구[1, 2]는 여러 당사자가 각자의 비공개 입력값을 서로에게 노출하지 않고 해당 입력값에 대한 함수를 공동으로 계산할 수 있는 이론적 기반을 마련했다. 이 개념은 특히 민감한 영역에서 개인 정보 보호 협업에 대한 근본적인 필요성에 의해 동기 부여되었다. 예를 들어, 금융 기관은 전체 고객 데이터베이스를 공개하지 않고 블랙리스트나 의심스러운 거래 패턴을 비교하여 사기를 탐지하고자 할 수 있다. 마찬가지로, 개인 정보 보호 기계 학습 또는 유전 데이터 분석에서 조직은 개별 데이터 세트를 노출하지 않고 공유된 민감한 데이터에 대한 모델을 학습하거나 분석을 수행해야 한다.

MPC를 실현하기 위한 중요한 구성 요소는 불투명 전송(OT)이다[6]. 수신자가 선택한 한 조각만 학습하도록 송신자가 데이터를 전송할 수 있게 하는 고전적 OT 프로토콜은 일반적으로 계산적 난제 가정에 의존한다[7, 8]. RSA 문제 또는 이산 로그 문제 해결의 어려움과 같은 이러한 가정은 보안의 기반을 형성한다. 그러나 양자 컴퓨팅, 특히 쇼어 알고리즘의 출현은 중요한 "고충점"을 드러냈다. 즉, 이러한 고전적 암호학적 가정은 양자 공격에 취약하다는 것이다. 이러한 취약성은 고전적 OT, 그리고 이를 기반으로 구축된 MPC의 보안이 충분히 강력한 양자 컴퓨터에 의해 근본적으로 파괴될 수 있음을 의미했다.

이러한 중대한 한계는 불투명 전송의 양자 유사체 탐색을 촉발하여 양자 불투명 전송(QOT) 프로토콜[9] 개발로 이어졌다. "노이즈가 있는 저장소 모델"[13-15]에서 광범위하게 연구된 초기 QOT 프로토콜은 양자 보안 통신 경로를 제공했다. 그러나 이러한 이전 QOT 접근 방식에는 고유한 근본적인 한계가 있었다. 즉, 보안 증명이 종종 적의 기술적 능력을 제한하는 데 의존한다는 것이다. 특히 적이 노이즈가 있거나 제한된 양자 메모리만 가지고 있다고 가정한다[17]. 이 가정은 양자 메모리 기술의 미래 발전이 이러한 프로토콜을 안전하지 않게 만들 수 있기 때문에 상당한 약점이다. 따라서 본 논문의 저자들은 이러한 제한적인 가정에 의존하지 않고, 충돌 저항 해시 함수와 같은 강력한 암호학적 기본 요소를 활용하여 보안을 달성하는 QOT 프로토콜을 개발해야 했다. 비트 커밋먼트는 다항 시간 복잡도를 가진 모든 고전적 또는 양자 공격에 대한 보안을 보장한다. 또한, QOT의 여러 실험적 시연에도 불구하고, QOT 기반 안전 다자간 연산의 실용적인 실제 구현 부족은 여전히 중요한 고충점으로 남아 있었으며, 본 논문은 이를 해결하고자 한다.

직관적인 도메인 용어

• 안전 다자간 연산(MPC): 친구 그룹이 서로의 실제 급여를 공개하지 않고 누가 가장 높은 소득을 가지고 있는지 알고 싶어한다고 상상해 보라. MPC는 모든 사람의 비공개 급여 정보를 처리하고 각 개인의 특정 소득을 다른 사람에게 노출하지 않고 가장 높은 급여만 출력할 수 있는 특별하고 신뢰할 수 있는 계산기와 같다. 이는 모든 개별 입력을 비밀로 유지하면서 계산에 협력하는 것이다.

• 불투명 전송(OT): 두 개의 비밀 메시지 $m_0$와 $m_1$을 제공하는 디지털 자판기를 생각해보라. 수신자인 당신은 $m_0$ 또는 $m_1$을 받을 수 있으며, 자판기는 선택한 메시지를 전달할 것이다. "불투명"이라는 부분은 자판기(송신자)가 당신이 어떤 메시지를 선택했는지 결코 알지 못할 것이며, 당신은 선택하지 않은 메시지에 대해 아무것도 배우지 못할 것이라는 것을 의미한다. 당신은 원하는 항목을 얻고 송신자는 당신의 선택을 알지 못한다.

• 비트 커밋먼트: 이는 변조 방지 봉투에 비밀 예측을 봉인하는 것과 같다. 이벤트가 발생하기 전에 종이에 예측(정보의 "비트")을 적고, 불투명 봉투에 봉인한 다음, 신뢰할 수 있는 제3자에게 전달한다. 이것이 "커밋먼트" 단계이다. 나중에 이벤트가 발생한 후, 제3자에게 봉투를 열어 예측을 공개하도록 요청할 수 있다. 이것이 "개봉" 단계이다. 핵심은 일단 커밋되면 예측을 변경할 수 없으며, 당신이 공개하기로 결정할 때까지 제3자는 예측을 알 수 없다는 것이다. 이는 예측이 이벤트 이전에 이루어졌고 변경되지 않았음을 보장한다.

• 개인 집합 교집합(PSI): 각자 고객 계정 목록을 가진 두 은행을 고려해 보라. 한 은행에는 의심스러운 계정의 블랙리스트가 있고, 다른 은행에는 신규 고객 목록이 있다. 그들은 각 은행이 전체 계정 목록을 서로에게 공개하지 않고 블랙리스트에 있는 신규 고객이 누구인지 알고 싶어한다. PSI는 각 목록의 다른 정보를 공개하지 않고 공통 계정(교집합)만 발견할 수 있게 하는 암호화 프로토콜이다. 이는 각 그룹의 전체 친구 목록을 공개하지 않고 두 그룹 간의 공통 친구를 찾는 것과 같다.

표기법 표

표기법	설명	유형
$x \in \{0,1\}^n$	인코딩을 위해 앨리스가 무작위로 선택한 비트 문자열	변수
$\theta \in \{0,1\}^n$	인코딩을 위해 앨리스가 무작위로 선택한 기저 문자열	변수
$|x\rangle_{\theta}$	앨리스가 보낸 편광 인코딩 단일 광자 상태	변수
$\hat{\theta} \in \{0,1\}^n$	측정을 위해 밥이 무작위로 선택한 기저 문자열	변수
$\hat{x} \in \{0,1\}^n$	밥의 측정 결과	변수
$c_i$	$i$-번째 라운드에 대한 밥의 커밋먼트	변수
$h$	암호화 해시 함수 (예: SHA-256)	매개변수
$r_i$	커밋먼트 $c_i$에서 밥이 사용한 무작위 비트 문자열	변수
$T \subset [n]$	테스트를 위해 앨리스가 무작위로 선택한 라운드 부분 집합	변수
$\alpha$	테스트 비트의 비율, $|T| = \alpha n$	매개변수
$c \in \{0,1\}$	밥이 원하는 메시지를 나타내는 밥의 선택 비트	변수
$m_0, m_1$	밥이 받을 두 개의 앨리스 메시지	변수
$m_c$	밥이 성공적으로 수신한 메시지 ( $m_0$ 또는 $m_1$ )	변수
Encode	오류 정정 코드 함수	매개변수
Decode	오류 정정 메시지 디코딩 함수	매개변수
$f_0, f_1$	개인 정보 증폭을 위한 해시 함수	매개변수
$\lambda$	메시지 $m_0, m_1$의 길이	매개변수
$n$	교환된 총 단일 광자 상태 수	매개변수
$N$	오류 정정 코드 길이	매개변수
$t$	수정 가능한 최대 비트 플립 오류 수	매개변수
$P_{\text{fpass}}$	앨리스의 테스트 중 거짓 실패 확률	매개변수
$P_{\text{fcorrect}}$	오류 정정 실패 확률	매개변수
$\text{cost}_{\text{cheat}}$	악의적인 밥이 성공적으로 속이기 위한 예상 비용	매개변수

Figure 1. 1-out-of-2 Oblivious Transfer

문제 정의 및 제약 조건

핵심 문제 공식화 및 딜레마

본 논문에서 다루는 핵심 문제는 강력한 양자 메모리를 가진 적을 포함한 모든 양자 공격에 대해 견고하게 안전하며, 안전 다자간 연산(MPC) 애플리케이션에 실용적인 양자 불투명 전송(QOT) 프로토콜의 개발 및 실험적 시연이다.

• 입력/현재 상태:
  • 두 명 이상의 당사자(예: 앨리스와 밥)가 비공개 데이터 세트를 보유한다.
  • 이들은 개인 정보 입력에 대한 추가 정보를 서로에게 노출하지 않고 해당 데이터 세트에 대한 함수를 공동으로 계산하기를 원한다 (예: 개인 집합 교집합, PSI에서 공통 요소 찾기).
  • MPC의 기본 구성 요소 역할을 하는 기존 고전적 불투명 전송(OT) 프로토콜은 계산적 난제 가정(예: RSA 문제 또는 이산 로그 문제)에 의존한다. 이러한 가정은 쇼어 알고리즘과 같은 양자 공격에 취약한 것으로 알려져 있다.
  • 어느 정도의 양자 보안을 제공하는 이전 QOT 프로토콜은 종종 "노이즈가 있는 저장소 모델" 하에서 작동했다. 이 모델은 적이 제한적이거나 노이즈가 있는 양자 메모리만 가지고 있다고 가정하는데, 이는 양자 기술의 발전으로 점점 비현실적이 되어가는 물리적 제약이다.
• 출력/목표 상태:
  • 완벽하고 오래 지속되는 양자 메모리를 가진 적을 포함한 모든 고전적 또는 양자 공격에 대해 보안을 달성하는 QOT 프로토콜. 이는 보안이 적의 기술적 한계에 대한 가정에 의존하지 않아야 함을 의미한다.
  • 프로토콜의 보안은 양자 보안 비트 커밋먼트와 같은 보다 근본적이고 강력한 암호학적 기본 요소에 기반해야 한다.
  • 이 QOT 프로토콜의 실험적 구현은 두 은행이 다른 고객 데이터를 공개하지 않고 공통 의심 계정을 안전하게 식별할 수 있도록 하는 등 실제 MPC 문제에 대한 실용성을 시연한다.
• 누락된 연결/수학적 격차: 정확한 누락된 연결은 이론적 양자 보안(종종 강력하고 때로는 비현실적인 물리적 가정에 의존함)과 실용적이고 강력한 구현 사이의 격차를 해소하는 QOT 프로토콜이다. 이전 QOT 구현은 이론적이거나 노이즈가 있는 저장소 모델로 인해 제한되었다. 본 논문은 물리적 한계가 아닌 암호학적 기본 요소에 의해 보안이 보장되는 QOT 프로토콜을 제공하고, 이를 통해 미래의 양자 메모리 발전에 대한 복원력을 확보한 다음, 실제 적용 가능성을 시연하는 것을 목표로 한다.

이전 연구자들이 겪었던 중심 딜레마는 강력하고 무조건적인 양자 보안을 달성하는 것과 실용적인 실행 가능성을 유지하는 것 사이의 고통스러운 절충이었다. 고전적 OT는 효율적이지만 양자 공격에 취약하다. 초기 QOT 프로토콜은 "노이즈가 있는 저장소 모델"에 의존하는 대가로 양자 보안을 제공했다. 이는 딜레마를 야기한다. 한 측면(예: 양자 메모리 기술)을 개선하면 노이즈가 있는 저장소 모델에 의존하는 프로토콜의 보안이 직접적으로 파괴된다. 과제는 모든 강력한 양자 적에 대해 안전하며(즉, 노이즈 저장소로 제한되지 않음) 실질적인 계산 또는 통신 오버헤드 없이 실제 시나리오에서 구현하고 사용할 수 있을 만큼 효율적인 QOT 프로토콜을 설계하는 것이다. 저자들은 비트 커밋먼트를 활용하여 이를 해결하는데, 이는 더 강력한 보안 기반을 제공하지만 자체적인 구현 복잡성을 야기한다.

제약 조건 및 실패 모드

저자들은 QOT 프로토콜 개발 및 구현 중에 몇 가지 가혹하고 현실적인 장벽과 제약 조건에 직면했다.

• 양자 하드웨어의 물리적 한계:

  • 불완전한 단일 광자 소스: 실제 양자 장치, 예를 들어 앨리스의 레이저 소스는 완벽한 단일 광자를 방출하지 않는다. 일반적으로 약한 일관 상태를 사용하여 근사하며, 이는 다중 광자 또는 전혀 광자가 방출되지 않을 확률이 0이 아님을 초래할 수 있다. 이러한 불완전성은 악의적인 밥이 악용할 수 있는 치명적인 취약점이다(예: 광자 수 분할 공격).
  • 전송 손실 및 검출기 노이즈: 광자는 흡수 및 산란으로 인해 양자 채널을 통한 전송 중에 필연적으로 손실된다. 또한, 밥의 단일 광자 검출기(SPD)는 완벽하지 않으며 "암흑 계수"(입력 광자 없이 발생하는 잘못된 검출)와 제한된 검출 효율성을 겪는다. 이러한 요인은 전반적인 채널 손실에 기여하고 비트 오류율을 증가시킨다.
  • 비트 플립 오류: 전송 노이즈와 측정 오류는 양자 통신에 내재되어 있어 비트 플립을 초래한다. 이러한 오류는 프로토콜의 중요한 검증 단계(예: QOT 프로토콜의 3-5단계에서 앨리스의 테스트)에서 실패를 유발하거나 밥이 9단계에서 의도한 메시지를 성공적으로 디코딩하는 것을 방해할 수 있다. 총 실패 확률은 $P_{failed} \leq P_{fpass} + P_{fcorrect}$로 제한된다.
  • 광 감쇠: 실험에서 입증된 바와 같이, 광 감쇠(채널 손실) 증가는 검출된 광자 수를 직접적으로 감소시키며, 이는 QOT 프로토콜의 유효 코드율(처리량)을 낮춘다. 이는 프로토콜이 작동할 수 있는 실제 거리와 속도를 심각하게 제한한다.

• 적의 능력 및 보안 요구 사항:

  • 무제한 양자 메모리: 이전 QOT 프로토콜과 달리, 본 연구는 적이 노이즈가 있거나 제한된 양자 메모리를 가지고 있다고 명시적으로 가정하지 않는다. 이는 악의적인 밥이 완벽하고 오래 지속되는 양자 메모리를 소유하여 앨리스가 자신의 기저를 공개할 때까지 수신된 큐비트를 무기한 저장하고 측정을 지연시킬 수 있는 경우에도 프로토콜이 안전해야 함을 의미한다. 이는 훨씬 더 강력한 보안 요구 사항이다.
  • 광자 수 분할(PNS) 공격: 악의적인 밥은 앨리스의 약한 일관 광원으로부터 다중 광자 방출을 이용하여 PNS 공격을 시도할 수 있다. 그는 즉시 하나의 광자를 측정하고 나머지를 양자 메모리에 저장한 다음, 앨리스가 자신의 측정 기저를 발표한 후 저장된 광자를 측정하여 자신이 알지 못해야 할 정보를 학습할 수 있다. 프로토콜은 이러한 공격을 탐지하고 방지하기 위한 메커니즘(예: 디코이 상태 QKD)을 포함해야 한다.
  • 비트 커밋먼트 우회: 악의적인 밥은 앨리스가 올바른 기저를 공개할 때까지 측정을 지연시켜 비트 커밋먼트 체계를 속이려 할 수 있다. 이렇게 하면 그는 앨리스의 두 메시지($m_0$ 및 $m_1$)를 모두 학습할 수 있다. 프로토콜은 밥이 커밋먼트 검증(3-5단계)을 우회하는 데 드는 계산 비용이 천문학적으로 높도록 보장해야 하며, 이러한 공격을 실질적으로 불가능하게 만들어야 한다. 본 논문은 이 "속임수 비용"을 약 $3.8 \times 10^{12}$로 계산하는데, 이는 공격자가 프로토콜 실행당 1초가 걸린다면 성공적으로 속이기 위해 약 120,000년이 필요함을 시사한다.

• 계산 및 데이터 기반 제약 조건:

  • 오류 정정 오버헤드: 비트 플립 오류를 상쇄하기 위해 고전적 오류 정정 코드(예: BCH 코드)가 필요하다. 이는 인코딩 및 디코딩에 대한 계산 오버헤드를 도입하고 오류율의 신중한 관리를 요구한다. 오류율이 특정 임계값을 초과하면 프로토콜은 중단해야 한다.
  • 개인 정보 증폭: 밥이 선택하지 않은 메시지에 대해 얻는 정보가 무시할 수 있을 정도로 적도록 보장하기 위해 범용 해시 함수를 사용한 개인 정보 증폭이 적용된다. 이는 또 다른 수준의 계산 처리를 추가한다.
  • 실제 애플리케이션을 위한 확장성: 프로토콜은 개인 집합 교집합(PSI) 애플리케이션에서 파티당 $10^5$개의 요소와 같은 대규모 데이터 세트를 처리하도록 확장 가능해야 한다. 본 논문은 실용적인 통신 비용(예: $10^5$개 요소에 대해 20MB)과 런타임(1Gbps 네트워크에서 0.4초 미만)을 시연하지만, 더 큰 데이터 세트 또는 더 복잡한 MPC 함수로의 확장은 지속적인 과제로 남아 있다.
  • 통합 복잡성: QOT 프로토콜은 독립형 솔루션이 아니라 다른 고전적 암호학적 기본 요소(예: 불투명 의사 난수 함수, OPRF 및 비트 커밋먼트용 해시 함수) 및 고전적 통신 채널과 통합되어야 하며, 이는 전반적인 시스템 설계 및 구현 복잡성을 증가시킨다.

왜 이 접근 방식인가

선택의 불가피성

비트 커밋먼트 체계로 강화된 이 특정 양자 불투명 전송(QOT) 프로토콜의 채택은 양자 위협 환경에서 안전 다자간 연산(MPC)의 엄격한 보안 요구 사항을 고려할 때 단순한 선호가 아니라 불가피성이었다. 저자들은 전통적인 "최첨단"(SOTA) 방법, 주로 고전적 불투명 전송(OT) 프로토콜이 근본적으로 불충분하다는 것을 인식했다. 고전적 OT는 RSA 문제 또는 이산 로그 문제와 같은 계산적 난제 가정에 의존한다. 그러나 이러한 가정은 쇼어 알고리즘과 같은 양자 공격에 취약한 것으로 알려져 있으며, 이는 이러한 암호학적 기반을 효율적으로 파괴할 수 있다. 이러한 취약성은 고전적 OT를 양자 적에 대한 장기적인 보안을 요구하는 애플리케이션에 부적합하게 만든다.

더욱이, 양자 역학을 보안에 활용하려 했던 이전 QOT 프로토콜조차도 부족한 것으로 밝혀졌다. 이러한 초기 양자 접근 방식 중 다수는 "노이즈가 있는 저장소 모델" 하에서 작동했으며, 적의 양자 메모리가 본질적으로 노이즈가 있거나 제한적이라고 가정했다. 저자들은 명시적으로 이러한 프로토콜이 "대규모의 안정적인 양자 메모리가 사용 가능해지면 취약해진다"고 언급한다[17]. 이러한 방법이 불충분하다는 것을 깨달은 정확한 순간은 적의 기술(예: 노이즈가 있는 양자 메모리)의 한계에 의존하는 것이 약한 보안 태세라는 이해에서 비롯되었을 가능성이 높다. 진정으로 강력한 솔루션은 고급의 안정적인 양자 메모리를 가진 적에 대해서도 보안을 보장해야 한다. 따라서 이러한 제한적인 가정을 하지 않고 대신 비트 커밋먼트와 같은 보다 강력한 암호학적 기본 요소에 보안을 구축하는 QOT 프로토콜은 모든 고전적 또는 양자 공격에 대해 무조건적인 보안을 달성하기 위한 유일하게 실행 가능한 경로가 되었다.

비교 우위

이 QOT 프로토콜은 보안 모델을 근본적으로 변경함으로써 이전의 황금 표준에 비해 질적인 우수성을 보여준다. "노이즈가 있는 저장소 모델"에 의존했던 이전 QOT 프로토콜과 달리, 이 접근 방식은 적의 기술적 능력을 제한하지 않는다. 대신, 적이 대규모의 안정적인 양자 메모리를 가지고 있더라도 지연 측정 공격에 대해 보안을 보장하기 위해 비트 커밋먼트 체계를 사용한다. 이것은 적의 한계에 기반한 보안에서 암호학적 기본 요소에 기반한 보안으로 이동하는 중요한 구조적 이점이다.

이 프로토콜의 보안은 충돌 저항 해시 함수로부터 구성될 수 있는 "양자 보안 비트 커밋먼트 체계"에 뿌리를 두고 있다. 논문의 표 2와 그림 5에 자세히 설명된 바와 같이, 이는 고전적 또는 심지어 사후 양자 OT를 뒷받침하는 "구조화된" 문제(예: 격자 기반 또는 이산 로그)에 비해 더 근본적이고 약한 암호학적 가정에 의존하는 "비구조화된" 대칭 키 문제에 프로토콜의 보안을 배치한다. 이는 구조화된 문제를 파괴할 수 있는 미래 발전에 대한 복원력을 제공하는 기초 보안 보장 측면에서 이 방법을 압도적으로 우수하게 만든다.

정량적으로, 본 논문은 악의적인 밥이 비트 커밋먼트 체계를 우회하고 앨리스의 두 메시지를 모두 훔치기 위해 극복해야 하는 엄청난 비용을 보여준다. 계산된 "속임수 비용"은 약 $3.8 \times 10^{12}$ (방정식 6)이다. 직관적인 이해를 제공하기 위해, 프로토콜의 한 번의 실행이 1초가 걸린다면, 밥은 평균적으로 성공적으로 속이기 위해 약 120,000년이 필요할 것이다. 이는 "실질적으로 모든 현실적인 배포에서 거의 무시할 수 있는" 수준의 보안으로, 고전적 또는 노이즈 저장소 모델 QOT 프로토콜이 제공할 수 있는 것보다 훨씬 뛰어난 수준이다. 강력하고 검증 가능한 암호학적 기본 요소에 기반한 이러한 구조적 이점은 기술적 가정보다는 질적으로 우수하게 만든다.

제약 조건과의 정렬

선택된 QOT 프로토콜은 비트 커밋먼트 체계로 보강되어 안전 다자간 연산(MPC) 문제에 대해 일반적으로 정의되는 가혹한 요구 사항과 완벽하게 일치한다. 2단계의 제약 조건에 강력한 개인 정보 보호, 양자 적에 대한 보안, 실용적인 실험적 실행 가능성에 대한 필요성이 포함된다고 가정하면, 이 솔루션은 이러한 요구 사항과 완벽한 "결혼"을 형성한다.

1. 개인 정보 보호: MPC, 특히 개인 집합 교집합(PSI)의 핵심은 개별 비공개 데이터를 공개하지 않고 협업 계산을 가능하게 하는 것이다. QOT 프로토콜은 송신자가 선택한 조각만 수신자가 학습하도록 데이터를 전송할 수 있게 함으로써 본질적으로 이를 달성하며, 송신자는 선택에 대해 알지 못한다(그림 1). PSI에 대한 적용은 두 은행이 "다른 어떤 데이터도 공개하지 않고" 공통 의심 계정을 식별하는 것으로, 이 개인 정보 보호 제약 조건을 직접적으로 충족한다.
2. 양자 보안: 현대 암호학에서 가장 중요한 요구 사항은 양자 공격에 대한 복원력이다. 고전적 OT 프로토콜은 쇼어 알고리즘에 취약한 가정에 의존하기 때문에 여기서 실패한다. 노이즈 저장소 모델의 이전 QOT 프로토콜도 고급 양자 메모리를 가진 적에 대해 부적절하다. 그러나 이 프로토콜은 명시적으로 "다항 시간 복잡도를 가진 모든 고전적 또는 양자 공격에 대해 안전하다"(4페이지, 2.1절)고 설계되었으며, 결정적으로 "적의 노이즈가 있거나 제한된 양자 메모리에 대한 가정에 의존하지 않는다"(9페이지, 2.1절). 비트 커밋먼트 체계의 통합과 디코이 상태 QKD 시스템(광자 분할 공격 방지용)의 사용은 양자 위협 제약 조건을 직접적으로 해결하고 극복하는 고유한 속성이다.
3. 실용적인 실험적 실행 가능성: 본 논문은 QOT의 실험적 구현으로, 실제 문제(PSI)에 대한 "최초의 실용적인 적용"을 시연한다. 결과는 프로토콜이 최대 $10^5$개의 요소에 대한 집합 크기에 대해 확장 가능하며, 통신 비용(예: $10^5$개 요소에 대해 20MB)과 런타임(1Gbps 네트워크에서 0.4초 미만)이 "이미 많은 실제 애플리케이션에 실용적"임을 보여준다(8페이지, 2.3절). 이러한 직접적인 실험적 검증 및 시연된 확장성은 실용적 실행 가능성 제약 조건과의 정렬을 확인한다.

대안의 거부

본 논문은 특히 고전적 OT와 노이즈 저장소 모델에 기반한 이전 QOT 프로토콜을 포함하여 대안적 접근 방식을 거부하는 이유를 명확하게 설명한다.

1. 고전적 불투명 전송(OT): 고전적 OT를 거부하는 주된 이유는 양자 공격에 대한 고유한 취약성이다. 저자들은 고전적 OT 프로토콜의 보안이 "쇼어 알고리즘을 이용한 양자 공격에 취약한 RSA 문제 및 이산 로그와 같은 추정되는 계산적 난제 가정[7, 8]에 기반한다"(3페이지, 1절)고 명시한다. 사후 양자 시대에 장기적인 보안을 요구하는 애플리케이션의 경우, 고전적 OT는 단순히 실행 가능하지 않다.
2. 이전 양자 불투명 전송(QOT) 프로토콜 (노이즈 저장소 모델): 고전적 방법보다 발전했지만, "노이즈가 있는 저장소 모델"[13-15]에서 광범위하게 연구된 이전 QOT 프로토콜도 불충분한 것으로 간주된다. 본 논문은 명시적으로 "대규모의 안정적인 양자 메모리가 사용 가능해지면 취약해진다"[17]고 언급한다(3페이지, 1절). 저자들의 프로토콜은 적의 양자 메모리에 대한 한계를 가정하지 않음으로써 "노이즈 저장소에서만 안전했던 이전 접근 방식을 능가하도록" 설계되었다(2페이지, 초록). 핵심 차이점은 밥의 측정 기저를 비트 커밋먼트 체계를 통해 의무적으로 커밋하는 것으로, 이는 적이 완벽한 양자 메모리를 가지고 있을 때 보안을 손상시키는 지연 측정 공격을 방지한다(4페이지, 2.1절; 12페이지). 이러한 거부는 적이 노이즈가 있거나 제한된 양자 메모리를 가지지 않는 더 강력한 적 모델에 기반한다.

본 논문은 이러한 것들이 불투명 전송 또는 안전 다자간 연산의 근본적인 암호학적 기본 요소에 해당하지 않기 때문에 GAN, 확산 모델 또는 트랜스포머와 같은 다른 인기 있는 기계 학습 또는 데이터 처리 접근 방식을 논의하지 않는다. 여기서 제시된 실험은 양자 보안 MPC를 위한 기초 단계이다.

Figure 5. Hierarchy of cryptographic assumptions

수학적 및 논리적 메커니즘

마스터 방정식

본 논문의 핵심 수학적 엔진, 특히 보안 주장과 관련하여, 악의적인 밥이 프로토콜을 성공적으로 속이기 위한 최소 예상 비용을 계산하는 것으로 요약된다. 이 값, 즉 $cost_{cheat}$는 적의 최적 전략을 나타내며, 프로토콜의 양자 불투명 전송(QOT)에 대한 특정 유형의 공격에 대한 견고성을 정량화한다.

$$ cost_{cheat} = \min_{0 \le s_1 \le n, 0 \le s_2 \le 2(N-t)-s_1} \frac{2^{s_2}}{P_{bypass, s_1} \cdot P_{cheat, s_1, s_2}} $$

이 방정식은 궁극적인 보안 지표를 정의하지만, 그 구성 요소인 $P_{bypass, s_1}$ 및 $P_{cheat, s_1, s_2}$ 자체는 $P_{fpass}$ 및 $P_{fcorrect}$와 같은 다른 근본적인 계산에 의존하는 복잡한 확률이며, 커밋먼트 검증을 위한 $Pr[check\ passed]$이다. 이러한 상호 연결된 방정식은 프로토콜의 무결성을 평가하기 위한 수학적 백본을 집합적으로 형성한다.

항별 분석

마스터 방정식과 그 기본 구성 요소를 분석하여 각 변수, 계수 및 수학적 연산자를 설명해 보자. 실험 구현에 사용된 매개변수는 $\lambda = 256$ (메시지 길이), $n = 2044$ (단일 광자 상태 수), $\alpha = 1/2$ (테스트 비트 비율), $\beta = 0.95$ (최소 허용 비트 일치 비율), $N = 511$ (오류 정정 코드 길이), $t = 30$ (수정 가능한 최대 비트 플립 오류)이다.

• $\min_{0 \le s_1 \le n, 0 \le s_2 \le 2(N-t)-s_1}$: 최소화 연산자이다.

  • 수학적 정의: $s_1$ 및 $s_2$의 모든 유효한 조합을 반복하여 뒤따르는 표현식의 가장 작은 값을 찾는다.
  • 물리적/논리적 역할: 이는 악의적인 밥의 최적 전략을 나타낸다. 적으로서 밥은 속이기 위한 "비용"을 최소화하는 방식으로 지연할 큐비트 수($s_1$)와 추측할 비트 수($s_2$)를 선택할 것이다. 이 최소값을 찾음으로써 프로토콜 설계자는 가장 효율적인 속임수 전략조차도 엄청나게 비싸다는 것을 보장한다.
  • 왜 최소화인가?: 목표는 프로토콜 보안에 대한 최악의 시나리오를 설정하는 것이다. 속임수가 적의 최적 전략 하에서도 비싸다면 프로토콜은 견고하다.

• $s_1$: 측정을 지연하는 밥의 큐비트 수.

  • 수학적 정의: 정수 변수, $0 \le s_1 \le n$.
  • 물리적/논리적 역할: 이는 악의적인 밥의 전략적 선택이다. 그는 앨리스의 인코딩 기저를 나중에(프로토콜의 6단계) 알게 되어 허용된 것보다 더 많은 정보를 얻을 수 있기를 바라며 일부 큐비트의 측정을 지연할 수 있다.

• $s_2$: 추측하는 밥의 비트 수.

  • 수학적 정의: 정수 변수, $0 \le s_2 \le 2(N-t)-s_1$.
  • 물리적/논리적 역할: 또 다른 전략적 선택인 악의적인 밥. 일부 정보를 얻은 후 측정을 지연한 후에도 그는 두 앨리스 메시지를 완전히 재구성하기 위해 추가 비트를 추측해야 할 수 있다. 상한 $2(N-t)-s_1$은 오류 정정 능력과 이미 획득한 비트를 고려하여 두 메시지에 필요한 총 정보를 반영한다.

• $2^{s_2}$: $s_2$ 비트를 추측하는 계산 비용.

  • 수학적 정의: 지수 항.
  • 물리적/논리적 역할: 이는 밥이 $s_2$ 비트를 추측해야 하는 경우 지출해야 하는 계산 노력의 양을 정량화한다. 각 비트에는 두 가지 가능성이 있으므로 $s_2$ 비트에는 $2^{s_2}$ 조합이 있다. 이 항은 밥의 추측 전략에 대한 "벌칙" 역할을 한다.
  • 왜 지수인가?: 추측은 가능성 측면에서 곱셈 과정이다. 비트 하나를 추측하면 2가지 옵션이 있다. 두 개를 추측하면 $2 \times 2 = 4$가지 옵션이 있고, 계속된다.

• $P_{bypass, s_1}$: $s_1$ 측정 지연을 통해 밥이 초기 커밋먼트 검사를 우회할 확률.

  • 수학적 정의: 논문 방정식 3에 의해 정의됨:
    $$ P_{bypass, s_1} = \sum_{i=0}^{s_1} \binom{s_1}{i} \binom{n-s_1}{\alpha n - i} \text{Pr[check passed]} $$
  • 물리적/논리적 역할: 이는 프로토콜의 중요한 커밋먼트 테스트 단계(3-5단계)에서 악의적인 밥이 앨리스를 성공적으로 속일 확률이다. 밥은 $s_1$ 큐비트에 대한 자신의 측정값을 숨기려고 시도하지만, 여전히 앨리스의 검증 테스트를 통과해야 한다.
  • $P_{bypass, s_1}$ 내의 항:
    • $\sum$: 합계, 밥이 지연된 큐비트와 즉시 측정된 큐비트 세트에 속하는 "운 좋은" 비트의 다양한 조합을 통해 검사를 통과할 수 있기 때문에 사용된다.
    • $i$: 합계의 인덱스로, $s_1$ 지연 큐비트 중에서 테스트 세트의 일부이고 검사 통과에 기여하는 $i$ 비트를 선택하는 방법의 수를 나타낸다.
    • $\binom{s_1}{i}$: $s_1$ 지연 큐비트에서 $i$ 비트를 선택하는 방법의 수.
    • $\binom{n-s_1}{\alpha n - i}$: 밥이 즉시 측정한 $n-s_1$ 큐비트에서 나머지 $\alpha n - i$ 비트를 테스트 세트로 선택하는 방법의 수.
    • $\text{Pr[check passed]}$: 특정 수의 일치하는 비트가 주어졌을 때 앨리스의 테스트(4단계)가 통과할 확률이다. 이는 논문 방정식 4에 의해 정의된 조건부 확률이다:
      $$ \text{Pr[check passed]} = \begin{cases} 1 & \text{if } \alpha n - i \ge \beta \alpha n \\ \sum_{j=\lceil i-(1-\beta)\alpha n \rceil}^{\alpha n - i} \binom{\alpha n - i}{j} \frac{1}{2^{\alpha n - i}} & \text{otherwise} \end{cases} $$
      • 물리적/논리적 역할: 이는 밥이 속이려 해도 앨리스의 검증 기준을 여전히 충족해야 함을 보장한다. 테스트 세트의 올바른 비트 수($\alpha n - i$)가 이미 임계값($\beta \alpha n$)보다 높으면 검사가 확률 1로 통과한다. 그렇지 않으면 밥은 차이를 메우기 위해 추측(확률 $1/2^{\alpha n - i}$)에 의존해야 하며, $j$ 성공적인 추측에 대해 합산한다. $\lceil \dots \rceil$는 최소 필요한 추측에 대한 정수 수를 보장한다.

• $P_{cheat, s_1, s_2}$: $s_1$ 지연 측정 및 $s_2$ 추측이 주어졌을 때 밥이 두 메시지를 성공적으로 재구성할 확률.

  • 수학적 정의: 논문 방정식 5에 의해 정의됨:
    $$ P_{cheat, s_1, s_2} = \frac{1}{2^{(1-\alpha)n}} \sum_{i=2(N-t)-s_1-s_2}^{(1-\alpha)n} \binom{(1-\alpha)n}{i} $$
  • 물리적/논리적 역할: 이는 커밋먼트 검사를 우회한 후 속임수 전략의 두 번째 단계에서 밥이 성공할 확률이다. 이는 그가 두 메시지 $m_0$와 $m_1$을 모두 디코딩할 만큼 충분한 정보를 얻을 가능성을 정량화한다.
  • $P_{cheat, s_1, s_2}$ 내의 항:
    • $(1-\alpha)n$: 메시지 자체를 전달하는 비테스트 세트의 비트 수.
    • $2(N-t)-s_1-s_2$: 밥이 $s_1$ 비트를 지연시키고 $s_2$ 비트를 추측한 것을 고려하여, 두 메시지를 성공적으로 디코딩하기 위해 $(1-\alpha)n$ 비테스트 비트에서 필요한 "올바른" 비트의 최소 수. 이 임계값은 두 메시지에 대해 $N-t$ 일치 비트의 오류 정정 요구 사항에서 파생된다.
    • $\binom{(1-\alpha)n}{i}$: $(1-\alpha)n$ 비테스트 비트에서 $i$개의 올바른 비트를 선택하는 방법의 수.
    • $1/2^{(1-\alpha)n}$: 이 계수는 $(1-\alpha)n$ 비트에 대해 밥이 올바른 기저를 가지고 있지 않다면 각 비트를 올바르게 추측할 확률이 1/2임을 시사한다. 이는 특정 결과 시퀀스의 확률을 나타내는 합계를 정규화한다.

• $P_{bypass, s_1} \cdot P_{cheat, s_1, s_2}$: 특정 전략 $(s_1, s_2)$를 사용하여 밥이 성공적으로 속일 전체 확률.

  • 수학적 정의: 두 확률의 곱.
  • 물리적/논리적 역할: 이 두 사건(커밋먼트 우회 및 메시지 재구성 성공)은 순차적이며 조건부로 독립적이다. 곱셈은 성공적인 속임수 시도의 전체 확률을 제공한다.
  • 왜 곱셈인가?: 독립적인 사건의 경우, 둘 다 발생할 확률은 개별 확률의 곱이다.

• $\frac{2^{s_2}}{P_{bypass, s_1} \cdot P_{cheat, s_1, s_2}}$: 예상 비용.

  • 수학적 정의: 비율.
  • 물리적/논리적 역할: 이 항은 성공적인 속임수 시도당 밥이 필요로 하는 "비용 단위"(예: 추측을 위한 계산 작업)의 예상 수를 나타낸다. 어떤 사건의 확률이 $p$이면, 성공할 때까지의 예상 시도 횟수는 $1/p$이다. 여기서 $2^{s_2}$는 추측 노력으로 이를 확장한다.
  • 왜 나누기인가?: 이는 예상 비용 또는 시도 횟수를 계산하는 표준 방법이다. 총 비용(또는 노력)을 성공 확률로 나눈다.

논문에서 정직한 당사자의 프로토콜 정확성에 대한 $P_{fpass}$(방정식 1) 및 $P_{fcorrect}$(방정식 2)도 정의한다는 점에 주목할 가치가 있다. 이는 프로토콜이 오류나 거짓 중단 없이 의도한 대로 작동하도록 보장하는 데 중요하다.

• $P_{fpass} = \sum_{i=0}^{\beta \alpha n} \binom{\alpha n}{i} p_e^i (1-p_e)^{\alpha n - i}$: 앨리스의 테스트를 통과하지 못할 거짓 실패 확률.
  • 물리적/논리적 역할: 이는 정직한 앨리스와 밥이 무작위 비트 플립 오류($p_e$)로 인해 3-5단계에서 테스트에 실패하여 불필요한 중단을 초래할 확률이다. 이는 낮게 유지되어야 한다.
• $P_{fcorrect} = 1 - \frac{1}{2^{n-\alpha n}} \sum_{i=N-t}^{n-\alpha n} \binom{n-\alpha n}{i} \left( \sum_{j=N-t}^{N} \binom{N}{j} p_e^j (1-p_e)^{N-j} \right) \left( \sum_{k=N-t-j}^{N-i} \binom{N-i}{k} \frac{1}{2^{N-i}} \right)$: 9단계에서 오류 정정 실패 확률.
  • 물리적/논리적 역할: 이는 정직한 당사자의 경우 오류 정정이 실패하여 밥이 선택한 메시지를 올바르게 디코딩하지 못할 확률이다. 프로토콜이 실용적이려면 이 역시 매우 낮아야 한다. 정직하게 말하면, 논문의 공식에 제시된 대로 오류 정정 실패 맥락에서 인덱스와 $1/2^{N-i}$ 항의 정확한 해석에 완전히 확신하지는 못하지만, 일반적으로 메시지 세그먼트에 걸쳐 성공적인 디코딩에 필요한 일치 비트 수가 부족할 가능성을 나타낸다.

단계별 흐름

앨리스의 선택 비트 $m_c$ (여기서 $c$는 밥의 선택)와 같은 단일 추상 데이터 포인트가 양자 불투명 전송(QOT) 프로토콜을 통해 어떻게 이동하는지 추적해 보자. 이를 정교한 정보 보안 조립 라인으로 상상해 보자.

1. 양자 상태 준비 (앨리스): 각 라운드 $i$에 대해 앨리스는 비밀 비트 $x_i$와 무작위 기저 $\theta_i$로 시작한다. 그녀는 단일 광자 양자 상태 $|x_i\rangle_{\theta_i}$를 준비하는데, 이는 편광(예: 수평/수직 또는 대각선)이 $\theta_i$ 기저에서 $x_i$를 인코딩하는 빛의 작은 패킷(광자)이다. 이것이 시스템에 들어가는 원자재이다.

2. 양자 측정 (밥): 이 광자는 양자 채널을 통해 밥에게 전달된다. 앨리스의 $\theta_i$를 알지 못하는 밥은 자신의 측정 기저 $\tilde{\theta}_i$를 무작위로 선택한다. 그런 다음 그는 들어오는 광자를 측정하여 양자 상태를 붕괴시키고 고전적 비트 $\tilde{x}_i$를 생성한다. 밥의 $\tilde{\theta}_i$가 앨리스의 $\theta_i$와 일치하면 $\tilde{x}_i$는 거의 확실하게 $x_i$와 같을 것이다. 일치하지 않으면 $\tilde{x}_i$는 무작위(50% 확률로 0 또는 1)가 된다. 이것은 양자에서 고전으로 데이터 포인트의 첫 번째 변환이며, 여기서 밥의 "불투명성"이 시작된다.

3. 커밋먼트 (밥): 앨리스가 자신의 기저에 대해 아무것도 공개하기 전에 밥은 자신의 측정 선택 및 결과에 "커밋"해야 한다. 각 라운드 $i$에 대해 그는 측정된 비트 $\tilde{x}_i$, 선택한 기저 $\tilde{\theta}_i$, 무작위 문자열 $r_i$를 가져와 암호화 해시 함수 $h$에 입력한다. 출력 $c_i = h(\tilde{\theta}_i, \tilde{x}_i, r_i)$는 디지털 지문이다. 그는 이 $c_i$를 앨리스에게 보낸다. 이 커밋먼트는 나중에 마음을 바꾸는 것을 방지하기 위해 자신의 선택을 변조 방지 봉투에 봉인하는 것과 같다.

4. 검증 테스트 (앨리스 & 밥): 앨리스는 이러한 커밋먼트의 부분 집합("테스트 세트" $T$)을 무작위로 선택한다. 그녀는 밥에게 이 특정 봉투를 "열도록" 요청한다. 밥은 $i \in T$에 대해 원래 내용물 $(\tilde{\theta}_i, \tilde{x}_i, r_i)$을 공개한다. 앨리스는 해시 $h(\tilde{\theta}_i, \tilde{x}_i, r_i)$를 다시 계산하고 밥이 이전에 보낸 $c_i$와 일치하는지 확인한다. 또한 $\theta_i = \tilde{\theta}_i$인 라운드에서 $x_i$와 $\tilde{x}_i$를 비교하여 양자 채널이 신뢰할 수 있었는지 확인한다. 오류가 너무 많이 발견되거나 밥의 커밋먼트가 일치하지 않으면 앨리스는 프로토콜을 중단하고 데이터 흐름이 중지된다. 이것은 품질 관리 및 사기 탐지 단계이다.

5. 테스트 데이터 폐기: 테스트 세트 $T$의 데이터 포인트는 양 당사자에 의해 폐기된다. 이들은 검증 목적으로 사용되었으며 실제 메시지 전송에는 사용되지 않는다.

6. 기저 공개 (앨리스): 나머지 모든 라운드(T에 없음)에 대해 앨리스는 자신의 원래 인코딩 기저 $\theta_i$를 밥에게 공개한다. 이것은 앨리스로부터의 중요한 정보 공개이다.

7. 데이터 분할 (밥): 이제 밥은 자신의 측정값 중 어떤 것이 "좋은" 것($\theta_i = \tilde{\theta}_i$)이고 어떤 것이 "나쁜" 것($\theta_i \neq \tilde{\theta}_i$)인지 안다. 그의 비밀 선택 비트 $c$에 따라 그는 두 세트를 형성한다: $I_c$ ( $\theta_i = \tilde{\theta}_i$인 인덱스 포함) 및 $I_{1-c}$ ( $\theta_i \neq \tilde{\theta}_i$인 인덱스 포함). 그는 이 세트의 레이블($I_0$ 및 $I_1$)을 앨리스에게 보내지만, 앨리스는 여전히 어떤 것이 밥의 선택 $c$에 해당하는지 모른다. 여기서 밥의 선택이 데이터 경로를 형성하기 시작한다.

8. 메시지 인코딩 (앨리스): 앨리스는 두 개의 메시지 $m_0$와 $m_1$을 가지고 있다. 그녀는 두 개의 무작위 비트 문자열 $r_0$와 $r_1$을 생성한다. 그런 다음 오류 정정 코드(Encode)와 해시 함수($f_0, f_1$)를 사용하여 두 개의 마스크된 데이터 패킷을 준비한다:

   • $y_0 = \text{Encode}(r_0) \oplus x_{I_c}$ (여기서 $x_{I_c}$는 밥의 "좋은" 측정값에 해당하는 앨리스의 비트)
   • $y_1 = \text{Encode}(r_1) \oplus x_{I_{1-c}}$ (여기서 $x_{I_{1-c}}$는 밥의 "나쁜" 측정값에 해당하는 앨리스의 비트)
     그녀는 또한 $z_0 = m_0 \oplus f_0(r_0)$ 및 $z_1 = m_1 \oplus f_1(r_1)$을 준비한다. 여기서 앨리스의 메시지가 전송을 위해 준비되며, 공유된 무작위성과 오류 정정이 사용된다.

9. 메시지 디코딩 (밥): 밥은 자신의 선택 비트 $c$를 알고 해당 $y_c$를 선택하고 자신의 "좋은" 측정 비트 $\tilde{x}_{I_c}$를 사용하여 $r_c = \text{Decode}(y_c \oplus \tilde{x}_{I_c})$를 복구한다. 오류 정정 코드는 일부 비트 플립이 발생했더라도 $r_c$를 복구하는 데 도움이 된다. 마지막으로 그는 $r_c$를 사용하여 선택한 메시지를 마스크 해제한다: $m_c = z_c \oplus f_c(r_c)$. 그는 올바른 $\tilde{x}_{I_{1-c}}$(기저가 일치하지 않아 $\tilde{x}_{I_{1-c}}$가 본질적으로 무작위 노이즈이기 때문)를 가지고 있지 않기 때문에 $r_{1-c}$ 또는 $m_{1-c}$를 복구할 수 없다. 이것은 밥이 선택한 메시지를 받고 다른 메시지는 그에게 숨겨진 마지막 단계이다.

이 전체 과정은 밥이 정확히 하나의 메시지를 받고 앨리스는 밥의 선택에 대해 아무것도 배우지 못하도록 보장하여 전송을 "불투명"하고 "안전하게" 만든다.

최적화 동역학

QOT 프로토콜은 기계 학습 알고리즘과 달리 전통적인 의미에서 경사 또는 손실 함수를 통해 내부 매개변수를 반복적으로 "학습"하거나 "업데이트"하지 않는다. 대신, "최적화 동역학"은 주로 다음을 포함한다.

1. 사전 프로토콜 매개변수 최적화: 프로토콜이 시작되기 전에 앨리스와 밥(또는 시스템 설계자)은 정확성과 보안을 모두 보장하기 위해 다양한 매개변수를 신중하게 선택해야 한다.

   • 정확성 매개변수: $\alpha$(테스트 비트 비율), $\beta$(최소 허용 비트 일치 비율), $N$(오류 정정 코드 길이), $t$(수정 가능한 최대 오류)와 같은 매개변수는 정직한 실패 확률 $P_{fpass}$ 및 $P_{fcorrect}$를 최소화하도록 선택된다. 예를 들어, 앨리스는 밥의 광자 누락 비율 범위와 테스트 통과 확률에 대한 $\epsilon$ 임계값을 설정하여 프로토콜이 정직한 당사자에 대해 안정적으로 진행되도록 보장한다.
   • 보안 매개변수: $n$(총 라운드), 해시 함수 $h$의 강도, 오류 정정 코드의 선택은 모든 악의적인 밥에 대한 $cost_{cheat}$를 최대화하도록 설계되었다. 본 논문은 또한 광자 수 분할 공격을 방지하기 위해 디코이 상태 BB84 프로토콜의 평균 광자 수($\mu, \nu, 0$) 및 그 확률($P_1, P_2, 1-P_1-P_2$)을 최적화하는 것을 언급하는데, 이는 일종의 양자 보안 사전 프로토콜 최적화이다.

2. 적 최적화 환경: $cost_{cheat}$ 방정식 자체는 악의적인 밥이 직면한 최적화 문제를 나타낸다. 밥의 "학습" 또는 "최적화"는 속임수 비용을 최소화하는 $s_1$(지연 측정) 및 $s_2$(추측 비트) 값의 조합을 찾는 것이다. 프로토콜은 이 최소 비용이 천문학적으로 높도록(예: $3.8 \times 10^{12}$) 설계되어, 모든 속임수 경로가 극도로 어려운 "적 환경"을 형성한다. 프로토콜의 보안은 밥이 아무리 영리하게 전략을 최적화하더라도 비용이 금지적이라는 사실에 달려 있다.

3. 동적 중단 메커니즘: 프로토콜에는 중요한 동적 요소가 포함되어 있다. 즉, 4단계의 중단 조건이다. 테스트 단계의 오류율이 미리 정의된 임계값( $\beta$에 의해 결정됨)을 초과하면(노이즈 또는 밥의 악의적인 행동으로 인해) 프로토콜은 즉시 중단된다. 이는 프로토콜이 안전하지 않은 상태나 채널 품질이 너무 나쁠 때 진행되는 것을 방지한다. 이것은 보안 또는 정확성을 보장할 수 없을 때 실행을 중지하는 실시간 "상태 업데이트"이다.

4. 오류 정정으로서의 데이터 업데이트: 9단계에서 밥은 오류 정정 코드를 사용하여 $r_c$를 복구한다. 이 메커니즘은 코드의 능력 $t$까지 비트 플립을 수정하여 잠재적으로 손상된 비트 문자열 $r_c$를 동적으로 "업데이트"한다. 이는 양자 채널의 노이즈가 전송된 정보의 무결성을 손상시키지 않도록 보장하여 프로토콜이 올바른 메시지 $m_c$로 수렴할 수 있도록 한다.

본질적으로 여기서 "최적화 동역학"은 지속적인 학습보다는 사전 계산된 매개변수, 적의 계산된 최적 공격 전략 및 프로토콜이 안전하게 성공하거나 안전하게 실패하도록 보장하는 내장된 안전 장치를 갖춘 견고한 설계에 더 가깝다.

Figure 2. Quantum Oblivious Transfer Protocol Figure 3. Schematic of experimental setup

결과, 한계 및 결론

실험 설계 및 기준선

QOT 프로토콜을 엄격하게 검증하기 위해 저자들은 포괄적인 실험 설정을 시작했다. 그들의 설계의 핵심은 1-아웃-오브-2 QOT 프로토콜을 구현하는 것이었고, 이는 실제 개인 집합 교집합(PSI) 문제를 해결하는 데 적용되었다. 종종 노이즈 저장소 모델에 의존했던 이전 QOT 프로토콜과 달리, 이 작업은 비트 커밋먼트 체계를 통합하여 양자 공격에 대한 이론적 보안을 강화함으로써 자신을 구별했다.

앨리스의 양자 장치의 물리적 구현은 약한 일관 레이저 소스와 디코이 상태 방법을 결합하여 사용했다. 이 아키텍처는 실제 양자 통신에서 일반적인 취약점인 광자 수 분할(PNS) 공격을 방지하기 위해 특별히 선택되었다. 앨리스의 설정에는 신호, 디코이 및 진공 상태를 생성하기 위한 강도 변조기(IM)와 편광 인코딩 모듈(PC, PBS, PM 포함)이 포함되었다. 수신 측의 밥은 Z 또는 X 기저에서 측정을 위해 광자를 분기하는 빔 스플리터(BS)를 사용했으며, 이어서 PC, PBS 및 단일 광자 검출기(SPDs)를 사용하여 투영 측정을 수행했다.

실제 애플리케이션의 경우, QOT 프로토콜은 참조 [32]에 자세히 설명된 최적화된 불투명 의사 난수 함수(OPRF) 기반 PSI 프로토콜에 원활하게 통합되었다. 이 실험적 검증의 "희생자"(기준선)는 고전적 OT 기반 PSI 구현이었다. 실험은 시뮬레이션 및 실제 데이터 세트를 모두 사용하여 수행되었다. 실제 시나리오는 두 금융 기관을 포함했다. 한 기관은 의심스러운 계정의 블랙리스트를 제공했고, 다른 기관은 활성 고객 계정 목록을 제공했다. 목표는 각 은행이 다른 민감한 고객 정보를 공개하지 않고 공통 의심 계정을 안전하게 식별하는 것이었다. 이 설정은 양자 보안 메커니즘이 효과적이고 실용적으로 작동할 수 있음을 명확하고 부인할 수 없는 증거를 제공하기 위해 세심하게 설계되었으며, 금융과 같은 민감한 도메인에서 개인 정보 보호 컴퓨팅에 대한 시급한 요구를 직접적으로 해결했다.

증거가 증명하는 것

본 논문에서 제시된 증거는 QOT 프로토콜의 기능, 보안 및 실용적 적용 가능성을 강력하게 입증한다. 무엇보다도 실험은 QOT 프로토콜 자체의 성공적인 작동을 확인하며, 양자 보안 방식으로 불투명 전송을 수행하는 능력을 보여준다.

그들의 검증의 중요한 측면은 악의적인 적에 대한 프로토콜의 보안에 대한 엄격한 분석이었다. 저자들은 비트 커밋먼트 체계를 우회하고 앨리스의 두 메시지를 모두 획득하려는 부정직한 밥의 "속임수 비용"을 정량화했다. 이 비용은 성공적인 속임수 시도에 대한 예상 시간으로 정의되며, 약 $3.8 \times 10^{12}$로 계산되었다. 이를 관점에서 보면, 프로토콜의 단일 실행이 1초가 걸린다면, 악의적인 밥은 평균적으로 단 한 번의 속임수 시도에 성공하기 위해 약 120,000년이 필요할 것이다. 이 엄청난 수치는 핵심 비트 커밋먼트 메커니즘이 양자 공격에 대해 프로토콜을 효과적으로 보호하여 속임수를 실제 배포에서 거의 무시할 수 있게 만든다는 강력하고 부인할 수 없는 증거를 제공한다. 또한, 디코이 상태 BB84 프로토콜의 사용은 PNS 공격에 효과적임이 실험적으로 입증되었으며, 밥이 그러한 공격을 시도할 경우 앨리스는 밥이 보고한 광자 클릭 통계의 편차를 탐지할 수 있었다.

기본 QOT를 넘어, 본 논문은 개인 집합 교집합(PSI) 문제에 적용될 때 확장성 및 실용성에 대한 확실한 증거를 제공한다. 최대 $10^5$개의 요소에 대한 집합 크기를 사용한 실험은 통신 비용과 런타임 모두 요소 수에 따라 거의 선형적으로 확장됨을 보여주었다. 예를 들어, 파티당 $10^5$개의 요소를 처리하면 약 20MB의 총 통신량과 1Gbps 네트워크에서 0.4초 미만의 런타임이 발생했다. 이러한 성능 지표는 특히 은행 및 사기 탐지와 같은 분야에서 많은 실제 애플리케이션에 매우 실용적이다.

결정적으로, 고전적 OT 기반 PSI와 비교했을 때, QOT 기반 PSI는 약간 더 높은 통신 오버헤드를 발생시켰지만 거의 동일한 런타임을 유지했다. 이것은 그들의 QOT 프로토콜이 제공하는 향상된 양자 보안이 고전적 대응물에 비해 상당한 성능 페널티를 필요로 하지 않음을 증명하는 심오한 발견이다. 두 개의 시뮬레이션된 은행 간의 공통 의심 통신 사기 계정 식별 성공은 안전 다자간 연산에 대한 QOT 기반의 상업적 실행 가능성 및 실험적 기능을 보여주는 결정적인 실제 적용 사례로 남아 있다.

한계 및 향후 방향

실험 결과는 강력하고 실용적인 양자 보안 불투명 전송 프로토콜을 시연하는 매우 고무적이지만, 특정 한계를 인정하고 향후 개발을 고려하는 것이 중요하다.

관찰된 한 가지 실용적인 한계는 프로토콜 성능에 대한 광 감쇠의 영향이다. 채널 손실이 증가하면 검출된 광자 수가 감소하고 결과적으로 코드율(표 1)이 낮아진다. 정보 이론적 보안 보장은 그대로 유지되지만, 처리량 및 최대 전송 거리 측면에서 전반적인 실용성에 영향을 미친다. 향후 연구는 더 강력한 양자 채널 구현 또는 고급 오류 정정 기술을 탐색하여 높은 감쇠의 영향을 완화하고 QOT의 실제 범위를 확장할 수 있다.

고려해야 할 또 다른 점은 비트 오류율이 너무 높아지면 프로토콜이 중단되는 테스트 단계(4단계)에 대한 프로토콜의 의존성이다. 이는 보안을 보장하지만 극도로 노이즈가 많은 조건에서의 신뢰성과 절충을 의미한다. 추가 작업은 매개변수를 동적으로 조정하거나 더 정교한 후처리 기법을 사용하여 더 높은 오류율에서도 프로토콜이 진행될 수 있도록 하는 적응형 전략 또는 보다 복원력 있는 오류 정정 코드를 조사할 수 있다.

본 논문 자체는 불투명 전송(OT) 확장 기법 및 비버 트리플 사용과 같은 잠재적인 최적화 방법을 제시한다. OT 확장은 소수의 기본 OT에서 많은 수의 OT를 생성할 수 있게 하여 필요한 양자 리소스를 크게 줄인다. 비버 트리플, 사전 생성된 상관 관계가 있는 무작위성은 복잡한 계산을 오프라인 단계로 오프로드하여 온라인 단계에서 MPC 프로토콜을 더 효율적으로 실행할 수 있게 한다. 이러한 최적화를 구현하고 실험적으로 검증하는 것은 더 큰 데이터 세트와 더 복잡한 함수에 대해 프로토콜을 더욱 확장 가능하고 효율적으로 만들기 위한 자연스러운 다음 단계가 될 것이다.

앞으로, 시연된 프레임워크는 개인 집합 교집합을 넘어 광범위한 영향을 미친다. 저자들은 양자 보안 기계 학습 및 익명 투표 시스템을 포함한 다른 안전 다자간 연산 문제에 대한 적용 가능성을 제안한다. 이는 QOT 프로토콜이 차세대 양자 보안 MPC 애플리케이션을 위한 기본 요소 역할을 할 수 있는 풍부한 연구 분야를 열어준다. 이러한 다양한 애플리케이션을 탐색하려면 프로토콜을 다른 계산 작업에 맞게 조정하고 해당 특정 컨텍스트에서 성능과 보안을 평가해야 한다.

마지막으로, 프로토콜의 보안은 고전적 또는 사후 양자 OT를 뒷받침하는 가정보다 약하고 더 근본적인 암호학적 가정인 충돌 저항 해시 함수에 기반한 양자 보안 비트 커밋먼트의 존재에 의존한다. 이것은 강점이지만, 양자 컴퓨팅 및 암호 해독의 발전과 함께 이러한 가정들이 어떻게 진화할 수 있는지에 대한 최소한의 가정에 대한 추가적인 이론적 탐구를 유도한다. 또한 노이즈 저장소 모델 QOT와 비트 커밋먼트 기반 QOT 간의 성능 및 보안 절충에 대한 더 깊은 비교 분석은 양자 메모리 기술이 발전함에 따라 커뮤니티에 대한 가치 있는 논의 포인트가 될 것이다. 기밀 유지 계약으로 인해 공개 데이터 가용성이 부족한 것은 독립적인 검증 및 추가 연구에 대한 실질적인 한계이며, 향후 벤치마킹을 위해 표준화된 익명 데이터 세트의 필요성을 시사한다.

Figure 4. Comparison of communication cost and runtime between QOT-based and OT-based PSI experiments Table 2. Security assumptions for OT protocols Table 1. Dependence of the QOT code rate on optical attenuation. The code rate is defined as the number of successfully transmitted qubits per second (kbps)