기술 요약: 근미래 양자 컴퓨터를 위한 클래식 섀도우 기반 디지털 서명

문제 정의

전통적인 디지털 서명 방식은 정수 인수분해(RSA)나 격자 기반 문제(LWE)와 같은 일방향 함수(OWF)의 존재에 의존한다. 이러한 가정들은 결함 허용 양자 컴퓨터(예: 쇼어 알고리즘)에 취약하며, 양자 공격자에 대한 보안성을 두고 지속적인 연구 대상이 되고 있다. 양자 역학은 수학적 난해함이 아닌 물리 법칙에 근거한 대안적인 암호학적 프리미티브를 제공할 수 있지만, 기존의 양자 디지털 서명(QDS) 제안들은 일반적으로 공개 키로서 양자 상태의 전송과 결맞음 저장(coherent storage)을 필요로 한다. 이러한 양자 상태에 대한 의존성은 저노이즈 양자 통신과 긴 수명의 양자 메모리를 요구하므로, 현재의 제안들은 근미래 양자 장치에서 구현하기에 비실용적이다.

본 연구가 다루는 핵심 과제는 다음과 같은 조건을 충족하는 양자 디지털 서명 체계를 실현하는 것이다:

1. 일방향 함수(OWF)나 일방향 함수의 존재 여부에 의존하지 않는다.
2. 고전적 통신만을 사용하여 작동하며, 양자 메모리나 공개 키의 양자 전송 필요성을 제거한다.
3. 근미래의 노이즈가 있는 중간 규모 양자(NISQ) 하드웨어에서 실행 가능하다.

방법론

핵심 개념: 공개 키로서의 클래식 섀도우(Classical Shadows)

저자들은 공개 키가 양자 상태가 아니라 양자 상태의 클래식 섀도우인 서명 방식을 제안한다.

• 비밀 키: 두 개의 무작위 양자 회로 $C_0$와 $C_1$.
• 공개 키: 상태 $|C_b\rangle = C_b|0\rangle$에 대해 무작위 측정(randomized measurements)을 수행하여 생성된 클래식 섀도우 $S(|C_0\rangle)$ 및 $S(|C_1\rangle)$.
• 서명: 송신자는 비트 $b$를 서명하기 위해 회로 $C_b$의 고전적 설명을 공개한다.
• 검증: 수신자는 공개된 섀도우와 공개된 회로를 사용하여, 해당 회로 $C_b$가 공개 섀도우와 일치하는 상태를 생성하는지 검증한다. 이는 **섀도우 중첩 프로토콜(shadow overlap protocol)**을 통해 이루어진다.

보안 가정: 계산적 학습 불가능성(Computational No-Learning, CNL)

이 체계의 보안은 클래식 섀도우로부터의 계산적 학습 불가능성(CNL) 추측에 기초한다. 이 추측은 공격자가 양자 회로의 고전적 섀도우(무작위 측정의 다항 길이 샘플)만을 가지고 해당 회로의 기술(description)을 학습하는 것이 계산적으로 불가능하다는 가설이다.

• 이 가정은 표준적인 "상태로부터의 학습 불가능성" 추측보다 약하며 구별되는 개념으로, 섀도우는 단순 측정을 통한 상태 복사본으로부터 유도된다.
• 저자들은 기존의 학습 알고리즘(예: 로컬 역전 또는 라이트-콘(light-cone) 논리에 기반한 알고리즘)이 본 프로토콜의 제약 조건(적절한 학습, 임의의 기하학적 구조, 섀도우 전용 액세스) 하에서 이러한 회로를 학습하는 데 실패한다는 이론적 근거를 제시한다.
• 저자들은 서명을 검증하는 데 걸리는 시간(검증자에게는 지수적이지만 실행 가능한 수준)과 회로를 학습(위조)하는 데 걸리는 시간(지수적으로 더 어려운 수준) 사이의 격차를 입증한다.

기술적 혁신

노이즈가 있는 하드웨어에서도 이 체계를 실행 가능하게 만들기 위해, 저자들은 두 가지 핵심 기술적 개선 사항을 도입했다.

