On Limits on the Provable Consequences of Quantum Pseudorandomness

이 논문은 양의 무작위성 (quantum pseudorandomness) 의 다양한 개념들이 고전적 경우와 달리 서로 등가적이지 않을 수 있음을 보여주기 위해, 로그 길이의 출력 PRFSG 는 존재하지만 양자 계산 가능한 의사난수 생성기 (QPRG) 는 존재하지 않는 단위 오라클 분리를 증명하고, 이를 위해 새로운 기하학적 장벽 정리를 제시합니다.

핵심

이 논문은 양자 컴퓨팅과 암호학의 세계에서 **"가짜 무작위성 (Pseudorandomness)"**이 어떻게 작동하는지에 대한 흥미로운 발견을 담고 있습니다.

쉽게 말해, **"우리가 양자 컴퓨터로 만든 '가짜 난수'는 고전적인 컴퓨터의 그것과는 완전히 다른 규칙을 따를 수 있다"**는 것을 증명하는 연구입니다.

이 복잡한 내용을 일상적인 비유로 풀어서 설명해 드릴게요.

---

1. 배경: 진짜와 가짜의 차이 (난수 생성기)

우리가 암호를 만들 때 '난수 (무작위 숫자)'가 필요합니다.

• 고전적 세계: 컴퓨터는 '가짜 난수 생성기 (PRG)'를 통해 진짜처럼 보이는 숫자를 만듭니다. 이걸로 암호를 만들면, 외부인은 진짜 난수인지 가짜인지 구별할 수 없습니다. 고전 암호학에서는 이 '가짜 난수'만 있으면 모든 암호 체계 (지문, 서명, 암호화 등) 를 만들 수 있다고 믿었습니다.
• 양자 세계: 양자 컴퓨터는 '양자 상태'라는 새로운 자원을 가집니다. 여기서 '양자 가짜 난수 (PRSG)'나 '양자 가짜 함수 (PRFSG)' 같은 개념이 등장합니다.

핵심 질문: "양자 세계에서도 고전 세계처럼, '짧은 가짜 난수'만 있으면 모든 복잡한 암호를 만들 수 있을까?"

2. 이 논문의 주요 발견: "양자는 고전과 다르다!"

연구자들은 **"아니요, 양자 세계는 그렇게 간단하지 않습니다"**라고 답했습니다. 고전 세계에서는 서로 다른 난수 개념들이 모두 서로 변환 가능했지만, 양자 세계에서는 어떤 것은 만들 수 있어도 다른 것은 절대 만들 수 없는 경우가 있다는 것을 증명했습니다.

이를 세 가지 재미있는 비유로 설명해 볼게요.

비유 1: "완벽한 주사위 vs 불완전한 주사위" (QPRG 분리)

• 상황: 우리는 아주 작은 씨앗 (Short PRSG) 을 가지고 아주 긴 난수열 (QPRG) 을 만들어내려 합니다. 고전 세계에서는 씨앗 하나면 원하는 만큼의 난수를 뽑아낼 수 있습니다.
• 문제: 연구자들은 "양자 세계에서는 이 씨앗을 아무리 키워도, 완벽하게 예측 불가능한 (오류가 0 에 가까운) 난수를 뽑아낼 수 없다"는 것을 증명했습니다.
• 비유: 마치 "작은 씨앗을 심어 거대한 나무를 키우려는데, 양자 세계에서는 그 나무가 항상 약간 시들거나 (오류 발생) 잎이 떨어지는 현상이 필연적으로 발생한다"는 것입니다.
• 의미: 양자 컴퓨터로 만든 암호는 완벽하게 안전하지 않을 수 있으며, 이는 고전 암호학의 상식을 깨는 결과입니다.

비유 2: "보이지 않는 보조 도구 (Ancilla) 의 중요성" (PRU 분리)

• 상황: 우리는 '양자 가짜 함수 (PRFSG)'를 가지고 '양자 가짜 순열 (PRU, 일종의 암호화 키)'을 만들려고 합니다.
• 문제: 연구자들은 **"보조 도구 (Ancilla, 계산 중 임시로 쓰는 메모리) 를 쓰지 않고는 절대 만들 수 없다"**는 것을 증명했습니다.
• 비유: 요리사 (알고리즘) 가 요리를 하려는데, 접시나 그릇 (보조 도구) 을 전혀 쓰지 않고 재료를 섞으려 한다면, 아무리 뛰어난 요리사라도 완벽한 요리를 할 수 없다는 것입니다. 양자 세계에서는 이 '보조 도구'가 없으면 암호화 키를 만드는 것이 불가능하다는 뜻입니다.

