2025-11-14T17:16:11.719199

Quantum One-Time Protection of any Randomized Algorithm

Gunn, Movassagh
The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we demonstrate such a solution with quantum one-time tokens. A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models. We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a black box model. Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum resources serve only to increase the security of the protocol. Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum computing in either the NISQ or early fault tolerant regime.
academic

임의의 무작위화 알고리즘의 양자 일회용 보호

기본 정보

  • 논문 ID: 2411.03305
  • 제목: Quantum One-Time Protection of any Randomized Algorithm
  • 저자: Sam Gunn, Ramis Movassagh (Google Quantum AI)
  • 분류: quant-ph cs.CR
  • 발표 시간: 2025년 1월 3일 (arXiv v2)
  • 논문 링크: https://arxiv.org/abs/2411.03305v2

초록

기계학습 모델의 급속한 발전과 가치 있는 훈련 데이터에 대한 의존성은 로컬에서 프로그램을 실행하는 편의성과 프로그램 세부 사항을 사용자에게 노출할 위험 사이의 근본적인 모순을 재조명했습니다. 동시에 양자 상태의 기본 성질은 극소량의 양자 자원만으로 구현 가능하며 계산 실행 시간을 초과하는 이점을 제공하는 데이터 및 프로그램 보안을 위한 새로운 솔루션을 제공합니다. 본 연구는 양자 일회용 토큰을 통해 이러한 솔루션을 제시합니다.

양자 일회용 토큰은 특정 프로그램이 정확히 한 번만 평가되도록 허용하는 양자 상태입니다. 일회용 보안은 토큰이 프로그램을 여러 번 평가하는 데 사용될 수 없음을 보장합니다. 저자들은 임의의 무작위화 고전 프로그램(생성형 AI 모델 포함)에 대한 양자 일회용 토큰을 구성하는 방안을 제시하고, 고전 알고리즘의 출력이 충분히 높은 최소 엔트로피를 가진다는 전제 하에 블랙박스 모델에서 흥미로운 일회용 보안 정의를 만족함을 증명합니다.

연구 배경 및 동기

문제 정의

소프트웨어 상용화는 핵심 딜레마에 직면합니다: 소유권을 포기하지 않으면서 소프트웨어를 배포하는 방법은 무엇인가? 전통적인 솔루션은 고유한 가용성과 배타성 간의 트레이드오프를 가집니다:

  1. 프로그램 난독화 방안: 난독화된 버전의 소프트웨어를 배포하지만 불법 복제 위험이 있으며 사용자는 무제한으로 실행 가능
  2. 서버 쿼리 방안: 소프트웨어를 서버에 유지하여 사용자 쿼리에 응답하지만 가용성이 감소하고 지속적인 통신 필요

문제의 중요성

생성형 AI 시대에 이 문제는 더욱 심각해집니다:

  • 소프트웨어가 극도로 가치 있을 수 있음
  • 개인 정보 유출 가능성
  • 쿼리당 지불 모델의 증가

기존 방법의 한계

고전 정보는 항상 복제 가능하므로, 소프트웨어가 배포되면 사용자는 임의로 여러 번 쿼리하거나 복제할 수 있습니다. 이러한 한계로 인해 전통적인 방안은 높은 가용성과 강한 배타성을 동시에 달성할 수 없습니다.

양자 솔루션의 이점

양자 정보의 복제 불가능성은 기존 솔루션을 개선할 가능성을 제공합니다:

  • 양자 복제 보호: 방안(1) 개선, 프로그램 복제 방지하되 무제한 실행 허용
  • 양자 일회용 프로그램: 방안(2) 개선, 쿼리당 지불 모델에서 온라인 통신 필요성 제거

핵심 기여

  1. 최초의 범용 양자 토큰화 프로그램 방안: 양자 정보를 사용하여 임의의 무작위화 알고리즘을 보호하는 최초의 범용 방안 제시, 특정 암호학적 기능에 국한되지 않음
  2. 프로그램 복잡도와 무관한 양자 자원 요구: 양자 토큰의 크기와 복잡도는 보호되는 프로그램과 완전히 독립적
  3. 이론적 보안성 증명: 블랙박스 모델에서 일회용 보안 정의를 만족함을 증명
  4. 실용성 고려: 방안이 충분히 간결하여 NISQ 또는 초기 내결함 양자 컴퓨팅 시대에 구현 가능할 것으로 예상

방법 상세 설명

작업 정의

임의의 무작위화 알고리즘 f: X × R → Y를 보호하기 위한 양자 일회용 토큰 구성:

  • 토큰은 프로그램이 정확히 한 번만 평가되도록 허용
  • 일회용 보안 보장 제공
  • 프로그램이 양자 컴퓨터에서 일관되게 구현될 필요 없음