1. 개선된 섀도우 중첩 프로토콜: 단순히 무작위 파울리 측정을 사용하는 대신, 큐비트의 부분 집합에 무작위 **클리포드 회로(Clifford circuits)**를 사용하는 방식으로 기존의 섀도우 중첩 프로토콜(참조 [30] 기반)을 수정하였다. 이는 인증 마르코프 체인의 "이완 시간(relaxation time, $\tau$)"을 줄이고 추정치의 분산을 낮추어, 노이즈 내성을 크게 향상시키고 인증에 필요한 샘플 복잡도를 감소시킨다.
2. 양자 오류 탐지(QED): 하드웨어의 부정확성을 극복하기 위해, 저자들은 다중 블록 아이스버그(Iceberg) 오류 탐지 코드를 사용한다.
   • 아이스버그 코드는 $k$개의 논리 큐비트를 $k+2$개의 물리 큐비트로 인코딩한다.
   • 저자들은 특정 논리 연산자를 스테빌라이저(stabilizer)로 승격시키기 위해 **게이지 고정(gauge fixing)**을 활용하며, 이를 통해 "프록시(proxy)" 큐비트를 생성하여 단일 큐비트 논리 게이트의 병렬화를 가능하게 함으로써 회로 깊이와 메모리 오류를 줄인다.
   • 이 접근 방식은 인코딩된 충실도가 오버헤드에도 불구하고 인코딩되지 않은 충실도보다 높게 나타나는 "브레이크-이븐(break-even) 너머"의 성능을 달را한다.

주요 결과

이론적 근거

• 학습의 어려움: 저자들은 얕은 회로를 학습하는 알려진 알고리즘들이 본 체계를 깨뜨리기 위해 필요한 조건(적절한 학습, 임의의 기하학적 구조, 섀도우 전용 액세스)을 충족하지 못함을 보여준다.
• 보안 격차: 특정 회로 앙상블(근사 설계)에 대해, 저차 다항식이나 변분 학습(variational training)을 통해 회로를 학습하는 데 걸리는 시간 복잡도가 검증에 필요한 시간보다 지수적으로 크다는 것을 증명한다. 구체적으로, 사용된 회로 깊이에서 목표 충실도에 도달하기 위해 변분 학습이 지수적으로 많은 쿼리를 필요로 함을 보여준다.

실험적 시연

저자들은 Quantinuum H2 트랩 이온 프로세서(56 물리 큐비트)를 사용하여 프로토콜을 구현했다.

• 회로 파라미터: 80개 이상의 논리 2-큐비트 게이트(582개 이상의 물리 2-큐비트 게이트에 해당)를 가진 무작위 회로를 사용하여 32-큐비트 상태의 섀도우를 생성했다.
• 충실도: 게이지 고정을 적용한 다중 블록 아이스버그 코드를 사용하여, 17,316개의 샘플로 $0.90 \pm 0.01$의 인증된 충실도를 달성했다.
• 개념 증명: 실험은 정직한 서명자와 공격자를 구별할 수 있음을 성공적으로 입증했다. 저자들은 샘플 크기를 19.5배(약 340k 샘플) 늘리면, 계산 능력이 제한된 공격자가 서명을 위조할 확률이 무시할 수 있는 수준($< 10^{-5}$)이 되는 보안 파라미터를 달성할 수 있다고 계산했다.

의의 및 주장

본 논문은 일방향 함수(OWF)나 양자 통신에 의依赖하지 않는 근미래 실행 가능한 양자 디지털 서명의 가능성을 입증한다고 주장한다.

• OWF로부터의 독립성: 이 체계는 보안의 근거를 양자 프로세스를 학습하는 물리적 어려움에 두며, 이는 OWF가 존재하지 않더라도 안전할 수 있는 암호화 경로를 제공한다.
• NISQ 호환성: 전체 오류 수정 대신 클래식 섀도우와 오류 탐지 코드를 활용함으로써, 프로토콜은 현재의 노이즈가 있는 양자 하드웨어 역량 내에서 작동한다.
• 기초적인 프리미티브: 본 연구는 양자 디지털 서명과 일방향 퍼즐(one-way puzzles) 사이의 연결 고리를 확립하며, 이는 OWF를 가정하지 않고도 다른 양자 암호 프로토콜(예: 비대화형 비트 커밋먼트)을 구축할 수 있게 하는 프리미티브이다.

저자들은 현재의 시연이 단일 비트 서명에 대한 개념 증명이지만, 그 기저에 깔린 프리미티브(섀도우 중첩 인증 및 오류 탐지)는 확장 가능하다는 점을 강조한다. 또한, 검증 비용을 줄이기 위해 고전적 오류 정정 코드를 사용하여 다중 비트 메시지로 확장하는 것이 가능하며, 회로 크기를 키움으로써 잠재적인 미래의 학습 알고리즘 돌파구에 대한 보안성을 더욱 강화할 수 있다고 언급한다.