⚛️ quantum physics

Certified-Everlasting Quantum NIZK Proofs

この論文は、学習誤差（LWE）仮定に基づく暗号学的仮定を用いて、証明の破棄を証明可能に検証できる「認証永続的ゼロ知識（CE-ZK）」を満たす非対話ゼロ知識証明（NIZK）を、共通参照文字列（CRS）モデルおよび共有 EPR ペアモデルの両方で構築する手法を提案し、その際に直面する既存の相互作用型ゼロ知識証明からの一般化の障壁を克服することを示しています。

原著者： Nikhil Pappu

公開日 2026-02-13

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Nikhil Pappu

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🕵️‍♂️ 物語の舞台：「秘密の Sudoku パズル」

まず、この技術が解決しようとしている問題を、日常の例えで見てみましょう。

あなたが**「Sudoku（数独）の解」を知っているとします。あなたは友人（検証者）に「このパズルは解ける！」と証明したいけれど、「答え（解き方）は絶対に教えたくない」**とします。

従来の証明（NIZK）： あなたは「答えを知っている」ことを証明できますが、一度証明すると、その証拠（デジタルデータ）は永遠に残ります。もし将来、あなたの友人が超強力なコンピューターを手に入れたら、その証拠からあなたの「答え」を逆算して盗んでしまうかもしれません。
この論文の提案（CE-NIZK）： あなたは証明を提示し、友人はそれを確認します。そして、**「もういいよ、その証拠は消していいよ」**と合図が出たら、友人は証拠を物理的に消去します。
- 重要なのは： 消去したことを**「第三者が確認できる」**こと。
- 結果： 証拠が消えれば、たとえ友人が未来に超強力なコンピューターを手に入れても、あなたの「答え」を二度と復元できません。まるで、証拠が「消えた瞬間に魔法で消滅した」かのように。

これが**「認証付き永続的ゼロ知識（Certified-Everlasting Zero-Knowledge）」**です。

🚧 壁と突破口：なぜこれが難しかったのか？

研究者たちは、この「消去可能な証明」を作るために、いくつかの壁にぶつかりました。

1. 「二つに分裂する」罠

これまでの試みでは、「証明を二つの部分に分けて、一方は消去証明に使って、もう一方は検証に使おう」というアイデアがありました。
しかし、これには致命的な欠点がありました。

たとえ： 犯人が「消去した」と嘘をつき、実は「もう一方の証拠」を隠し持っていたらどうなる？
もし証明が「消去証明用」と「検証用」に簡単に分けられてしまうと、悪意ある証明者は**「検証に使う方だけ渡して、消去証明の方だけ残す」**という手口が使えてしまいます。これでは「証拠を消した」と言っても、実は証拠が手元に残っていることになり、セキュリティが崩壊します。

この論文は、**「CRS（共通参照文字列）モデル」**と呼ばれる一般的な設定では、この「分裂攻撃」を防ぐために、単純な方法を試しても失敗することを突き止めました。

2. 突破口：「量子の重ね合わせ」と「二重の鍵」

そこで、著者は**「量子の不思議な性質」**を利用した新しい方法を開発しました。

アイデア： 証明を「重ね合わせ（スーパーポジション）」の状態で作ります。
- 例えるなら、「証明という封筒」の中に、2 つの異なる鍵（パッド）を同時に混ぜて入れている状態です。
- 検証者は、この封筒を受け取りますが、中身を見る前に「証拠を消去する」必要があります。
- 量子の性質上、「証拠を消去する（観測する）」行為そのものが、中身（秘密）を無効化してしまいます。
- さらに、この技術は「証明が正しいか」をチェックする際にも、「答え（秘密）」を使わずに済むように設計されています。

これにより、**「証拠を消去したなら、もう秘密は復元できない」**という保証が、数学的に厳密に成立するようになりました。

🌌 2 つの異なる世界：2 つの解決策

この論文は、この問題を解決するために2 つの異なるアプローチを提案しています。

① 一般的な世界（CRS モデル）：「複雑な量子パズル」

