Quantum Key Search Algorithms under Side-channel Attack

기술 요약: 부채널 공격 하에서의 양자 키 탐색 알고리즘

문제 정의
본 연구는 공격자가 부채널 공격(SCA)으로부터 유도된 노이즈가 포함된 키를 보유한 경우의 암호 알고리즘 키 탐색 문제를 다룬다. 이 시나리오에서 공격자는 실제 타겟 키 $k^*$와 특정 비트 반전 수(해밍 거리)만큼 차이가 나는 키 $Y$를 얻는다. 키 공간의 확률 분포는 균등하지 않으며, 비트 에러율(BER) $\alpha$에 의해 결정되는 $n$-중 베르누이 분포를 따른다. 과제는 주어진 노이즈 키가 제공하는 사전 정보를 활용하여, 이 비균등한 키 공간을 효율적으로 탐색하여 $k^*$를 찾는 것이다. 표준 그로버(Grover) 알고리즘은 $O(\sqrt{N})$의 쿼리를 요구하는 반면, 고전적인 브루트 포스(brute-force) 탐색은 $O(N)$의 쿼리가 필요하며, 두 방식 모두 부채널 공격으로 인해 발생하는 베르누이 분포의 특수한 구조를 완전히 활용하지 못한다. 또한, 몽타나로(Montanaro)의 알고리즘과 같은 기존의 양자 접근 방식은 동일한 사후 확률을 가진 키 블록들을 위한 특정 초기 중첩 상태를 준비하는 데 어려움을 겪는다.

방법론
저자들은 이론적 모델링, 알고리즘 설계, 상태 준비를 아우르는 종합적인 프레임워크를 제안한다:

1. 확률적 모델링: 본 연구는 비트 반전 확률이 $\alpha$인 독립 동일 분포(i.i.d.)를 가정하여 키 공간 분포를 모델링한다. 베이즈 정리를 사용하여, 후보 키의 사후 확률은 노이즈 키 $Y$로부터의 해밍 거리 $d$에 의해서만 결정됨을 보인다. 이는 동일한 해밍 거리를 가진 키들이 동일한 사후 확률을 공유함을 입증한다.
2. 고전적 기준선(Baseline): 후보 키를 사후 확률이 높은 순서(즉, 해밍 거리 $d=0$에서 $d=n$까지)로 순회하는 고전적 키 탐색 알고리즘을 도출한다. 기대 쿼리 복잡도 $G_c$는 각 거리에서의 후보 키에 대한 이항 분포를 기반으로 엄격하게 계산된다.
3. 개선된 양자 알고리즘:
   • 분할 전략: 기하급수적으로 증가하는 블록 $\{1, c, c^2, \dots\}$로 키 공간을 분할하는 몽타나로의 알고리즘과 달리, 본 논문은 해밍 거리 $d$에 따라 $(n+1)$개의 블록 $\{R_0, R_1, \dots, R_n\}$으로 키 공간을 분할할 것을 제안한다. 각 블록 $R_d$는 정확히 $d$개의 비트 에러를 갖는 $\binom{n}{d}$개의 후보 키를 포함한다.
   • 탐색 실행: 알고리즘은 확률이 감소하는 순서(해밍 거리 $d$가 증가하는 순서)로 이 블록들을 순회한다. 각 블록 $R_d$에 대해, 해당 블록 내의 키들의 균등 중첩 상태를 준비하고 그로버 탐색을 적용한다.
   • 복잡도 분석: 양자 쿼리 복잡도 $G_q$는 타겟 키가 해당 블록에 존재할 확률에 가중치를 두어 각 블록에 대한 그로버 탐색 비용을 합산함으로써 도출된다.
4. 초기 상태 준비: 각 블록 $R_d$를 위한 특정 중첩 상태를 준비하는 데 발생하는 어려움을 해결하기 위해, 저자들은 후보 키 상태와 디케 상태(Dicke state) $|D^n_d\rangle$ 사이의 등가성을 확립한다. 저자들은 $Y$로부터 해밍 거리 $d$인 키들의 균등 중첩 상태가 디케 상태 $|D^n_d\rangle$에 파울리-$X$ 연산의 텐서 곱($X^{\otimes Y}$)을 적용하여 생성될 수 있음을 증명한다.
   • 구현: 디케 상태는 보조 큐비트(auxiliary qubits)를 필요로 하지 않는 짧은 깊이의 분할 정복 회로(Bärtschi와 Eidenbenz의 연구 기반)를 사용하여 준비된다. 최종 상태는 노이즈 키 $Y$에 따라 $O(d)$개의 X-게이트를 적용하여 얻어진다.

