Malleability of transformations on the ciphertext in noisy Quantum public key encryption

기술 요약: 노이즈가 있는 양자 공개 키 암호화에서의 암호문 변환의 가변성(Malleability)

문제 정의
본 논문은 노이즈가 존재하는 환경에서 양자 공개 키 암호화(QPKE) 및 양자 키 분배(QKD)에 대한 "영속적 보안(everlasting security)"을 엄밀하게 정식화하는 과제를 다룬다. Malavolta와 Walter [3]의 선행 연구는 무결한(noiseless) 설정에서 영속적 보안을 위한 프레임워크를 구축하여, Alice와 Bob 사이의 단 두 차례의 상호작용만으로 보안을 달ắt 수 있음을 입증한 바 있다. 본 연구는 노이즈의 도입이 프로토콜의 보안 임계값(security thresholds)에 어떠한 영향을 미치는지 조사한다. 구체적으로, 본 논문은 암호 연산에 노이즈가 주입될 때 암호문 변환의 가변성과 프로토콜 보안 사이의 관계를 탐구한다. 핵심 문제는 평문 및 암호문 변환의 가변성에 관한 가정을 활용하여, 이상적인 무결한 경우로부터 노이즈가 있는 설정으로 무효성 함수(negligibility function, 공격자의 이득을 정량화함)를 일반화하는 것이다.

방법론
저자들은 노이즈가 있는 QPKE-QKD 프로토콜을 분석하기 위해 양자 정보 이론과 추상 암호학의 결 조합을 채택한다. 방법론은 다음과 같은 주요 구성 요소로 구조화된다:

1. 가변성을 통한 노이즈 주입: 저자들은 "인증 후 암호화(authenticate then encrypt)"와 "암호화 후 인증(encrypt then authenticate)" 프로토콜을 비교하기 위해 Maurer와 Tackmann [9]이 도입한 가변성 개념을 응용한다. 저자들은 전달 오류(forwarding error), 삭제 오류(deleting error), 재구성 오류(reconstruction error)라는 세 가지 오류 확률로 특징지어지는 평문 공간상의 노이즈가 있는 변환을 정의한다. 이러한 오류들은 암호문에 미치는 노이즈의 영향을 모델링하는 데 사용된다.
2. 트레이스 거리(Trace Distance) 및 완만한 측정 보조정리(Gentle Measurement Lemma, GML): 핵심적인 기술적 도구는 양자 정보 이론[18]의 완만한 측정 보조정리를 적응시키는 것이다. 저자들은 특정 연산자의 트레이스(trace)의 하한을 바탕으로 두 양자 상태(실제 실험과 이상적 실험을 나타내는) 사이의 트레이스 거리의 상한을 설정하기 위해 이 보조정리를 사용한다. 이를 통해 노이즈가 존재하는 상황에서 무효성 함수를 일반화할 수 있다.
3. 노이즈가 있는 양자 다항 시간(NQPT) 머신: 저자들은 노이즈가 있는 환경을 모델링하기 위해 Alice, Bob, 그리고 공격자(Eve)의 동작을 모델링하는 노이즈가 있는 완전 양의 트레이스 보존(CPTP) 맵과 NQPT 머신을 정의함으로써 노이즈가 있는 설정을 공식화한다. 이는 기존의 무결한 대응물들을 대체한다.
4. 투영 연산자 및 상태 분해: 분석에는 표준 투영 연산자 $\Pi$에 노이즈 항(예: $|\sigma + \text{noise}\rangle$)을 포함하는 노이즈 투영 연산자($\tilde{\Pi}$)를 구성하는 과정이 포함된다. 저자들은 노이즈가 없는 투영 연산자와 노이즈가 있는 투영 연산자, 트레이스 연산, 그리고 ket/bra 상태 간의 비율을 비교함으로써 트레이스 거리의 상한을 도출한다.
5. 자원 이론적 접근 방식: 저자들은 [9]의 자원 이론적 프레임워크를 활용하여, 프로토콜에 의해 구축된 자원의 구별 불가능성 측면에서 보안과 가용성을 정의한다. 여기에는 프로토лот의 합성 및 하이브리드 실험의 구별 불가능성 분석이 포함된다.

주요 기여

