기술적 요약: QROM에서 불완전한 완결성을 가진 키 합의의 불가능성을 향하여

1. 문제 정의

본 논문은 양자 계산, 고전 통신(QCCC) 키 합의 프로토콜의 **양자 랜덤 오라클 모델(QROM)**에서의 보안성을 다룬다. 구체적으로, 정당한 당사자들이 확실성(완벽한 완결성)이 아닌 역다항식 확률($\alpha > 0$)로 유효한 키에 합의하는 불완전하게 완결된(imperfectly complete) 프로토콜의 실현 가능성을 조사한다.

기존 연구들은 다양한 제한 조건 하에서 완벽하게 완결된 QCCC 키 합의 및 양자 공개키 암호(QPKE)에 대한 무조건적 불가능성 결과를 확립했다. 그러나 정당한 당사자들이 제한 없는 양자 오라클 접근 권한을 갖는 경우, 불완전하게 완결된 프로토콜의 가능성은 열려 있는 문제였다. Austrin 등(2022)이 식별한 중요한 장벽은 만약 "시뮬레이션 추측(Simulation Conjecture)"이 성립한다면, 고전적 공격자가 이러한 프로토콜을 깨뜨릴 수 없음을 시사한다. 본 논문은 정당한 당사자의 오라클 접근 방식을 특정 방식으로 제한함으로써 이 추측을 우회하며, 이를 통해 계산 능력이 무제한인 양자 공격자에 의한 무조건적 공격을 가능하게 한다.

2. 방법론 및 기술적 접근

저자들은 **헤비 쿼리 학습(heavy-query learning)**과 랜덤 리프로그래밍(random reprogramming) 기술의 결적인 조합을 사용하여 무조건적 공격을 구성한다. 핵심 전략은 공격자(Eve)가 통신을 가로채어 정당한 당사자들이 수행한 오라클 쿼리의 "헤비(heavy)" 집합을 학습한 후, 이 부분적 오라클에 조건화된 정당한 당사자들의 뷰(view)를 재샘플링하여 키를 복구하는 것이다.

2.1 2-메시지 공격

첫 번째 설정은 다음과 같은 두 라운드 프로토콜을 고려한다:

• Alice는 첫 번째 라운드에서 오라클에 고전적 쿼리만을 수행하고 Bob에게 고전적 메시지($m_1$)를 보낸다.
• Bob은 임의의 양자 계산을 수행하고 양자 쿼리를 만들 수 있으며, 양자 메시지($\Psi$)를 보낸다.
• Alice는 마지막 라운드에서 양자 계산과 양자 쿼리를 수행할 수 있다.

공격 메커니즘:

