技術概要：検証可能かつ共謀耐性を備えたマルチパーティ量子プライベート集合演算

1. 問題提起

プライベート集合演算（PSO）は、プライベート集合積（PSI）やプライベート集合和（PSU）を含み、セキュアなマルチパーティ計算（SMC）の基本となるものである。古典的な暗号学的解決策は存在するが、量子アルゴリズム（例：ショアのアルゴリズム）の出現により、現在の数論的スキームは脅威にさらされている。その結果、研究の焦点は量子PSI（QPSI）へと移行している。

しかし、既存の量子PSO（QPSO）プロトコルには重大な制限がある：

• 脅威モデル： 既存の多くのQPSIスキームは、準半誠実（semi-honest）な信頼できる第三者（TP）を想定しているか、あるいはTPがどの参加者とも共謀できないという仮定に依存している。
• 共謀耐性： 従来のマルチパーティQPSI（MP-QPSI）プロトコルは、TPと一部の参加者の間の共謀に対して耐性を持たないことが多い、あるいは単一の参加者の破損のみを許容する。
• 検証可能性： 多くのスキームは、TPが規定された量子回路を正しく実行したことを検証するメカニズムを欠いており、悪意のある逸脱に対してシステムを脆弱にしている。

2. 手法

著者らは、**検証可能な量子完全準同型暗号（vQFHE）と閾値完全準同型暗号（TFHE）**を統合した、マルチパーティ・プライベート集合積（MP-QPSI）プロトコルを提案している。このプロトコルは、$n$ 個のデータ保持参加者、強力な量子TP、および信頼できる機関（TA）を含むモデルで動作する。

コアコンポーネント

1. 閾値鍵管理（TFHE）：

   • 復号のための秘密鍵は、$(t, n)$ 閾値秘密分散スキームを用いて $n$ 個の参加者の間で共有される。
   • 復号には、少なくとも $t$ 人の参加者の協力が必要である。これにより、破損した参加者のサブセット、またはTPと $t$ 人未満の参加者の間の共謀のいずれにおいても、秘密鍵の復元やプライベートな入力の漏洩を防ぐことができる。

2. 検証可能な量子評価（vQFHE）：

   • プロトコルは、vQFHEレイヤーとして TrapTP 構成（[ADS+17]より）を利用する。
   • 暗号化： 参加者は、CSSコードを用いてプライベートな集合を量子状態にエンコードし、トラップ量子ビット（$|0\rangle$ および $|+\rangle$）を付加し、ランダムな置換を適用した後、量子ワンタイムパッド（QOTP）で結果をマスクする。QOTPの鍵はTFHEの下で暗号化され、メッセージ認証コード（MAC）によって認証される。
   • 評価： TPは、暗号化された量子状態に対して、マルチパーティAND回路（$C_{\text{AND}}$）の準同型評価を実行する。TPは、ガーデンホースモデルに従って、非クリフォード（T）ゲートを処理するために「ガジェット」（マジックステート）を消費しながら、暗号化されたQOTP鍵を準同型的に更新する。
   • 検証： TPは、評価の古典的なトランスクリプト（ログ）を生成する。参加者およびTAは、TPが目標とする回路から逸脱していないことを確認するために、MAC、ゲート配列、およびトラップコードの測定値に対してログを検証する。

3. プロトコルの流れ：

   • フェーズ1（準備）： TAが鍵を生成し、置換をサンプリングし、Tゲートガジェットを準備し、秘密のシェアを配布する。
   • フェーズ2（暗号化）： 参加者は集合を量子状態にエンコードし、トラップとQOTPを適用し、暗号化された状態と鍵をTPに送信する。
   • フェーズ3（評価）： TPは、鍵を更新し、トランスクリプトを記録しながら、$C_{\text{AND}}$ 回路を準同型的に実行する。
   • フェーズ4（検証と復号）： 参加者は、古典的な検証（MAC、ゲート、およびトランスクリプトのチェック）と閾値復号を行い、QOTP鍵を復元する。TAは、量子的な検証（トラップチェック）を行い、最終的な状態を復号して積集合の結果をブロードキャストする。

