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

要旨

機械学習モデルの急速な発展と価値のある訓練データへの依存により、ローカルで実行されるプログラムの利便性と、ユーザーへのプログラム詳細の露出リスクとの間の根本的な矛盾が再び注目されている。同時に、量子状態の基本的性質は、最小限の量子リソースで実装でき、計算実行時間を超える利点を提供する、データとプログラムセキュリティのための新しいソリューションを提供する。本研究は、量子ワンタイムトークンを通じてそのようなソリューションを実証する。

量子ワンタイムトークンは、特定のプログラムが正確に1回評価されることを許可する量子状態である。ワンタイム安全性は、トークンが複数回のプログラム評価に使用できないことを保証する。著者は、任意のランダム化古典プログラム（生成型AIモデルを含む）に対する量子ワンタイムトークンを構築するスキームを提案し、古典アルゴリズムの出力が十分に高い最小エントロピーを有することを前提として、ブラックボックスモデルにおいて興味深いワンタイム安全性定義を満たすことを証明している。

研究背景と動機

問題定義

ソフトウェアの商業化は中核的なジレンマに直面している：所有権を放棄することなくソフトウェアをどのように配布するか？従来のソリューションには固有の利用可能性と排他性のトレードオフが存在する：

  1. プログラム難読化スキーム：難読化されたバージョンのソフトウェアを配布するが、海賊版のリスクがあり、ユーザーは無制限に実行できる
  2. サーバークエリスキーム：ソフトウェアをサーバー上に保持してユーザークエリに応答するが、利用可能性が低下し、継続的な通信が必要である

問題の重要性

生成型AI時代において、この問題はより深刻になっている。理由は以下の通りである：

  • ソフトウェアは極めて価値がある可能性がある
  • 個人情報を漏らす可能性がある
  • クエリごとの支払いモデルが益々一般的になっている

既存方法の限界

古典情報は常にコピー可能であり、ソフトウェアが配布されると、ユーザーは任意の回数クエリまたはコピーできる。この限界により、従来のスキームは高い利用可能性と強い排他性を同時に実現することができない。

量子ソリューションの利点

量子情報の複製不可能性は、既存のソリューションを改善する可能性を提供する：

  • 量子複製保護：スキーム(1)を改善し、プログラムのコピーを防ぐが無制限の実行を許可する
  • 量子ワンタイムプログラム：スキーム(2)を改善し、クエリごとの支払いモデルにおけるオンライン通信の必要性を排除する

中核的貢献

  1. 初の汎用量子トークン化プログラムスキーム：特定の暗号学的機能に限定されない、任意のランダム化アルゴリズムを保護するための量子情報を使用した初の汎用スキームを提案
  2. プログラム複雑性に独立した量子リソース要件：量子トークンのサイズと複雑性は、保護されるプログラムから完全に独立している
  3. 理論的安全性証明：ブラックボックスモデルにおいてスキームがワンタイム安全性定義を満たすことを証明
  4. 実用性の考慮：スキームは十分に簡潔であり、NISQ時代または初期の耐障害性量子計算時代での実装が期待される

方法の詳細

タスク定義

任意のランダム化アルゴリズムf：X × R → Yを保護するための量子ワンタイムトークンを構築する。以下を満たす必要がある：

  • トークンはプログラムが正確に1回評価されることを許可する
  • ワンタイム安全性保証を提供する
  • プログラムが量子コンピュータ上で一貫して実装される必要がない

中核的構成 (Construction 2)

暗号学的プリミティブ

スキームは3つの暗号学的プリミティブに依存する：

  1. (AuthKeyGen, AuthTokenGen, Sign, Verify)：量子ワンタイム認証スキーム
  2. Obf：古典プログラム難読化器
  3. H：ハッシュ関数（ランダムオラクルとしてモデル化）

トークン構造

プログラムトークンは2つの部分で構成される：

  • |ψ⟩：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)

量子ワンタイム認証スキームは以下を満たす必要がある：

  • 正確性：正当な署名は検証を通過する
  • ワンタイム偽造不可能性：多項式時間対手は2つの異なる有効な署名ペアを生成できない

具体的構成 (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. 対手は2番目のクエリを提出し、チャレンジャーは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による圧縮オラクル技術に関する研究

本論文は理論量子密暗号学分野における重要な貢献を行い、ソフトウェア配布における利用可能性とセキュリティの矛盾を平衡させるための優雅なソリューションを提供している。実用化にはまだ課題が残っているが、量子計算の密暗号学応用における近期実現のための有望な方向性を提供している。