기술 요약: 함수형 의사 난수 유니터리(Function-like Pseudorandom Unitaries)를 통한 의사 난수 양자 프로세스 생성

문제 정의

Haar-난수 유니터리는 일반적인 무작위 양자 진화의 표준 모델로서, 디커플링(decoupling), 정보 스크램블링(information scrambling), 양자 암호학 등의 현상을 뒷받침한다. 그러나 전형적인 Haar-난수 유니터리는 지수적인 기술(description) 및 회로 복잡도를 가지므로 실제 구현이 불가능하다. 의사 난수 유니터리(PRU)는 단일한 무작위 진화에 대해서는 효율적인 대안을 제공하지만, 많은 암호학적 및 물리적 과업은 공공 컨텍스트(예: 논스(nonce), 레지스터 폭 또는 타임 스텝)에 의해 인덱싱된 일련의 독립적인 무작위 유사 연산들을 필요로 한다.

이러한 패밀리를 생성하기 위한 기존 방식, 예를 들어 각 컨텍스트마다 독립적인 PRU 키를 샘플링하는 방식은 거대하고 동적으로 증가하는 비밀 키 집합을 관리해야 하는 오버헤드 때문에 비실용적이다. 또한, 표준 PRU는 적응형(adaptive)으로 여러 인스턴스를 쿼리하는 적대자와 상호작용하는 적응형 양자 쿼리에 대해 본질적인 보안을 제공하지 못한다. 본 논문은 단 하나의 짧은 마스터 키로부터 적응형으로 주소 지정이 가능한 전체 의사 난수 유니터리 패밀리를 생성하면서도, 적대자가 패밀리를 적응적이고 코히어런트하게(coherently) 쿼리할 수 있는 상황에서도 보안을 유지하는 프리미티브(primitive)의 필요성을 다룬다.

방법론

저자들은 단일 키 $k$와 공공 레이블 $x$에 의해 효율적으로 구현 가능한 유니터리가 결정되는 키 기반 패밀리 $\{G_k(x)\}_{x \in \mathcal{X}_\lambda}$인 **의사 난수 함수형 유니터리(Pseudorandom Function-like Unitaries, PRFU)**를 도입한다. 보안 목표는 각 레이블 $x$가 독립적으로 샘플링된 Haar-난수 유니터리 $H_x$로 매핑되는 함수형 Haar 패밀리와의 계산적 구별 불가능성이다.

본 논문은 레이블 $x$에 대한 두 가지 액세스 모델을 구분한다:

1. 클래식 레이블 액세스(Classical-label access): 레이블이 클래식 비트 문자열로 공급된다. 데이터 및 참조 레지스터는 양자 상태를 유지한다.
2. 코히어런트 레이블 액세스(Coherent-label access): 레이블이 양자 레지스터 $L$ 내에 공급되며, 중첩 상태이거나 다른 레지스터와 얽혀 있을 수 있다. 오라클은 제어 유니터리 $W_k = \sum_x |x\rangle\langle x|_L \otimes G_k(x)$를 적용한다.

구성(Constructions)

1. 클래식 레이블 구성:
저자들은 포스트 퀀텀 의사 난수 함수(PRF) $F_k$와 적응형 포워드 PRU 패밀리 $\{V_a\}$를 결래히는 일반적인 구성을 제안한다. 이 구성은 다음과 같이 정의된다:
$$G_k(x) := V_{F_k(x)}$$
여기서 PRF는 내부 PRU의 시드 $a = F_k(x)$를 도출한다. 보안 증명은 레이블이 처음 나타나는 순서대로 처리하는 "지연된 테이블(deferred table)" 하이브리드 논증을 활용한다. 핵심 요소는 중간 단계의 하이브리드를 시뮬레이션하기 위해 (증폭된 상대 오차 Permutation-Function-Clifford (PFC) 설계로부터 유도된) 효율적으로 구현 가능한 Haar 프록시를 사용하는 것이다. 이를 통해 내부 PRU가 모든 가능한 쿼리에 대해 완전한 Haar 프록시일 필요 없이, 적대자가 수행하는 제한된 수의 쿼리에 대해서만 동작하도록 함으로써 차별 우위를 바운드하는 환원을 가능하게 한다.

2. 코히어런트 레이블 구성:
코히어런트 액세스를 위해, 저자들은 **인덱스된 PFC 앙상블(indexed PFC ensemble)**을 사용하여 직접 PRFU를 구축한다. 키를 통해 키를 도출하는 대신, 레이블 $x$를 위상(phase) 및 치환(permutation) 프리미티브에 직접 포함시킨다. 이 구성은 다음을 사용한다:

• 위상 레이어를 위한 양자 보안 의사 난수 함수(qPRF) $g_{k_\Phi}(x, z)$
• 치환 레이어를 위한 튜커블 인플레이스 의사 난수 치환(qPRP) $\Pi_{k_P}(x, z)$
• 공유 유니터리 2-디자인 $C$
  결과 유니터리는 $W_k^{coh} = \hat{P}_{\Pi} \hat{\Phi}_{g} (I_L \otimes C)$이다.
  보안은 인덱스된 경로 기록(indexed path-recording) 기법을 사용하여 확립된다. 이 방법은 레이블의 중첩을 포함하는 쿼리 이력을 추적하여 간섭을 분석한다. 증명은 이상적인 인덱스된 PFC 앙상블이 $q$가 쿼리 횟수이고 $N=2^n$일 때, $2q(q-1)/(N+1)$의 범위 내에서 독립적인 Haar 유니터리와 통계적으로 구별 불가능함을 보여준다. 계산적 보안은 무작위 프리미티브를 양자 보안 대응물로 교체함으로써 확보된다.

