기술 요약: 샤미르 비밀 공유의 양자 누설 회복력 (Quantum Leakage Resilience of Shamir Secret Sharing)

문제 정의

본 논문은 소수 체 $\mathbb{F}_p$ 상에서 작동하는 표준적이고 수정되지 않은 샤미르 비밀 공유 방식의 양자 누설 회복력을 조사한다. 샤미르 방식은 임계값 암호학 및 안전한 다자간 계산에서 널리 사용되지만, 그 보안 보장은 전통적으로 권한이 없는 집합이 비밀에 대해 아무것도 알 수 없음을 가정한다. 그러나 실제로는 부채널을 통해 부분적인 정보(누설)가 노출될 수 있다.

저자들은 고전적 설정(각 공유로부터 짧은 고전적 출력, 예: 1비트를 얻는 경우)에서의 국소 누설 회복력(local leakage resilience) 연구를 양자적 설정으로 확장한다. 이 모델에서 각 당사자의 장치는 고전적 공유를 수신하고, 적대자에게 단일 큐비트(또는 소수의 큐비트)를 출력하며, 적대자는 이를 결합 측정할 수 있다. 또한 본 연구는 누설 장치들 사이, 또는 장치와 적대자 사이의 **사전 공유된 얽힘(pre-shared entanglement)**이 보안에 미치는 영향을 탐구한다.

방법론

본 논문은 두 비밀 상태 사이의 구별 가능 이점(distinguishing advantage)을 제한하기 위해 **유한체 푸리에 분석(finite-field Fourier analysis)**과 최대 거리 분리(MDS) 코드의 특성을 결합하여 사용한다.

