Certified Randomness without Structure Against Shallow-Query Adversaries

기술 요약: 얕은 쿼리 적대자(Shallow-Query Adversaries)에 대한 구조 없는 인증된 무작위성

문제 정의
본 논문은 양자 랜덤 오라클 모델(QROM)에서 *인증 가능한 무작위성(certifiable randomness)*을 생성하는 과제를 다룹니다. 양자 역학은 본질적인 확률성을 제공하지만, 고전적 검증자는 양자 증명자가 진정으로 이 무작위성을 활용하고 있는지, 아니면 편향되거나 미리 결정된 답을 출력하고 있는지를 신뢰할 수 있어야 합니다.

최근 Yamakawa와 Zhandry(YZ24)의 프로토콜은 리스트 복구 가능 코드(list-recoverable code) $C$로부터 모든 좌표 $i$에 대해 $H_i(x_i) = 0$을 만족하는 코드워드 $\mathbf{x}$를 찾는 방식의 양자성 증명을 제안했습니다. 여기서 $H$는 랜덤 오라클입니다. 정직한 YZ 알고리즘의 핵심 특징은 그 출력이 본질적으로 무작위적(유효한 코드워드들로부터의 균등 샘플링)이라는 점입니다. YZ는 모든 성공적인 증명자가 높은 엔트로피를 가진 분포에서 샘플링해야 한다고 추측하였으며, 이를 통해 해당 프로토лот을 인증된 무작위성의 원천으로 변모시켰습니다.

이전에 YZ는 이 추측을 Aaronson-Ambainis (AA) 추측 하에서만 증명했습니다. AA 추측은 양자 가속도가 입력 도메인 내의 근본적인 구조를 필요로 한다는 구조적 가설입니다. AA 추측은 일반적으로 아직 미해결 상태입니다. 저자들은 질문합니다: AA 추측에 의존하지 않고, YZ 프로토콜의 인증된 무작위성 보장을 확립할 수 있는가?

방법론 및 기술적 접근
저자들은 특정 클래스의 적대자, 즉 랜덤 오라클에 대해 최대 $o(\log \lambda)$ 번의 적응적 쿼리 라운드를 수행하는 적대자(단, 각 라운드 내에서는 다항식 개의 병렬 쿼리를 수행할 수 있음)에 대해 무조건적인 보안 증명을 제공합니다. 증명 전략은 "쿼리 가중치(query weight)" 분석과 오라클 재프로그래밍(oracle reprogramming)을 이용한 계수 논증(counting argument)에 기반합니다.

1. 쿼리 가중치와 스와핑 보조정리(Swapping Lemma):
   중심적인 분석 도구는 쿼리 레이어 전반에 걸쳐 양자 적대자의 쿼리 레지스터가 특정 심볼 $(i, x_i)$를 측정할 누적 확률인 쿼리 가중치입니다. 저자들은 오라클이 특정 입력 세트에서 재프로그래밍될 때 적대자의 양자 상태가 변화하는 정도를 해당 입력들에 대한 총 쿼리 가중치에 대한 함수로 제한하는 스와핑 보조정리를 활용합니다. 만약 적대자가 특정 입력 세트에 낮은 가중치를 부여한다면, 해당 입력들을 재프로그래밍하더라도 적대자의 출력 분포에는 거의 변화가 없습니다.

2. 1단계: 저엔트로피 적대자는 자신의 답에 대해 "강하게 쿼리"해야 한다:
   저자들은 만약 적대자가 높은 확률로 올바른 코드워드 $\mathbf{x}$를 출력한다면, $\mathbf{x}$의 거의 모든 심볼에 대해 비영(non-negligible)의 쿼리 가중치를 할당해야 함을 증명합니다.

• 논증: 만약 적대자가 $\mathbf{x}$를 높은 확률로 출력하면서도 많은 심볼에 대해 작은 가중치를 부여한다면, 해당 낮은 가중치의 심볼들의 해시 값을 0에서 1로 뒤집음으로써 "나쁜(bad)" 오라클 세트를 구성할 수 있습니다. 스와핑 보조정리에 의해, 적대자의 행동은 이러한 나쁜 오라클에서도 거의 변하지 않으며, 이는 $\mathbf{x}$가 더 이상 유효한 솔루션이 아님에도 불구하고 여전히 $\mathbf{x}$를 출력할 것임을 의미합니다. 계수 논증을 통해, 이러한 "나쁜" 오라클의 수가 "좋은" 오라클의 수보다 훨씬 많다는 것을 보여줌으로써, 적대자가 답을 강하게 쿼리하지 않는 한 모순이 발생함을 입증합니다.