비유 3: "짧은 줄을 긴 줄로 늘리기" (길이 확장 불가)

• 상황: 짧은 양자 난수 (Short PRSG) 를 가지고 긴 양자 난수 (Long PRSG) 를 만들려고 합니다.
• 문제: 고전 세계에서는 짧은 줄을 늘려 긴 줄로 만들 수 있지만, 양자 세계에서는 특정 방식으로는 절대 늘릴 수 없다는 것을 보였습니다.
• 비유: "짧은 실로 긴 실을 만들려고 할 때, 실을 늘리는 과정에서 실의 질감 (순도) 이 변해버려서 더 이상 '진짜'처럼 보이지 않게 된다"는 것입니다.

3. 연구자들이 어떻게 증명했나요? (기하학적 장벽)

이 논문의 가장 혁신적인 부분은 증명 방법입니다. 연구자들은 **'기하학적 장벽 정리 (Barrier Theorem)'**라는 새로운 수학적 도구를 개발했습니다.

• 비유: imagine(상상해 보세요) 양자 상태들이 거대한 구 (구면) 위에 흩어져 있다고 칩시다.
• 연구자들은 "어떤 두 그룹 (진짜 난수와 가짜 난수) 이 서로 너무 멀리 떨어져 있다면, 그 사이에는 **반드시 빈 공간 (장벽)**이 존재한다"는 것을 수학적으로 증명했습니다.
• 이 '빈 공간' 때문에, 알고리즘이 한쪽에서 다른 쪽으로 넘어가려 할 때 필연적으로 실수 (오류) 를 하거나, 예측 가능해진다는 것을 보인 것입니다.

4. 결론: 양자 암호학의 새로운 지평

이 연구는 우리에게 중요한 메시지를 줍니다.

1. 양자는 고전과 다릅니다: 고전 암호학의 규칙 (예: "작은 것에서 큰 것을 만들 수 있다") 을 양자 세계에 그대로 적용하면 안 됩니다.
2. 불완전함의 인정: 양자 컴퓨터로 완벽한 암호를 만들려면, 우리가 생각했던 것보다 더 많은 자원 (보조 메모리 등) 이 필요하거나, 어쩔 수 없는 오류를 감수해야 할 수 있습니다.
3. 새로운 암호의 필요성: 양자 시대에 안전할 새로운 암호 체계는 고전적인 방식과는 완전히 다른 접근이 필요하다는 것을 시사합니다.

한 줄 요약:

"양자 세계에서는 '작은 씨앗'으로 '완벽한 열매'를 맺는 것이 고전 세계처럼 쉽지 않으며, 이를 위해선 우리가 아직 잘 모르는 새로운 규칙 (보조 도구 등) 이 필요하다는 것을 수학적으로 증명했습니다."

이 논문은 양자 암호학이 아직 초기 단계이며, 우리가 고전적인 사고방식을 버리고 양자만의 고유한 법칙을 이해해야 함을 일깨워주는 중요한 연구입니다.

기술 요약

1. 연구 배경 및 문제 제기

• 양자 난수성의 다양성: 양자 암호학에서는 의사난수 상태 생성기 (PRSG), 의사난수 함수와 같은 상태 생성기 (PRFSG), 의사난수 유니타리 (PRU) 등 다양한 난수성 개념이 존재합니다.
• 고전적 대조: 고전 암호학에서는 PRG(의사난수 생성기) 와 PRF(의사난수 함수) 가 서로 변환 가능하며, 하나의 기본 가정 (예: 일방향 함수) 으로 모든 것을 설명할 수 있습니다.
• 핵심 질문: 양자 세계에서도 이러한 개념들이 서로 변환 가능한가? 즉, 짧은 출력 길이의 PRSG 로부터 긴 출력 길이의 PRSG 나 QPRG(양자 의사난수 생성기) 를 구성할 수 있는가? PRFSG 로부터 PRU 를 구성할 수 있는가?
• 기존 연구의 한계: Kretschmer [Kre21] 등은 긴 출력 길이의 PRSG 가 고전 암호학보다 약할 수 있음을 보였으나, 짧은 출력 길이의 PRSG 와 QPRG 사이의 관계, 혹은 보조 레지스터 (ancilla) 없이 PRU 를 구성하는 것의 불가능성 등에 대해서는 명확한 답이 없었습니다.