핵심 구성 (Construction 2)

암호학적 원시 요소

방안은 세 가지 암호학적 원시 요소에 의존합니다:

  1. (AuthKeyGen, AuthTokenGen, Sign, Verify): 양자 일회용 인증 방안
  2. Obf: 고전 프로그램 난독화기
  3. H: 해시 함수 (무작위 예언기로 모델링)

토큰 구조

프로그램 토큰은 두 부분으로 구성됩니다:

  • |ψ⟩: f에 독립적인 복제 불가능 양자 상태
  • Obf(P): f에 의존하는 난독화 고전 회로 P

알고리즘 흐름

KeyGen(1^λ, f):

  1. sk ← AuthKeyGen(1^λ) 샘플링
  2. 고전 회로 P: X × {0,1}^m → Y ∪ {⊥} 정의
    • Verify(sk, (x,z)) 계산, 거부 시 ⊥ 출력
    • 그 외의 경우 f(x; H(x,z)) 출력
  3. 난독화 P̂ = Obf(P) 계산
  4. (sk, P̂) 출력

TokenGen(sk):

  1. 일회용 인증 토큰 |tk⟩ ← AuthTokenGen(sk) 계산
  2. |tk⟩ 출력

TokenEval(x, |tk⟩, P̂):

  1. z ← Sign(x, |tk⟩) 계산
  2. P̂(x,z) 계산 및 출력

양자 일회용 인증 방안

정의 (Definition 1)

양자 일회용 인증 방안은 다음을 만족해야 합니다:

  • 정확성: 합법적 서명이 검증을 통과
  • 일회용 위조 불가능성: 모든 다항식 시간 대적이 두 개의 서로 다른 유효한 서명 쌍을 생성할 수 없음

구체적 구성 (Construction 1)

숨겨진 부분공간 상태 기반 단일 비트 인증:

AuthKeyGen(1^λ): 무작위 부분공간 A ⊆ F₂^λ 샘플링, 차원 λ/2

AuthTokenGen(A): |A⟩ = 2^(-λ/4) ∑_{a∈A} |a⟩ 출력

Sign(x, |A⟩):

  • x = 0인 경우: 표준 기저에서 측정 및 결과 출력
  • x = 1인 경우: Hadamard 기저에서 측정 및 결과 출력

Verify(A, (x,z)): z가 해당 부분공간에 있는지 검증

기술적 혁신점

  1. 프로그램 무관 양자 자원: 양자 상태 |ψ⟩는 보호되는 프로그램과 무관하여 복잡한 프로그램을 소형 양자 장치로 보호 가능
  2. 무작위성 바인딩 메커니즘: H(x,z)를 통해 무작위성 결정, 입력, 인증 및 출력을 효과적으로 "혼합"
  3. 붕괴 해시 함수 성질: 측정 출력이 입력 및 인증 레이블을 붕괴시키는 양자 특성 활용

이론적 분석

보안성 정의

블랙박스 일회용 프로그램 게임 G^BB-OTP

  1. 대적이 |ψ⟩와 P̂에 대한 양자 예언기 접근 획득
  2. 대적이 양자 쿼리 제출, 도전자가 P̂ 계산 및 결과 y 측정
  3. y = ⊥이면 게임 중단, 대적 패배
  4. 대적이 두 번째 쿼리 제출, 도전자가 y' 측정
  5. y' ∉ {y, ⊥}이면 대적 승리

주요 정리

정리 2: 모든 x ∈ X에 대해 f(x;r)이 무작위 r에 대해 최소 poly(λ)의 최소 엔트로피를 가지고, 양자 일회용 인증 방안이 안전하면, Construction 2는 f에 대해 블랙박스 일회용 안전합니다.

증명의 핵심: 붕괴 해시 함수

보조정리 1: f: {0,1}^m × {0,1}^n → Y이고, 모든 x에 대해 f(x;r)이 무작위 r에 대해 최소 τ의 최소 엔트로피를 가지면, H가 무작위 예언기일 때 함수 g^H: x ↦ f(x;H(x))는 O(q³·2^(-τ))의 이점으로 붕괴됩니다.

증명 사고

압축 예언기 기술 사용:

  1. Invert_f와 CPhsO가 거의 교환 가능함을 증명
  2. 최소 엔트로피 조건을 사용하여 충돌 확률 제한
  3. 측정 출력을 통해 입력 붕괴 구현

실험 및 응용

양자 자원 요구

  • CLLZ21의 일회용 서명 방안 사용 시, 사용자는 다음만 필요:
    • 상수 크기 양자 상태 저장
    • 표준 기저 및 Hadamard 기저에서 측정 수행

