Where Quantum Fourier Sampling Stops Short: A Three-Gate Audit Protocol for Delay-PUF Security Models

기술 요약: 양자 푸리에 샘플링이 한계에 부딪히는 지점

문제 정의
지연 기반 물리적 복제 불가능 함수(PUF)는 저장된 비밀값이 아닌 제조 공정의 변이를 통해 장치의 신원을 도출한다. 이들의 보안은 근본적으로 학습 문제이다: 즉, 공격자가 도전-응답 쌍(CRP)으로부터 장치의 응답 함수를 모델링할 수 있는가 하는 문제이다. 선형 모델링과 같은 고전적 공격은 단순한 아비터(Arbiter) PUF를 위협하지만, XOR-아비터 PUF와 같은 복잡한 구조는 이를 저항하도록 설계되었다. 양자 푸리에 샘플링(QFS)은 푸리에 계수의 제곱에 비례하는 확률로 푸리에 특성(Fourier characters)을 샘플링함으로써, 이러한 함수들의 '스펙트럼 학습 가능성'을 직접 식별할 수 있는 경로를 이론적으로 제공하는 잠재적 감사 도구로 제안되어 왔다.

그러나 기존의 분석들은 결정적인 구현 및 접근 제약 사항을 간과하는 경우가 많다. 구체적으로, 이들은 일관된 양자 오라클(coherent quantum oracle)의 비용을 고전적 멤버십 쿼리(classical membership queries)와 혼동하거나, "저차수(low-degree)" 집중이 실질적인 도전 길이($n$)에서 "작은 서포트(small support)" 집합을 의미한다고 가정할 수 있다. 본 논문은 적절한 접근 모델을 맞추고, 구조적 희소성을 고려하며, 물리적 구현 비용을 평가하는 엄격한 감사를 통해 QFS의 약속이 생존할 수 있는지 조사한다.

방법론: 3단계 게이트 양자 감사 프로토콜
저자들은 이상적인 쿼리 이점과 실현 가능한 보안 이득을 구분하기 위해 세 가지 결정 기준("게이트")으로 구성된 재현 가능한 평가 프레임워크를 제안한다.

1. 구조적 게이트(Structural Gate): 이 게이트는 도달 가능한 도전 길이($n$)에서 PUF의 푸리에 스펙트럼이 충분히 희소한지를 테스트한다. 이는 '저차수' 집중(이론적 속성)과 '작은 서포트'(효율적 샘플링을 위한 실질적 요구사항)를 구분한다. 저자들은 허용 가능한 서포트 크기 $L(n, d)$와 전체 공간 $2^n$의 비율, 그리고 푸리에 질량의 90%를 축적하는 가장 작은 집합의 크기를 평가한다.
2. 알고리즘 게이트(Algorithmic Gate): 이 게이트는 "접근 매칭(access matching)"을 강제한다. 양자 위상 오라클(quantum phase oracle)을 구축하는 것은 논리적으로 고전적 모델(및 그에 따른 고전적 멤버십 접근)의 존재를 함의하므로, 양자 샘플러는 동일한 접근 권한을 가진 강력한 고전적 베이스라인과 비교되어야 한다. 저자들은 쿠실레비츠-맨서(Kushilevitz–Mansour, KM) 알고리즘을 비교 대상으로 사용한다. 또한, 훈련 전 양자 커널 맵이 고전적 커널에 비해 실질적인 이점을 제공하는지 확인하기 위해 양자 커널 진단(기하학적 차이 $g_{CQ}$)을 채택하며, 레이블 순열을 통해 컨디셔닝 효과를 제어한다.
3. 구현 게이트(Implementation Gate): 이 게이트는 가역적 위상 오라클의 물리적 실행 가능성을 평가한다. 이는 타겟 응답 위상을 재현하고, 워크스페이스를 계산 해제(uncompute)하며, 감사 신호를 보존하는 양자 푸리에 변환(QFT) 기반의 정밀한 고정점 위상 오라클을 요구한다. 저자들은 정적 백엔드 스냅샷(FakeSherbrooke)에서 이를 시뮬레이션하여, 큐비트 $T_2$ 시간 대비 라우팅 깊이, 지속 시간 및 결맞음(coherence) 요구사항을 추정한다.

주요 결과