3. 2단계: 저심도(Low-Depth) 적대자는 올바른 답에 대해 강하게 쿼리할 수 없다:
   핵심 기여는 적응적 깊이($D = o(\log \lambda)$)가 제한된 적대자가 오라클에 대해 충분히 학습하기 전에 특정 올바른 코드워드에 충분한 쿼리 가중치를 집중시킬 수 없음을 보여주는 것입니다.

• 부트스트래핑(Bootstrapping) 논증: 단일 쿼리 케이스와 달리, 적응적 쿼리는 가중치가 이전 오라클 응답에 의존하게 만듭니다. 저자들은 일련의 성장하는 임계값(growing thresholds) $t_0 < t_1 < \dots < t_D$를 도입합니다. 저자들은 적대자가 코드워드의 $(1-\zeta)n$ 개 심볼에 대해 상당한 가중치를 처음으로 축적하는 임계 레이어 $q^*$를 식별합니다.
• 재프로그래밍 전략: 레이어 $q^*$ 직전에, 적대자는 적어도 $\zeta n$ 개의 심볼에 대해 임계값에 도달하지 못한 상태입니다. 저자들은 이 낮은 가중치의 심볼들을 재프로그래밍합니다. 임계값의 재귀 관계를 사용하여, 재프로그래밍으로 인한 섭동(perturbation)이 충분히 작아서 적대자가 새로운 오라클 하에서도 (비록 코드워드가 이제는 유효하지 않더라도) 여전히 해당 코드워드를 "강하게 쿼리"하게 됨을 보여줍니다.
• 계수: 코드의 리스트 복구 가능성(이는 어떤 심볼 리스트와도 일치하는 코드워드의 수를 제한함)과 서로 다른 '좋은 쌍(good pairs)'에 의해 생성된 서로 소인 나쁜 오라클 세트를 결합함으로써, 적대자가 올바른 코드워드를 성공적으로 강하게 쿼리할 확률이 무시할 수 있는 수준임을 보여줍니다.

주요 기여 및 결과

• 무조건적 보안: 본 논문은 Yamakawa-Zhandry 프로토콜의 인증된 최소 엔트로피 성질을 무조건적으로 증명하여, 미해결 상태인 Aaronson-Ambainis 추측에 대한 의존성을 제거했습니다.
• 정리 1.1 (비형식적): 프로토콜은 임의의 쿼리 깊이 $D(\lambda) = o(\log \lambda)$와 최소 엔트로피 경계 $h_\infty(\lambda) = o(\lambda^{c/2})$에 대해 $(D, h_\infty)$-인증된 최소 엔트로피를 만족합니다. 이는 검증자를 유의미한 확률로 수락하게 만드는 $o(\log \lambda)$ 라운드의 적응적 쿼리를 수행하는 모든 적대자는 $\Omega(\lambda^{c/2})$ 비트의 최소 엔트로피를 가진 분포에서 샘플링하고 있음을 의미합니다.
• 기술적 한계: 본 증명은 현재 $o(\log \lambda)$ 적응적 라운드로 제한됩니다. 저자들은 임계값이 라운드 수에 따라 이중 지수적으로 성장해야 하는 임계값 부트스트래핑 기법의 특성상, $O(\log \lambda)$를 초과하면 계수 논증에 필요한 경계를 벗어나게 된다고 언급했습니다.

의의
본 논문은 Yamakawa-Zhandry 프로토콜의 무작위성이 단순히 그들의 특정 알고리즘에 의한 결과물이 아니라, 얕은 쿼리 적대자에 대한 모든 성공적인 전략의 필수적인 특징임을 입증합니다. 이는 인증된 무작위성의 토대를 양자 가속의 본질에 관한 광범위하고 미해결된 추측이 아니라, 근본적인 탐색 문제의 어려움과 리스트 복구 가능 코드의 구조적 특성에만 의존하도록 강화합니다. 이 연구는 양자 쿼리 복잡도에 대해 알려진 바와 실질적인 암호 프로토콜의 보안 사이의 간극을 좁히며, 특히 적응적 깊이가 제한된 적대자에 대한 보안을 확립합니다.