1. 헤비 쿼리 학습: $m_1$을 수신하면, Eve는 학습 알고리즘(Austrin 등 및 Katz & Sela 기반)을 사용하여 $m_1$에 조건화되어 Alice가 첫 라운드에서 쿼리할 가능성이 높은 "헤비" 입력들을 식별한다. 그녀는 이러한 헤비 입력들을 쿼리함으로써 부분적 오라클 $h$를 구축한다.
2. 조건부 재샘플링: Alice의 첫 라운드 쿼리는 고전적이므로, 일단 $m_1$과 답변의 트랜스크립트 $h$가 고정되면, Alice의 잔여 양자 상태는 오직 이러한 고전적 변수들에만 의존한다. 따라서 Eve는 조건부 분포 $\omega_{m_1, h}$로부터 신선한 뷰 $(T'_A, S'_A)$를 샘플링할 수 있다.
3. 리프로그래밍: Eve는 Bob의 양자 메시지 $\Psi$를 가로챈다. 그녀는 샘플링된 상태 $S'_A$와 $\Psi$를 사용하여 Alice의 최종 알고리즘을 실행하며, 이때 $Dom(h)$상에서는 샘플링된 트랜스크립트$T'_A$와 일치하고 그 외의 영역에서는 원래의 오라클처럼 동작하는 **리프로그래밍된 오라클**$H[T'_A]$를 사용한다.
4. 분석: 보안 손실은 랜덤 리프로그래밍 렘마(Katz & Sela)에 의해 경계가 정해진다. Alice가 학습된 집합 $Dom(h)$외부의 점을 쿼리할 확률은 작기 때문에(파라미터$\delta$에 의해 제어됨), 리프로그래밍은 양자 알고리즘의 수용 확률을 크게 변화시키지 않는다.

2.2 다중 라운드 공격

두 번째 설정은 **고전적 통신 접두사(classical-communication prefix)**가 존재하는 경우 임의의 라운드 수를 가진 프로토콜로 결과를 확장한다:

• 접두사 동안의 모든 메시지와 오라클 쿼리는 고전적이다.
• 당사자들은 양자 상태를 유지하고 로컬 양자 계산을 수행할 수 있다.
• 마지막 라운드는 Bob으로부터의 가능한 양자 메시지와 Alice의 최종 양자 계산을 포함한다.

공격 메커니즘:

1. 고전적 시뮬레이션: Eve는 고전적 접두사를 보조적인 고전 프로토콜로 취급한다. 그녀는 계산 능력이 무제한이므로, 조건부 잔여 상태를 포함한 Alice와 Bob의 고전적 뷰를 정확하게 시뮬레이션할 수 있다.
2. Barak-Mahmoody 학습기: Eve는 시뮬레이션된 고전적 뷰에 Barak-Mah Mahmoody 학습기(원래 고전 프로토콜용)를 적용하여 부분적 오라클 $h$를 학습하고, $h$에 조건화되었을 때 Alice와 Bob의 뷰가 대략적으로 독립적(곱 상태)임을 보장한다.
3. 재샘플링 및 커플링: Eve는 $h$에 조건화된 Alice와 Bob의 독립적인 뷰를 샘플링한다. 그 후, Bob을 위한 베이스 오라클을 샘플링하고 이를 Alice를 위해 리프로그래밍함으로써 이 뷰들을 일관된 오라클과 결합(couple)한다.
4. 최종 공격: Eve는 마지막 양자 메시지를 가로채고, 리프로그래밍된 오라클과 함께 샘플링된 상태 위에서 Alice의 최종 알고리즘을 실행한다.

3. 주요 기여 및 결과

3.1 주요 정리

• 정리 1.1 (2-메시지 공격): Alice의 1단계 쿼리와 메시지가 고전적인 모든 프로토콜에 대하여, Bob의 키를 확률 $> \alpha/2$로 복구하는 계산 능력이 무제한인 양자 공격자가 $O(\text{poly}(q, 1/\alpha))$ 쿼리를 사용하여 존재한다. 공격자는 Bob의 응답 전에 고전적 쿼리를 수행하고 이후 양자 쿼리를 수행한다.
• 정리 1.2 (다중 라운드 공격): 임의 길이의 고전적 쿼리 접두사를 가진 프로토콜에 대해서도 유사한 공격이 존재한다. 쿼리 복잡도는 전체 접두사 쿼리 수에는 의존하지만, 라운드 수에는 의존하지 않는다.
• 정리 1.3 (QPKE 공격): 이러한 결과는 (다항 길이의) 고전적 메시지에 대한 **양자 공개키 암호(QPKE)**가, 암호화, 복호화, 그리고 암호문이 모두 양자일지라도, 다항개의 쿼리를 수행하는 계산 능력이 무제한인 공격자에 대해 IND-CPA 보안을 가질 수 없음을 시사한다.

3.2 구체적 적용

• OSP로부터의 불완전하게 올바른 PKE: 본 논문은 Bartusek와 Khurana(CRYPTO 2025)의 **Oblivious State Preparation (OSP)**에서 유도된 PKE 스킴에 자신의 결과를 적용한다. 이는 만약 OSP 송신자가 오직 고전적 랜덤 오라클 쿼리만을 수행한다면, 결과적인 PKE가 QROM에서 보안이 아님을 보여준다. 특히 이는 기저가 되는 OSP 프로토콜이 무시할 수 있는 수준으로 틀린(negligibly incorrect) 경우(즉, 불완전하게 완결된 경우)에 해당한다.
• 고전적 도청: 만약 (Bob의 응답을 포함한) 전체 프로토콜이 고전적이라면, 이 공격은 수동적 고전 도청 공격으로 축소된다.

4. 의의 및 주장

본 논문은 정당한 당사자들이 후기 단계에서 제한 없는 양자 오라클 접근 권한을 갖는 제한된 설정에서, 불완전하게 완결된 QCCC 키 합의의 불가능성을 향한 진전을 이루는 최초의 무조건적 공격을 제공한다고 주장한다.

• 시뮬레이션 장벽 극의: 저자들은 불완전하게 완결된 일반적인 QCCC에 대한 완전한 고전적 공격은 시뮬레이션 추측을 부정해야 할 것임을 언급한다. 정당한 당사자의 초기 쿼리를 고전적으로 제한함으로써, 본 연구는 이 장벽을 우회하여 추측이 거짓이라고 가정하지 않고도 무조건적 공격을 가능하게 한다.
• 제한의 엄밀성: 결과는 중요한 트레이드오프를 강조한다: 공격은 초기 오라클 쿼리가 고전적이라는 사실에 의존한다. 만약 접두사 쿼리가 양자적이었다면, 당사자들은 오라클과 얽히게 되어 여기서 사용된 "재샘플링" 기법을 사용할 수 없었을 것이다. 저자들은 접두사의 양자 쿼리로 이 결과를 확장하는 것은 새로운 기술이 필요하며 향후 과제로 남겨둔다고 명시했다.
• 보안 개념: 본 논문은 표준적인 CC1QM 보안보다 강한 의미의 특정 보안 개념(가로채기 키 복구)을 정의한다. 이는 공격자가 Alice를 위한 유효한 상태를 시뮬레이션할 필요 없이 키를 복구하기만 하면 된다는 점에서 차이가 있지만, 파생된 QPKE 스킴의 IND-CPA 보안을 깨뜨리기에는 충분하다.

요약하자면, 본 논문은 키 합의 프로토콜의 초기 단계에서의 고전적 오라클 접근이 불완전하게 완결된 스킴에 있어 치명적인 약점이 되며, 프로토콜의 나머지 부분이 완전히 양자일지라도 무제한 양자 공격자에게 보안이 없음을 입증한다.