2. 주요 방법론 (Methodology)

이 논문은 오라클 분리 (Oracle Separation) 기법을 사용하여, 특정 오라클 환경에서는 한 원소는 존재하지만 다른 원소는 존재하지 않음을 증명합니다.

• 공통 하르 함수와 같은 상태 오라클 (CHFS Oracle):
  • 입력 $x$에 대해 길이 $\ell(|x|)$의 하르 무작위 상태 $|\phi_x\rangle$를 출력하는 오라클을 정의합니다.
  • 이는 등거리 (Isometry) 버전과 유니타리 (Unitary/Reflection) 버전으로 나뉘며, PRFSG 를 구성하는 데는 매우 자연스럽습니다.
• QPSPACE 오라클:
  • 다항 공간 (Polynomial Space) 으로 계산 가능한 유니타리 회로를 구현하는 오라클을 추가하여, 공격자가 복잡한 계산 (예: 상태의 순도 테스트, 토모그래피) 을 수행할 수 있게 합니다. 이는 공격 능력을 강화하여 더 강력한 분리 결과를 얻기 위함입니다.
• 새로운 기하학적 장벽 정리 (Barrier Theorem):
  • 기존 오라클 분리에서 주로 사용되던 **집중 부등식 (Concentration Inequality)**은 출력 길이가 로그 (log) 수준일 때 (즉, 차원이 작을 때) 적용하기 어렵습니다.
  • 저자들은 **하르 측도 (Haar measure)**의 기하학적 성질을 이용한 새로운 장벽 정리를 증명했습니다. 이 정리는 두 개의 큰 집합 (예: 알고리즘이 0 을 출력하는 오라클 집합과 1 을 출력하는 집합) 이 서로 멀리 떨어져 있을 때, 그 사이의 '중간 영역'도 충분히 크다는 것을 보장합니다. 이는 알고리즘이 결정론적 (pseudodeterministic) 이면서 동시에 보안성을 유지하는 것을 기하학적으로 불가능하게 만듭니다.

3. 주요 결과 및 기여 (Key Results & Contributions)

논문의 주요 결과는 세 가지 분리 (Separation) 로 요약됩니다.

3.1. 짧은 PRFSG 로부터 QPRG 의 불가능성 (Theorem 1.1)

• 결과: 로그 길이 ($O(\log \lambda)$) 출력 PRFSG 는 존재하지만, 오류가 무시할 수 있을 정도로 작은 (negligible error) QPRG 는 존재하지 않는 오라클 세계가 존재합니다.
• 의미:
  • 기존 연구 [ALY24] 에서 짧은 PRSG 로부터 QPRG 를 구성할 때 역다항식 (inverse-polynomial) 오류가 필연적으로 발생한다는 것을 증명했습니다.
  • 이는 고전 암호학의 '미니크립트 (Minicrypt)'가 양자 세계에서도 완전히 복원되지 않음을 시사합니다. 즉, QPRG 가 없어도 디지털 서명이나 암호화가 가능할 수 있음을 보여줍니다.
  • Pessiland의 양자 버전 존재 증명: QCMA $\cap$ coQCMA 에 속하는 평균적으로 어려운 언어는 존재하지만, QPRG 나 QOWF(양자 일방향 함수) 는 존재하지 않는 세계가 가능합니다.

3.2. 보조 레지스터 없는 PRU 의 불가능성 (Theorem 1.4)

• 결과: 적응적으로 안전한 PRFSG 는 존재하지만, 보조 레지스터 (ancilla) 를 사용하지 않는 비적응적 PRU 는 존재하지 않습니다.
• 방법론:
  • 공격자는 PRU 생성 알고리즘이 보조 레지스터 없이 작동할 때, 하르 무작위 상태에 대한 반사 연산 (reflection) 이 상태를 거의 변경하지 않는다는 점을 이용합니다.
  • **토모그래피 (Tomography)**를 통해 작은 입력 크기의 오라클을 학습하고, 이를 시뮬레이션하여 실제 PRU 와 하르 유니타리를 구별하는 공격을 수행합니다.
  • 이는 고전 암호학에서 PRF 로부터 PRP(의사난수 치환) 를 구성할 수 있다는 사실과 대조적으로, 양자 세계에서는 보조 메모리 없이는 불가능함을 보여줍니다.