• 노이즈가 있는 영속적 보안의 공식화: 본 논문은 노이즈가 있는 QPKE 프로토콜에 대한 "영속적 보안"을 정의하며(정의 37), 노이즈가 있는 하이브리드 실험 간의 트레이스 거리가 노이즈가 있는 보안 파라미터 $\lambda'$에 의존하는 무효성 함수에 의해 유계됨을 입증한다.
• 무효성 함수의 일반화: 저자들은 노이즈가 있는 설정에서의 트레이스 거리와 무효성 함수 $NEGL(\lambda')$ 사이의 관계를 도출한다. 그들은 특정 노이즈 가정 하에서, 노이즈가 있는 설정의 무효성 함수가 무결한 경우에 비해 더 높은 보안 임계값과 관련이 있음을 보여준다.
• GML을 통한 트레이스 거리 상한 도출: 주요 기술적 기여는 완만한 측정 보조정리를 사용하여 트레이스 거리의 상한을 도출하는 것이다. 저자들은 다음을 입증한다:
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  이는 노이즈가 있는 상태와 무결한 상태($\tilde{\rho} - \tau$)를 포함하는 특정 연산자의 트레이스에 대한 하한을 증명함으로써 달성된다.
• 가변성 가정: 본 연구는 암호문 변환의 가변성과 프로토콜 보안을 명시적으로 연결한다. 저자들은 노이즈가 있는 변환의 전달, 삭제, 재구성 오류 확률이 무결한($\lambda$) 프로토콜과 노이즈가 있는($\lambda'$) 프로토콜 사이의 보안 임계값 격차와 어떻게 연관되는지 정량화한다.
• 계산 실행 시간 트레이드오프: 논문은 노이즈가 있는 프로토콜과 무결한 프로토콜 간의 계산 실행 시간(인코딩, 디코딩, 키 생성)의 트레이드오프를 분석한다. 이는 만약 노이즈가 있는 프로토콜의 실행 시간이 상당히 더 크다면, 보안 임계값 격차 $\lambda' - \lambda$가 실행 시간 차이와 관련된 특정 방식(지수 또는 다항 함수와 관련된 방식)으로 스케일링될 수 있음을 시사한다.

결과

• 주요 정리: 본 논문은 올바름(correctness) 조건을 만족하는 노이즈가 있는 QPKE-QKD 프로토콜에 대해, 노이즈가 있는 하이브리드 실험(비트 0과 1로 초기화된) 사이의 트레이스 거리가 노이즈가 있는 보안 파라미터의 무효성 함수에 의해 유계됨을 증명한다:
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• 이득 함수에 관한 따름정리: 저자들은 서로 다른 하이브리드 실험에 대한 노이즈가 있는 이득 함수($\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$)가 모두 동일한 무효성 함수 $NEGL(\lambda')$에 의해 유계됨을 보여줌으로써, 다양한 실험 설정에 걸친 보안 정의의 일관성을 확인한다.
• 트레이스 하한: 논문은 특정 연산자의 트레이스가 무효성 함수의 역수에 상수를 곱한 값보다 크다는 상세한 유도 과정을 제공하며, 이는 완만한 측정 보조정리를 적용하기 위한 전제 조건이다.

의의 및 주장
본 논문은 노이즈가 있는 양자 공개 키 암호화로 영속적 보안의 개념을 확장하기 위한 엄밀한 수학적 프레임워크를 제공한다고 주장한다. 완만한 측정 보조정리를 적응시킴으로써, 저자들은 암호문 변환에 대한 가변성 가정이 제공되는 한, 무결한 프로토콜의 보안 보장이 노이즈가 있는 설정으로 일반화될 수 있음을 보여준다.

저자들은 노이즈의 도입이 일반적으로 더 높은 보안 임계값(즉, $\lambda'$ 측면에서 잠재적으로 더 약한 보안 보장을 의미함)을 초래하지만, 도출된 상한선들이 노이즈가 있는 프로토콜과 무결한 프로토콜 간의 정량적 비교를 가능하게 한다고 강조한다. 본 연구는 무조건적 및 영속적 보안을 실험적으로 구현하는 것이 어렵다는 점을 언급하며 이론적 디딤돌로서 제시되며, 제안된 프레임워크는 암호학적 맥락에서 노이즈가 있는 양자 계산의 한계를 분석하기 위한 가치 있는 출발점을 제공한다. 논문은 도출된 트레이스 거리 경계 계산이 게임 이론적 접근 방식에 중심을 둔 환경에서도 추가로 검토될 수 있음을 시사하며, 이론적 분석 이상의 구체적인 실험적 구현이나 즉각적인 응용을 제안하지는 않는다.