1. 파울리-푸리에 환원 (Pauli-Fourier Reduction):

   • 각 공유로부터의 누설은 밀도 행렬 $\rho_i(y_i)$로 모델링된다. 저자들은 이를 파울리 기저로 전개한다: $\rho_i(y) = \frac{1}{2}(I + r_{i,X}(y)X + r_{i,Y}(y)Y + r_{i,Z}(y)Z)$.
   • 그들은 파울리 계수 함수의 제곱 크기를 기반으로 한 "푸리에 예산(Fourier budget)" $W_i(a)$를 정의한다.
   • 파스발 항등식(Parseval's identity)과 파울리 연산자의 직교성을 사용하여, 구별 가능 이점은 듀얼 샤미르 코드 $C^\perp_0$에 대한 합으로 제한된다:
     $$\text{Adv} \leq \sum_{a \in C^\perp_0 \setminus \{0\}} \prod_{i=1}^n \sqrt{W_i(a_i)}$$
   • 이는 양자 보안 문제를 듀얼 코드 상의 가중 합을 제어하는 문제로 환원시키며, 이는 고전적 누설 증명과 유사하지만 계수의 행렬 값 특성으로 인해 더 복잡하다.

2. 얽힘 및 블록 처리:

   • 분리된 블록 (Disjoint Blocks): 서로 분리된 블록 내에서 (블록 간 또는 블록과 적대자 사이에는 얽힘이 없지만) 얽힘을 공유하는 장치들의 경우, 저자들은 블록 MDS 브라스캄프-리 ليب(Brascamp-Lieb) 부등식을 적용한다. 이를 통해 블록 출력에 대한 푸리에 계수의 트레이스 노름(trace norm) 곱의 합을 제한할 수 있다.
   • 적대자와의 얽힘: $E$라는 집합의 장치들이 적대자와 임의의 얽힘을 공유하는 경우, 저자들은 **환원 논증(reduction argument)**을 사용한다. 만약 적대자가 $E$의 고전적 공유를 학습한다면, 남은 시스템의 보안은 $n-r$명의 당사자와 $t-r$의 임계값을 가진 얽히지 않은 샤미르 방식으로 환원됨을 보여준다.

3. 부정적 결과 (공격):

   • 저자들은 $t$개의 장치 사이에 공유된 GHZ 상태를 사용하는 특정 공격을 구성한다. 각 장치가 자신의 공유에 따라 위상 변화(phase shift)를 적용하고 파울리-X 기저에서 측정함으로써, 높은 이점을 가지고 비밀을 구별해낼 수 있다. 이는 각 장치가 단 하나의 고전적 비트만을 출력하는 경우에도 가능하다.

주요 기여 및 결과

1. 얽히지 않은 양자 누설

저자들은 임계율(threshold rate) $\tau = t/n$이 특정 상수 $\tau^\star \approx 0.73339$를 초과할 때, 샤미르 비밀 공유가 얽히지 않은 국소 1-큐비트 누설에 대해 안전함을 증명한다.

• 결과: 만약 $\tau > \tau^\star + \eta$ (고정된 $\eta > 0$에 대해)라면, 구별 가능 이점은 지수적으로 작다 ($2^{-\Omega(n)}$).
• 기법: 이는 블록 크기 $b=1$인 블록 MDS 브라스캄프-리 ليب 부등식을 사용하여 도출된다.

2. 분리된 얽힌 블록

장치들이 고정된 최대 크기 $b$를 가진 분리된 블록으로 나뉘어 있고, 블록 내 장치들은 얽힘을 공유하며 공동 계산을 수행할 수 있지만, 블록 간 또는 블록과 적대자 사이에는 독립적인 시나리오로 보안을 확장한다.

• 결과: 보안은 충분히 높은 임계율 $\tau > \tau^\star(b)$에서 유지되며, 이때 $\tau^\star(b) < 1$이다. 블록 크기 $b$가 증가함에 따라 요구되는 임계율은 1에 근접한다.
• 세부 사항: 논문의 표 1은 동일한 블록 크기에 대한 충분한 임계값을 나열한다 (예: $b=2$일 때 $\tau \approx 0.933$, $b=3$일 때 $\tau \approx 0.987$).

3. 적대자와의 얽힘이 있는 누설

본 논문은 선형 개수의 장치($r = \delta n$)가 서로 및 적대자와 임의의 얽힘을 공유하는 경우를 분석한다.

• 결과: 보안은 다음 조건을 만족할 때 유지된다:
  $$\frac{\tau - \delta}{1 - \delta} > \tau^\star$$
  이는 고정된 임계율 $\tau > \tau^\star$에 대해, 선형 비율의 장치($\delta < \frac{\tau - \tau^\star}{1 - \tau^\star}$)가 적대자와 얽힘을 공유하더라도 보안이 유지됨을 의미한다.

4. 부정적 결과: GHZ 공격

저자들은 $t$개의 장치가 GHZ 상태를 공유할 경우, 해당 방식이 고전적 단일 비트 누설 하에서도 불안전해짐을 입증한다.

• 메커니즘: $t$개의 장치가 GHZ 상태를 공유한다. 각 장치는 자신의 공유에 기반하여 위상을 적용하고 X-기저에서 측정한다. 결과값들의 곱은 $\cos^2(\pi/(2p)) \approx 1 - O(p^{-2})$의 이점을 가지고 비밀을 드러낸다.
• 시사점: 이 공격은 적대자와의 얽힘 없이, 오직 누설되는 $t$개의 장치 사이의 얽힘만을 필요로 한다. 이는 보안을 유지하면서 임의의 얽힘을 공유할 수 있는 최대 장치 수가 $n$에 대한 선형(상수 배 차이 내에서)임을 확립하지만, 최적의 비율은 여전히 미해결 과제로 남아 있다.

의의 및 주장

본 논문은 널리 사용되는 수정되지 않은 샤미르 비밀 공유 방식의 양자 누설 회복력 연구를 개시한다고 주장한다.

• 표준 방식의 견고성: 결과는 표준 샤미르 방식이 새로운 공유 알고리즘이나 프로토콜 변경 없이도, 임계율이 충분히 높다면(약 0.733 이상) 양자 누설에 대해 강력한 보안 보장을 유지함을 보여준다.
• 얽힘의 역할: 본 연구는 중요한 차이점을 강조한다: 얽히지 않은 양자 누설은 높은 임계값 하에서 관리 가능하지만, 누설 장치들 사이의 임의의 얽힘(특히 $t$개 장치 사이의 GHZ 상태)은 고전적 출력 상황에서도 보안을 무너뜨릴 수 있다.
• 최적성: 저자들은 자신들의 경계값이 최적이라는 점에 대해 신중한 태도를 보인다. 그들은 충분한 임계값 $\tau^\star \approx 0.733$이 알려진 고전적 경계($\approx 0.668$)보다 높다는 점을 언급하며, 이 간극을 메울 수 있는지에 대한 의문을 제기한다. 마찬가지로, 보안과 호환되는 얽힌 장치의 정확한 최적 비율 또한 미해결 문제로 남겨둔다.

결론적으로, 양자 누설 회복력은 누설되는 출력의 크기와 누설 장치들이 가용할 수 있는 얽힘 구조 모두에 근본적으로 의존한다.