特徴： 特別な準備（共通のランダムな文字列）があれば、誰でも使える。
仕組み： 非常に高度な量子技術（BB84 状態や量子暗号）を駆使して、証明を「重ね合わせ」の状態で作ります。
メリット： 標準的な設定で実現可能。
デメリット： 証明の生成や検証に、少し複雑な量子計算が必要。

② 特別な世界（共有 EPR モデル）：「双子のテレパシー」

特徴： 証明者と検証者が、事前に**「EPR 対（量子もつれ状態）」**という、まるで双子のようにリンクした粒子を共有している場合。
仕組み：
- 二人は事前に「リンクしたコイン」を持っています。
- 証明者は「コインの表裏（量子状態）」を測定して情報を隠し、検証者は自分のコインを測定して確認します。
- 検証者が「証拠を消去」するときは、自分のコインを別の角度から測定（ハダマード基底測定）するだけで OK。
メリット： 驚くほどシンプル！ 複雑な量子計算は不要で、ただ「コインの向きを見る（測定する）」だけで済みます。
デメリット： 事前に「リンクした粒子」を共有しておく必要がある（これは量子インターネットのような未来のインフラを想定しています）。

💡 なぜこれが重要なのか？

この技術は、**「未来のセキュリティ」**を守るための鍵となります。

現在の暗号： 「今のコンピューターでは解けない」から安全です。でも、10 年後に量子コンピューターが完成したら、今のデータがすべてバレてしまう可能性があります。
この技術： 「証拠を消去すれば、どんなに強力なコンピューターが来ても、永遠に秘密は守られる」と保証します。

例え話：
あなたが銀行から「あなたの預金残高は 1 億円です」という証明書を受け取りました。

普通の証明書： 将来、ハッカーが超強力なコンピューターを手に入れたら、その証明書を解析して「あなたの秘密のパスワード」を盗むかもしれません。
この証明書の魔法： 「はい、証明書を確認しました。さあ、破り捨ててください（消去してください）。」
- あなたが証明書を確認し、「消去した」という証拠を銀行に返すと、その瞬間、証明書は物理的に意味を失います。
- 100 年後にハッカーが現れても、「消去された証拠」からは何も読み取れません。

🏁 まとめ

この論文は、**「証明を消去したことを、第三者が確認できる」**という、一見矛盾する（消去したら検証できないはずなのに）量子技術を実現しました。

壁を突破した： 「証明を分裂させて悪用する」手口を防ぐ新しい量子プロトコルを発見。
2 つの道を開いた：
- 複雑だが一般的な**「CRS モデル」**での実装。
- シンプルで効率的な**「共有 EPR モデル」**での実装（量子もつれを利用）。
未来への約束： 「一度消えれば、永遠に復元できない」という、**「認証付き永続的セキュリティ」**を、NP 問題（多くの現実的な問題）に対して実現可能にしました。

これは、量子コンピューター時代における「プライバシーの究極の守り方」の一つとして、非常に重要な一歩です。

論文「Certified-Everlasting Quantum NIZK Proofs」の技術的サマリー

この論文は、Nikhil Pappu によって書かれ、Certified-Everlasting（認証付き永続的）な非対話型ゼロ知識証明（CE-NIZK） の構成と不可能性の研究に焦点を当てています。従来の NIZK は、計算量的仮定が破られた場合にゼロ知識性が失われるという課題を抱えていますが、本論文は量子リソースを活用することで、検証者が証明を「削除」し、その削除が証明者によって検証可能（認証）である場合、将来の無限計算能力を持つ敵に対してもゼロ知識性が保証される（永続的ゼロ知識）という新しいセキュリティ概念を確立します。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題設定と背景

1.1 背景

