Parallel Kac's Walk Generates PRU

기술 요약: 병렬 카츠 워크(Parallel Kac's Walk)를 통한 PRU 생성

문제 정의

의사 난수 유니터리(Pseudorandom Unitaries, PRUs)—양자 다항 시간 구별자가 구별할 수 없으면서도 효율적으로 구현 가능한 유니터리 앙상블—의 구축은 양자 암호학에서 중요한 과제였습니다. **의사 난수 상태(Pseudorandom States, PRSs)**는 이전에 확립되었으나, PRU는 여まで도 난해한 과제로 남아 있었습니다.

최근 Metger, Poremba, Sinha, 그리고 Yuen [MPSY24]에 의한 PFC 구성(무작위 클리포드, 무작위 위상, 무작위 치환 게이트의 시퀀스)이 도입되었으며, 이후 Ma와 Huang [MH25]에 의해 적응적 보안성(adaptive-secure)이 있음이 증명되었습니다. 그러나 현재까지 알려진 모든 증명 가능한 보안 PRU 구성은 이 PFC 패러다임을 따릅니다. 본 연구에서 다루는 열린 질문은, 무작위 워크(random walks)에 기반한 대안적인 구성이 또한 PRU 보안성을 달성할 수 있는지 여부입니다.

방법론

저자들은 고전적인 카츠 워크(유니터리 군 위의 무작위 워크)를 양자 컴퓨팅에 맞게 변형한 **병렬 카츠 워크(Parallel Kac's Walk)**를 분석합니다. 병렬 카츠 워크의 단일 단계에서는 다음과 같은 과정이 수행됩니다:

1. 계산 기저(computational basis)에 무작위 치환 $\sigma$를 적용하여, $n-1$ 길이의 접미사(suffix)를 공유하는 기저 상태 $|i\rangle$와 $|j\rangle$를 쌍으로 묶습니다.
2. 각 쌍에 대해, 독립적인 $2 \times 2$ 하르-무작위(Haar-random) 유니터리를 적용합니다.

제안된 구성인 $HP_{n, T}$는 이 병렬 카츠 워크 단계를 $T$번 순차적으로 반복하는 것으로 구성되며, 여기서 무작위 함수와 치환은 양자 보안 대응물인 QPRF 및 QPRP로 대체됩니다. 저자들은 구성을 효율적(큐비트 수에 대해 선형)으로 유지하기 위해 $T = O(n)$ (구체적으로 $30n$)으로 설정했습니다.

증명 전략은 Ma와 Huang [MH25]가 도입한 **경로 기록 기술(path-recording technique)**을 카츠 워크의 특정 구조에 맞게 변형하여 활용합니다. 방법론은 다음 세 가지 주요 단계로 진행됩니다:

1. 서로 다른 블록 부공간으로의 투영(Projection to Distinct Block Subspace): 저자들은 먼저 $O(n)$ 단계의 병렬 카츠 워크가 **무작위 상태 스크램블러(Random State Scrambler, RSS)**로서 작용함을 입증합니다. 이후 무작위 치환이 뒤따를 때, 공격자의 상태는 높은 확률로 **서로 다른 블록 부공간(distinct block subspace)**으로 투영됩니다. 이 부공간에서 쿼리 튜플 $(x_1, \dots, x_t)$는 서로 다른 블록에 속하게 됩니다. 이 투영은 공격자의 쿼리가 이러한 서로 다른 블록들로 제한되어야 한다는 보안 분석에 있어 매우 중요합니다.

2. 순수화된 오라클 및 경로 기록(Purified Oracle and Path Recording): 저자들은 공격자가 무작위 유니터리 $H_f \cdot P_\sigma$와 상호작용하는 것을 모델링하기 위해 **순수화된 함수-치환 오라클(Purified Function-Permutation Oracle, HPO)**을 도입합니다. 또한, 서로 다른 블록에 속하는 출력들을 보장하도록 설계된, 서로 다른 블록에 특화된 새로운 **경로 기록 오라클(Path-Recording Oracle, PR)**을 정의합니다.

3. 등거리 사상(Isometry)을 통한 구별 불가능성: 핵심적인 기술적 기여는 HPO 오라클의 환경 상태를 경로 기록 오라클의 상태 공간으로 매핑하는 등거리 사상인 Compress의 구축입니다. 저자들은 공격자의 상태가 서로 다른 블록 부공간에 존재한다면(초기 $O(n)$ 단계에 의해 보장됨), 병렬 카츠 워크 단계의 동작이 경로 기록 오라클과 구별 불가능함을 증명합니다. 경로 기록 오라클은 이러한 제약 조건 하에서 하르-무작위 유니터리와 구별 불가능하므로, 전체 구성의 보안성이 증명됩니다.

주요 기여 및 결과

1. 적응적 보안 PRU 구성

본 논문은 선형 횟수의 순차적인 병렬 카츠 워크 반복이 적응적 보안 PRU를 형성함을 증명합니다.

• 정리 1 (비형식적): $O(n)$-단계 무작위 병렬 카츠 워크에 대응하는 유니터리의 분포는 적응적 공격자에 대해 하르 분포와 계산적으로 구별 불가능합니다.
• 정리 16: $HP_{n, T+1}$ ($T=30n$인 경우)이 하르 분포와 계산적으로 구별 불가능함을 공식적으로 확립합니다.

2. 역 쿼리에 대한 강력한 보안성

본 구성은 공격자가 순방향($O$) 및 역방향($O^\dagger$) 쿼리에 모두 접근할 수 있는 경우에도 구별 불가능함을 유지하는 **강력한 보안성(strong security)**을 만족함을 보여줍니다.

• 정리 33: $2T+1$ 단계(구체적으로 $HP_{n, 2T+1}$)를 사용함으로써, 본 구성은 통계적 강력한 보안성을 달 achieves 합니다. 이는 양자 후 암호학적 일방 함수(post-quantum one-way functions)의 가정 하에 계산적 강력한 PRU가 존재함을 시사합니다.

3. PFC 패러다임의 대안

본 연구는 PFC(클리포드-위상-치환) 패러다임에서 크게 벗어난 최초의 보안 PRU 구성을 제공합니다.

• 이 구성은 기본 "스크램블링" 모듈(병렬 카츠 워크 단계)의 반복으로 이루어져 있어 모듈식 구조를 가집니다.
• 이는 PRU 설계에 대한 새로운 관점을 제공하며, "필터"(예: 2-디자인 또는 RSS) 다음에 단일 단계의 "무작위성 컴파일러"(예: 병렬 카츠 워크)를 배치함으로써 완전한 PRU를 얻을 수 있음을 시사합니다.

4. 보안 조건의 일반화

저자들은 PRU 및 strong-PRU 구성을 위한 일반적인 조건(정리 32 및 정리 34)을 도출합니다. 이들은 특정 트위를잉(twirling) 연산(예: 근사 2-디자인 또는 RSS) 하에서 하르 무작위성을 근사하는 임의의 유니터리 분포 $K$가 병렬 카츠 워크의 단일 단계와 결합될 때 PRU를 생성함을 보여줍니다. 이는 새로운 PRU 후보를 생성하기 위한 템플릿을 제공합니다.

의의 및 주장

본 논문은 병렬 카츠 워크가 PRU를 생성할 수 있다는 [LQS+26]의 추측을 확인한다고 주장합니다. 그 의의는 다음과 같습니다:

• PRU 후보의 다양화: PFC 계열 이외의 구성을 제공함으로써, 단일 패러다임에 연관된 잠재적 취약성의 위험을 완화합니다.
• 경로 기록 기술의 다재다능함 입증: 본 연구는 카츠 워크 고유의 "서로 다른 블록" 구조를 처리할 수 있도록 경로 기록 기술을 확장하여, 다양한 양자 무작위 프로세스를 분석하는 데 있어 해당 기술의 적응성을 보여주었습니다.
• 고전 암호학과의 연결: 기본 모듈을 반복하는 이 구성의 반복적 성격은 AES나 페이스텔 네트워크(Feistel networks)와 같은 고전 블록 암호와 유사성을 띠며, 잘 알려진 이러한 구조들에 대한 양자적 아날로그를 제공합니다.

저자들은 자신들의 구성이 현재로서는 PFC 구성에 비해 점근적 효율성 측면에서 이점이 없다는 점을 언급하며 겸허한 태도를 유지합니다. 또한, 라운드 수를 상수로 줄일 수 있는지, 혹은 구성을 로컬 무작위 회로로 단순화할 수 있는지와 같은 열린 질문을 제시하며, 이는 양자 복잡도 이론의 오랜 문제를 해결할 수 있는 과제임을 밝힙니다.