주요 기여

• 이론적 도출: 본 논문은 부채널 공격 조건 하에서의 고전 및 양자 키 탐색에 대한 계산 복잡도를 베르누이 분포를 모델링하여 엄밀하게 도출한다.
• 알고리즘 개선: 해밍 거리 기반의 블록 분할 전략을 사용하는 개선된 양자 키 탐색 알고리즘을 도입한다. 이 전략은 몽타나로의 알고리즘에서 사용되는 기하학적 분할보다 실제 부채널 공격 시나리오의 키 분포에 더 부합함을 보여준다.
• 상태 준비 솔루션: 문제를 디케 상태 준비로 변환함으로써 입력 상태 준비의 병목 현상을 해결한다. 저자들은 필요한 상태가 $O(nd)$개의 CNOT 게이트와 낮은 회로 깊이(이온 트랩 토폴로지의 경우 $O(d \log \frac{n}{d})$, 초전도 토폴로지의 경우 $O(\sqrt{nd})$)를 사용하여 보조 큐비트 없이 생성될 수 있음을 입증한다.

결과
비트 에러율(BER)이 1%($\alpha = 0.01$)인 256비트 암호 키에 대한 시뮬레이션 결과, 상당한 성능 향상을 입증하였다:

• 복잡도 감소: 부채널 공격 조건 하에서 고전 알고리즘의 쿼리 복잡도는 $2^{256}$(공격 없음)에서 $2^{62.29}$로 감소한다. 제안된 양자 알고리즘은 이를 다시 $2^{19.77}$로 줄인다.
• 가속 계수(Speedup Factor): 제안된 양자 알고리즘은 부채널 공격 조건 하의 고전 알고리즘 대비 3.15배의 가속 계수를 달성한다. 이는 동일한 조건에서 글레이저(Glaser) 등이 몽타나로 알고리즘을 분석하며 보고한 2.73배의 가속 계수와 비교된다. 저자들은 자신들의 탐색 효율이 [9]에서 제안된 몽타나로의 기하급수적 성장 알고리즘보다 15.38% 더 높다고 언급한다.
• 경계값과의 비교: 본 논문은 도출된 양자 쿼리 복잡도($2^{19.77}$)가 이 특정 분포 시나리오에서 글레이저가 몽타나로 알고리즘을 위해 추정한 상한/하한($2^{21.59}$ 및 $2^{17.59}$)보다 더 정밀하고 타이트하다고 주장한다.
• 자원 효율성: 상태 준비 방식은 짧은 깊이의 회로로 구현 가능함이 나타났으며, $n=256, d=4$인 경우에 대한 구체적인 자원 수치(예: 1024개의 CNOT 게이트, 0개의 보조 큐비트)가 제공된다.

의의
본 논문은 부채널 공격 하에서의 양자 암호 해독을 위한 이론적 분석부터 실제 구현까지의 전체 체인 솔루션을 제공한다고 주장한다. 부채널 노이즈(베르누이 분포)의 특수한 구조를 활용함으로써, 제안된 알고리즘은 고전적 대응 방식에 대해 **초이차적 가속(super-quadratic speedup)**을 달성하며, 몽타나로의 알고리즘과 같은 기존의 양자 탐색 적응 모델보다 우수한 성능을 보인다. 디케 상태를 사용하여 필요한 초기 상태를 준비할 수 있는 능력은 실질적인 양자 키 탐색 배치의 핵심 장벽을 해결한다. 저자들은 이러한 결과가 노이즈가 포함된 키 형태의 사전 정보가 가용할 때 더 정확한 복잡도 추정과 더 효율적인 탐색 전략을 제공한다고 단언한다. 향후 연구 과제로 특정 암호(AES, SM4)와의 통합 및 양자 노이즈의 영향 분석을 제시하였다.