NIZK の限界: 非対話型ゼロ知識証明（NIZK）は、証明者が検証者に単一のメッセージを送るだけで命題の真偽を証明できる強力な暗号プリミティブですが、通常は計算量的ゼロ知識（Computational ZK）しか保証されません。つまり、検証者が将来的に計算能力が無限大になった場合、証明から秘密情報を抽出できてしまう可能性があります。
統計的ゼロ知識の困難さ: 統計的ゼロ知識（Statistical ZK）と統計的音響性（Statistical Soundness）を同時に満たす NIZK は、NP の大部分の言語に対して構築不可能であることが知られています。
量子の妥協点: 近年の研究（HMNY22, BK23 など）では、対話型プロトコルにおいて、検証者が証明を「削除」し、その削除が「認証」されることで、無限計算能力を持つ敵に対してもゼロ知識性が保証される「認証付き永続的ゼロ知識（CE-ZK）」が実現可能であることが示されました。
未解決課題: しかし、この CE-ZK の概念を非対話型（NIZK） に拡張すること、特に共通参照文字列（CRS）モデルや共有 EPR モデルにおいて、統計的音響性と永続的ゼロ知識を両立させる構成は、これまで実現されていませんでした。

1.2 核心的な課題

削除耐性プロトコルの不可能性: 単純に既存の対話型 CE-ZK プロトコルを非対話型に一般化（例：Fiat-Shamir 変換）すると、証明者が証明状態を「検証に使える部分」と「削除認証に使える部分」に分割（Split）する攻撃が可能になり、統計的音響性と統計的ゼロ知識を同時に満たす NIZK が存在することになってしまい、これは不可能であるため、そのようなアプローチは失敗します。
量子リソースの活用: この不可能性を回避しつつ、効率的な構成を行うための新しいアプローチが必要です。

2. 主要な貢献と結果

著者は以下の 3 つの主要な貢献を提示しています。

2.1 定義と不可能性の特定（CRS モデル）

CE-NIZK の定義: 共通参照文字列（CRS）モデルおよび共有 EPR モデルにおける CE-NIZK の形式定義を提案しました。
不可能性の証明: 「削除耐性（Deletion-Resistant）」と呼ばれる特定のクラスのプロトコル（証明状態を分割して検証と認証を別々に処理できるもの）が存在すれば、統計的音響性と統計的ゼロ知識を両立する NIZK が存在することになり、これは不可能であることを証明しました。既存の対話型プロトコルの非対話型一般化はこのクラスに属するため、単純な拡張では構成できないことを示しました。

2.2 CRS モデルにおける構成（LWE 仮定に基づく）

不可能性の壁を回避するため、量子状態の重ね合わせを利用した新しい構成法を提案しました。

手法:
1. 2 段階の NIZK: 内部の NIZK 証明（ $\pi_{in}$ ）と、それを BB84 状態（Wiesner 状態）とエンタングルさせた外部の NIZK 証明（ $\pi_{out}$ ）の 2 段階構造を採用します。
2. ワンタイムパッド暗号化: 内部証明 $\pi_{in}$ を、BB84 状態から導出されるパッド（Pad）でワンタイムパッド暗号化します。これにより、BB84 状態が検証可能に削除されれば、 $\pi_{in}$ の情報は理論的に消去されます。
3. OR 証明と 2 スロット技術: 外部証明では、 $ct_0$ （ $\pi_{in}$ を含む）と $ct_1$ （ダミーまたはシミュレートされた証明を含む）のどちらかが真であることを示す「OR 証明」を使用します。これにより、証明のビットをシミュレートされた値に置き換える際に、ゼロ知識性が保たれるようにします。
4. 量子安全な NIZK: 基底情報 $\theta$ を隠すために、量子安全な適応的ゼロ知識性を持つ NIZK（LWE 仮定に基づく [WWW25] のような構成）を使用します。
結果: 学習誤差問題（LWE）の多項式困難性を仮定することで、CRS モデルにおいて統計的音響性、計算量的ゼロ知識、および認証付き永続的ゼロ知識を満たす CE-NIZK を構成することに成功しました。

2.3 共有 EPR モデルにおける効率的構成

不可能性の壁が適用されない別の設定として、共有 EPR モデル（証明者と検証者が事前に EPR 対を共有している）を提案しました。