3. 主な貢献

• マルチパーティへの拡張： 著者らは、TFHEと組み合わせることでvQFHEをマルチパーティ設定に拡張し、プライベートなデータを明かすことなく $n$ 個のパーティが集合積を計算できるようにした。
• 共謀耐性： 従来のQPSIスキームとは異なり、本プロトコルはTPと最大 $t-1$ 人の参加者の間の共謀に耐性を持つ。閾値メカニズムにより、破損したパーティが $t$ 未満である限り、秘密鍵とプライベートな入力は安全に保たれる。
• 悪意のあるTPに対する検証可能性： 本プロトコルは、意味論的セキュリティと検証可能性を提供する。古典的なトランスクリプト検証と量子トラップコードチェックの組み合わせにより、TPが規定された回路から逸脱（例：ゲート配列や出力を変更する）した場合、それを検出できる。
• モジュール式フレームワーク： この構成はモジュール式フレームワークとして提示されている。著者らは、以下を実現する方法を示している：
  • 回路複雑度の低減（例：Tゲート数を減らすために $C_nX$ の代わりに $CCCZ$ ゲートを使用する）。
  • オープン制御操作を介してAND回路をOR回路に置き換えることによる、量子プライベート集合和（QPSU）への機能拡張。
  • 異なる効率性/セキュリティのトレードオフに合わせて、基礎となるvQFHEの実装を入れ替えること。

4. 結果と分析

• 正当性： 著者らは、IBM Quantum PlatformおよびQiskitを用いて、論理的なマルチパーティANDゲートを検証した。シミュレーションにより、出力分布が論理AND演算の理想的な真理値表と一致することが確認された。
• セキュリティ証明：
  • プライバシー： プロトコルは、量子状態に関しては（QOTPと最大混合状態により）情報理論的に安全であり、古典的なデータに関しては（TFHEとMACにより）計算量的に安全であることが証明されている。
  • 共謀： 定理3は、TPと共謀する破損した参加者の連合（サイズ $<t$）が、積集合の結果以上の情報を得ることができないことを証明している。
  • 検証可能性： 意味論的セキュリティモデル（$\kappa\text{-SEM-VER}$）の下で、プロトコルは検証可能であることが示されている。ハイブリッド引数により、TPによるいかなる逸脱も、圧倒的な確率で検出されることが示されている。
• パフォーマンス：
  • 通信複雑度： 量子通信コストは $O(n\kappa L)$ である（ここで $n$ はパーティ数、$\kappa$ はセキュリティパラメータ、$L$ は集合サイズ）。
  • 比較： 既存のスキーム（例：[SMZ+15], [ZLS+20], [HZZ24]）と比較して、提案されたプロトコルは、PSIおよびPSUの両方の機能を持ち、かつTP-参加者間の共謀および悪意のあるTPの挙動に対する耐性を提供する唯一のマルチパーティ・シナリオをサポートしている。

5. 重要性と主張

本論文は、既存のQPSIソリューションを悩ませている「TP-参加者間の共謀」のギャップに対処することで、量子セキュア計算の分野における重要な進展を提供すると主張している。

• 堅牢性： TFHEを統合することにより、本プロトコルは、従来の量子PSIには存在しなかったレベルの共謀耐性を達成しており、TPと一部の参加者が結託した場合でもセキュリティを確保している。
• 信頼の最小化： 検証可能性レイヤーにより、システムはTPが（計算能力としては強力であっても）誠実であるという信頼を必要とせずに、安全に機能することができる。
• 柔軟性： モジュール設計により、このフレームワークを異なる集合演算（和、カーディナリティ）に適応させたり、異なるハードウェア制約（例：Tゲートの複雑度の低減）に合わせて最適化したりすることが可能である。

著者らは、本プロトコルが強力なセキュリティを提供する一方で、TrapTPベースのvQFHEに関連する古典的なオーバーヘッドを継承していることを認めている。今後の課題として、ガジェットフリーのT処理の探索や、古典的な通信コストを削減するためのさらなる最適化が示唆されている。