양자 프로세스로의 확장

본 논문은 PRFU를 의사 난수 양자 채널 및 **양자 콤(quantum combs, 내부 메모리를 가진 프로세스)**을 생성하도록 확장한다.

• 채널: 스틴스프리 dilation(Stinespring dilation) 내에서 PRFU를 적용하고 환경을 버림으로써, 저자들은 의사 난수 함수형 채널(PRFC)을 생성한다.
• 콤: 양자 콤의 연속적인 "치아(teeth, 연산)"에 서로 다른 PRFU 레이블을 할당함으로써, 저자들은 의사 난수 콤을 구축한다. 이를 통해 적응적 개입 및 동시 세션에 대해 안전한, 접근 불가능한 메모리를 가진 다중 시간 역학(multi-time dynamics)의 에뮬레이션을 가능하게 한다.

주요 기여

1. PRFU의 정의: 공공 레이블에 의해 인덱싱된 일련의 무작위 유사 유니터리를 생성하는 의사 난수 함수형 유니터리의 형식화.
2. 클래식 레이벨 구성 및 보안: 포스트 퀀텀 PRF와 PRU를 결합한 일반적 구성을 제안하고, 하이브리드 논증과 Haar 프록시를 사용하여 적응형 클래식 레이블 쿼리에 대한 보안을 증명함.
3. 코히어런트 레이블 구성 및 보안: qPRF와 튜커블 인플레이스 qPRP를 사용하는 인덱스된 PFC 앙상블 기반의 특정 구성을 제시함. 보안은 레이블 중첩과 간섭을 처리하기 위해 인덱스된 경로 기록을 통해 증명됨.
4. 프로세스 리프팅(Process Lifting): PRFU를 양자 채널 및 양자 콤으로 리프팅하여, 적응적 및 동시적 상호작용으로부터 내부 메모리를 갖는 프로세스를 보호하는 것을 입증함.
5. 가변 폭 PRU(Variable-Width PRUs): PRFU와 유니터리 글루잉(gluing)을 결합하여, 키 생성 후 레지스터 폭을 적응적으로 선택할 수 있는 단일 키 기반의 PRU 패밀리를 생성하는 방법.
6. 응용 분야: 다음과 같은 특정 응용 분야를 개괄함:
   • 논스 해결형 양자 인증(Nonce-resolved quantum authentication).
   • 코히어런트하게 마스킹된 QRAM 쿼리 (포워드 액세스 관찰자로부터 데이터베이스 내용을 숨김).
   • 무작위 다중 시간 역학의 효율적 에뮬레이션.

결과

• 보안 바운드: 클래식 레이블의 경우, 차별 우위는 PRF 우위, PRU 우위, 그리고 Haar 프록시 오차($2q\eta$)에 의존하는 항의 합으로 제한된다. 코히어런트 레이블의 경우, 이상적인 Haar 패밀스와의 통계적 거리는 $2q(q-1)/(N+1)$로 제한되며, 계산적 보안은 기저가 되는 qPRF 및 qPRP의 어려움에 의존한다.
• 효율성: 구성은 효율적이며, 보안 파라미터 $\lambda$ 및 쿼리 수에 대해 다항 시간 및 회로 크기를 요구한다.
• 가변 폭: 글루잉 구성은 키 생성 후 선택된 다항식 범위의 레지스터 폭에 대해 의사 난수 유니터리를 성공적으로 생성하며, 다양한 폭에 대해 보안이 유지된다.

의의 및 주장

본 논문은 양자 의사 난수의 개념을 개별 연산에서 효율적으로 생성되는 일련의 무작ัด 유사 양자 역학 패밀리로 확장한다고 주장한다. PRFU를 도입함으로써, 저자들은 단일 인스턴스 PRU와 고도화된 양자 프로토콜에 필요한 재현 가능하고 컨텍스트 의존적인 무작위 진화 사이의 간극을 메운다.

본 연구는 다음을 강조한다:

• 단일 키 패러다임: 독립적인 PRU 샘플링의 키 관리 문제를 피하면서, 단 하나의 짧은 마스터 키로부터 적응형으로 주소 지정 가능한 전체 의사 난수 유니터리 패밀리를 도출할 수 있다.
• 코히어런트 보안: 특정 인덱스된 경로 기록 기법을 통해, 레이블이 중첩 상태로 쿼리되는 경우에도 보안을 유지할 수 있으며, 이는 클래식 레이블 보안보다 강력한 요구사항이다.
• 프로세스 보안: 본 프레임워크는 내부 메모리를 가진 복잡한 양자 프로세스(채널 및 콤)로 자연스럽게 확장되어, 단계 사이에 개입하거나 동시 세션을 실행하는 적대자로부터 보안을 제공한다.

저자들은 클래식 레이블의 경우 (PRF 리프팅을 통해) PRU와 PRFU의 관계가 명확하지만, 코히어런트 레이블의 경우 그들의 구성이 단일 인스턴스 PRU로부터의 일반적인 변환이 아닌 특정 프리미티브에 의존하므로, 두 관계 사이의 관계는 여전히 미해결 과제로 남아 있다고 언급한다. 또한, 표준 가정으로부터 요구되는 튜커블 인플레이스 qPRP를 구성하는 것은 향-후 구현을 위한 구체적인 미해결 과제이다.