3.3. PRSG 출력 길이 확장 (Length Extension) 의 한계 (Theorem 1.5)

• 결과: 짧은 PRFSG 로부터 긴 PRSG 를 구성하는 자연스러운 방법 (비적응적 쿼리 후 유니타리 적용) 은 불가능합니다.
• 기술적 통찰:
  • 순도 테스트 (Purity Test): 양자 알고리즘의 출력 상태가 하르 무작위 상태 (순수 상태) 와 구별 불가능하려면, 알고리즘 내부의 중간 측정 (intermediate measurements) 이 거의 결정론적이어야 함을 보였습니다.
  • 이를 통해 적응적 쿼리를 가진 알고리즘도 비적응적 쿼리로 근사화될 수 있음을 보였고, 결과적으로 PRSG 의 출력 길이를 늘리는 일반적인 방법이 불가능함을 증명했습니다.

4. 기술적 세부 사항 및 증명 전략

1. 장벽 정리의 적용 (QPRG 분리):

   • QPRG 가 결정론적이어야 한다는 가정 하에, 오라클 공간에서 알고리즘이 0 을 출력하는 영역 ($S_0$) 과 1 을 출력하는 영역 ($S_1$) 이 모두 크다고 가정합니다.
   • 장벽 정리에 따라 이 두 영역 사이의 거리 ($d(S_0, S_1)$) 가 크다면, 두 영역을 제외한 중간 영역 ($X \setminus (S_0 \cup S_1)$) 도 충분히 커야 합니다.
   • 하지만 QPRG 는 결정론적이어야 하므로 중간 영역이 작아야 하므로 모순이 발생합니다. 이를 통해 QPRG 가 존재하지 않음을 증명합니다.

2. 순도 테스트와 측정의 결정론성 (PRSG 확장 분리):

   • 알고리즘의 출력 상태가 순수 (pure) 하려면, 알고리즘 내부의 모든 중간 측정 결과가 거의 확실히 (high probability) 결정되어야 합니다.
   • 이 성질을 이용해 공격자가 측정 결과를 미리 학습하고, 오라클 쿼리를 고정된 순서로 변경할 수 있음을 보입니다. 이는 PRSG 길이 확장을 불가능하게 만드는 핵심 요소입니다.

3. QPSPACE 오라클의 활용:

   • 공격자가 복잡한 상태 테스트 (예: Swap test, Product test) 를 수행하고, 그 결과를 기반으로 오라클을 구별할 수 있도록 QPSPACE 오라클을 도입하여 공격 능력을 극대화했습니다.

5. 의의 및 결론

• 양자 난수성의 비동일성: 양자 난수성 개념들은 고전적인 경우와 달리 단일한 가정으로 환원되지 않으며, 서로 다른 위계 구조를 가질 수 있음을 증명했습니다.
• 기술적 장벽: 보조 레지스터 (ancilla) 의 유무, 측정의 적응성, 출력 길이의 확장 등 양자 알고리즘의 구조적 특성이 암호학적 원소의 구성 가능성에 결정적인 영향을 미칩니다.
• 미래 연구 방향:
  • PRSG 의 길이 확장이 완전히 불가능한지, 아니면 다른 방법 (예: 양자 키 샘플링, 부분 추적 등) 으로 가능한지에 대한 논의가 필요합니다.
  • 보조 레지스터를 사용하는 PRU 와 PRFSG 의 관계에 대한 완전한 분리 (Full Separation) 는 여전히 열린 문제로 남았습니다.

이 논문은 양자 암호학의 기초 이론을 정립하는 데 중요한 이정표가 되었으며, 특히 오류가 있는 QPRG 의 필연성과 보조 메모리 없는 PRU 의 불가능성을 통해 양자 암호 시스템 설계 시 고려해야 할 새로운 제약 조건을 제시했습니다.