手法:
- 隠しビット（Hidden-Bits）パラダイム: 隠しビット生成器（HBG）と、隠しビットモデルにおける統計的 NIZK を組み合わせます。
- EPR 対の利用: 証明者と検証者が EPR 対の半分を共有し、共通の基底 $\theta$ で測定することで「隠しビット」を生成します。
- 削除メカニズム: 検証者は、開示されていない隠しビットに対応する EPR 対をハダマード基底で測定（削除）し、その結果を証明者に送り返します。これにより、計算量的仮定が破れても、BB84 状態の削除定理により情報が消去されることが保証されます。
結果: 統計的結合性を持つ HBG（LWE から構成可能）を仮定することで、CE-NIZK を構成しました。
効率性: このプロトコルは、EPR 対の単一量子ビット測定と古典計算のみで動作し、CRS モデルの構成に比べて量子リソースの消費が極めて少ないことが特徴です。

3. 技術的詳細とキーポイント

3.1 CRS モデル構成の核心

BB84 状態の削除定理: Bartusek と Khurana [BK23] の結果を応用し、BB84 状態が検証可能に削除されれば、暗号化された平文（NIZK 証明）は情報理論的に隠蔽されることを利用しています。
量子安全なゼロ知識: 外部証明のシミュレーションにおいて、通常の計算量的ゼロ知識では不十分であり、「量子安全な適応的ゼロ知識（Quantum-Secure Adaptive ZK）」が必要です。これは、証明者が重ね合わせ状態のクエリに対してゼロ知識性を保つことを要求します。
統計的 CRS 識別不可能性: 模擬器が生成する CRS が実世界の CRS と統計的に区別できないことが必要であり、LWE ベースの HBG 型 NIZK がこの要件を満たします。

3.2 共有 EPR モデルの利点

不可能性の回避: CRS モデルでは証明者が証明状態を完全に制御できるため「分割攻撃」が可能ですが、EPR モデルでは検証者が EPR 対の半分を保持しているため、証明者が証明状態を完全に分割することができず、不可能性の証明が適用されません。
シンプルさ: 複雑な量子状態の生成や操作ではなく、EPR 対の測定と古典的な暗号プリミティブ（HBG）のみで構成されるため、実装のハードルが低いです。

4. 意義と将来展望

4.1 学術的意義

量子暗号の新たなパラダイム: 「認証付き永続的セキュリティ」の概念を非対話型証明に初めて適用し、統計的音響性と永続的ゼロ知識を両立させる構成を示しました。
不可能性の克服: 既存の手法では不可能とされていた課題に対し、量子重ね合わせや共有エンタングルメントを活用することで解決策を提示しました。
仮定の最適化: 構成が LWE 仮定（ポスト量子暗号の標準仮定）に基づいているため、実用的なセキュリティ保証が期待されます。

4.2 実用的意義

長期セキュリティ: 将来の量子コンピュータや計算能力の向上によって現在の暗号が破られた場合でも、証明が適切に削除されれば、秘密情報が漏洩しないことを保証できます。これは機密性の高いデータや長期的な認証が必要なシステムに極めて重要です。
リソース効率: 共有 EPR モデルの構成は、量子ハードウェアの発展初期段階でも実装可能なレベルの量子操作（単一量子ビット測定）で済むため、現実的な応用への道筋を示しています。

4.3 今後の課題（Open Questions）

論文では以下の課題が提起されています：

公開検証可能な削除: 現在の構成は非公開（証明者だけが削除を検証できる）ですが、第三者が検証できる「公開検証可能な削除」の実現。
古典的証明書: 検証者が量子状態ではなく、古典的な証明書のみを送信して削除を検証できる構成。
平文モデルでの NIWI: 共通参照文字列なし（Plain Model）での認証付き永続的 NIWI（非対話型ウィットネス識別可能証明）の構成。
QMA への拡張: NP だけでなく、量子言語（QMA）に対する CE-NIZK の構成。

結論

本論文は、量子リソースを活用することで、従来の計算量的仮定に依存しない「永続的ゼロ知識」を非対話型証明で実現する画期的な成果です。CRS モデルでは高度な量子技術（重ね合わせ証明）を用いた構成を、共有 EPR モデルでは軽量な量子操作を用いた効率的な構成をそれぞれ提案し、LWE 仮定に基づいてその安全性を証明しました。これは、ポスト量子時代におけるプライバシー保護と長期セキュリティの新たな基盤となる重要な研究です。