• 구조적 실패 (희소성): 도달 가능한 도전 길이(예: $n=14$)에서 저차수 집중은 작은 서포트를 보장하지 않는다. 중앙값 차수가 $d=9$인 4-XOR PUF의 경우, 차수-9 영역은 전체 $2^{14}$ 캐릭터 중 **91.02%**를 수용한다. 90%의 푸리에 질량을 포착하는 데 필요한 중앙값 집합은 스펙트럼의 **32.90%**에 달한다. $n$이 증가함에 따라 이러한 비율은 여전히 크게 유지되어, 효율적인 양자 샘플링을 위한 희소한 타겟을 제공하지 못한다.
• 알고리즘 실패 (복구 및 커널):
  • 푸리에 복구: 이상적인 QFS 샘플러는 결맞은 호출(coherent calls) 측면에서 KM보다 임계값 밀집 캐릭터를 더 빠르게 복구하지만, 어떤 4-XOR 인스턴스에 대해서도 $2^n$ 호출 예산 내에서 전체 푸리에 질량의 90%에 도달하지 못한다. 반대로, KM은 유한한 도메인을 모두 소진하지만 질량이 넓게 퍼져 있기 때문에 매우 적은 질량(90% 질량 집합의 중앙값 4.1% 회수)만을 포착한다. 구속 요인은 단순히 알고리즘의 선택이 아니라 스펙트럼의 확산성(diffuseness)이다.
  • 커널 진단: 양자 및 고전 그람 행렬(Gram matrices) 사이의 기하학적 차이 $g_{CQ}$는 유리한 양상($N=512$에서 2.151까지 상승)을 보였다. 그러나 이러한 증가는 고전 그람 행렬의 최소 고유값의 역 제곱근($1/\sqrt{\lambda_{min}(K_C)}$)과 0.991의 상관관계를 보였다. 레이블 특이성을 제어하기 위해 균형 보존 순열을 사용하여 검증했을 때, 4-XOR 레이블 복잡도 비율은 영 분포(null distribution)를 초과하지 못했으며($p=0.930$), 이는 특정 작업에 대한 양자 정렬이 없음을 나타낸다.
• 구현 실패 (결맞음): 정밀한 고정점 위상 오라클이 구축 및 최적화되었다. 이는 전체 QFT에 비해 라우팅 깊이를 18.9% 감소시켰으나, 최소 인증 정밀도(정확도 기준 충족을 위해 필요)를 위한 예상 지속 시간은 매핑된 큐비트의 중앙값 디페이징 시간($T_2$)의 1.18에서 1.55배 사이였다. 시뮬레이션된 백엔드에서 정확도 기준과 결맞음 시간 임계값을 모두 만족하는 테스트된 정밀도는 없었다.

의의 및 주장
본 논문은 평가된 지연-PUF 감사 범위 내에서 종단 간 이점(end-to-end advantage)이 존재하지 않는다고 결론짓는다. "3단계 게이트 양자 감사 프로토콜"은 이상적인 쿼리 복잡도와 실현 가능한 보안 이득 사이의 분리를 강제함으로써, 이상적인 이론적 이점이 현실적인 제약 하에서 어디에서 무너지는지를 성공적으로 격리해 냈다:

1. 접근 매칭: 양자 오라클은 고전적 모델을 함의하므로 KM 알고리즘이 올바른 베이스라인이며, 이는 스펙트럼 희소성의 결여를 드러낸다.
2. 구조적 실체: "저차수"만으로는 불충분하다. 실질적인 $n$에서 서포트는 여전히 너무 크다.
3. 물리적 한계: 최적화된 회로를 사용하더라도, 요구되는 결맞음 시간은 현재의 정적 백엔드 능력을 초과한다.

저자들은 이것이 모든 양자 학습에 대한 불가능성 결과나 배치된 실리콘에 대한 주장이 아님을 명시한다. 오히려 이는 균등한 도전에 대한 시뮬레이션된 지연-PUF 모델의 특정 범위에 대한 부정적 결과이다. 주요 기여는 프로토콜 자체이다: 이상적인 쿼리 복잡도와 실현 가능한 보안 이득 사이의 간극을 드러내어, 근거 없는 양자 보안 이점 주장을 방지하기 위한 엄격하고 재현 가능한 절차를 제공하는 것이다. 본 논문은 향후의 주장들이 반드시 접근 클래스를 명시하고, 농축 분모(concentration denominators)를 포함하며, 오라클 구현 비용을 고려해야 한다고 강조한다.