실용성 고려

  1. 근기간 실현 가능성: 양자 능력 요구가 프로그램 복잡도와 무관
  2. 확장 가능 보안성: 추가 양자 자원은 보안성 향상에만 사용
  3. 고전 통신 대체: 원격 상태 제조 프로토콜을 통해 양자 통신을 고전 통신으로 대체 가능

적용 시나리오

  • 생성형 AI 모델 보호
  • 쿼리당 지불 소프트웨어 서비스
  • 오프라인 실행이 필요한 민감한 프로그램

관련 연구

역사적 발전

  • GKR08: 일회용 프로그램 초기 연구 (양자 컴퓨팅 없음)
  • BGS13: 양자 일회용 프로그램 개념 제시, 결정론적 프로그램의 불가능성 증명
  • BS23: 표준 모델에서 서명 함수 보호
  • GLR+24: 병렬 독립 연구, 더 강한 보안 정의 제공

본 논문의 기여 비교

  • 임의의 무작위화 알고리즘을 보호하는 최초의 범용 방안
  • 간결한 자체 포함 보안성 증명
  • 실용성 지향적 설계 고려

결론 및 논의

주요 결론

  1. 양자 일회용 토큰은 임의의 무작위화 고전 프로그램을 보호 가능
  2. 보안성은 프로그램 출력의 높은 최소 엔트로피에 의존
  3. 양자 자원 요구는 프로그램 복잡도와 무관
  4. 방안은 NISQ 시대에 구현 가능성 보유

한계

  1. 높은 엔트로피 요구: 프로그램 출력이 충분히 높은 최소 엔트로피를 가져야 함
  2. 블랙박스 모델: 보안성 증명이 이상화된 블랙박스 모델에서 수행됨
  3. 결정론적 프로그램 제한: BGS13의 불가능성 결과로 인해 결정론적 프로그램에 부적용
  4. 복잡한 고전 통신 프로토콜: 이론상 양자 통신을 고전 통신으로 대체 가능하지만 프로토콜이 극도로 복잡함

향후 방향

  1. 표준 모델에서의 보안성 분석
  2. 프로그램 출력 엔트로피 요구 감소
  3. 실제 양자 장치에서의 구현 및 테스트
  4. GLR+24 연구와의 관계 분석

심층 평가

장점

  1. 이론적 혁신: 임의의 무작위화 알고리즘을 보호하는 범용 양자 방안 최초 제시
  2. 실용적 설계: 양자 자원 요구와 프로그램 복잡도 분리로 실용성 증대
  3. 엄밀한 증명: 붕괴 해시 함수 기반의 간결한 보안성 증명 제공
  4. 응용 전망: 현재 주목받는 생성형 AI 보호 수요에 직접 적용 가능

부족한 점

  1. 이상화된 가정: 블랙박스 모델 및 무작위 예언기 모델에 의존
  2. 엔트로피 조건 제한: 높은 최소 엔트로피 요구가 실제 응용 범위를 제한할 수 있음
  3. 구현 복잡성: 이론상 우아하지만 실제 구현은 여전히 공학적 과제 직면
  4. 보안 정의: 저자들이 이것이 일회용 보안의 최종 정의가 아님을 인정

영향력

  1. 학술적 가치: 양자 암호학의 프로그램 보호 문제에 새로운 이론적 틀 제공
  2. 실용적 잠재력: 가치 있는 AI 모델 보호를 위한 가능한 양자 솔루션 제시
  3. 기술 진전: 복제 불가능 암호학 발전 추진
  4. 영감 제공: 양자 컴퓨팅의 근기간 실용 응용을 위한 새로운 사고 제시

적용 시나리오

  • 지식재산권 보호가 필요한 AI 서비스 제공자
  • 사용량 기반 소프트웨어 라이선스 모델
  • 보안 요구도가 극도로 높은 민감한 알고리즘 보호
  • 양자 우월성 시연의 후보 응용

참고문헌

본 논문은 양자 암호학, 복제 불가능 암호학 및 양자 계산 복잡성 이론의 중요한 연구를 인용하며, 특히:

  • Aar09 Aaronson의 양자 복제 보호에 관한 개척적 연구
  • BS23 Ben-David와 Sattath의 양자 디지털 서명 연구
  • CLLZ21 숨겨진 코셋 및 복제 불가능 암호학 구성
  • Zha19 Zhandry의 압축 예언기 기술 연구

본 논문은 이론적 양자 암호학 분야에서 중요한 기여를 하며, 소프트웨어 배포에서 가용성과 보안성 간의 모순을 균형 있게 해결하기 위한 우아한 솔루션을 제공합니다. 실용화에는 여전히 과제가 있지만, 양자 컴퓨팅의 암호학 응용에서 근기간 구현을 위한 유망한 방향을 제시합니다.