最大共謀攻撃に耐える効率的な多者間プライベート集合和

秘密を明かさずにブラックリストを共有する意義

多くの組織は、背後にある機密情報を晒さずにデータを協調させる必要があります。疑わしい口座のブラックリストを共同で集めたい銀行や、顧客情報や内部手法を秘匿したまま不正検知指標を結合したい企業を想像してください。本稿は、複数の当事者が各自の非公開リストの和集合（少なくとも一つのリストに現れるすべての要素）を計算し、参加者は最終的な結合リストだけを知り、それ以外の互いのデータについては何も学ばないようにする方法を探ります。焦点は、共謀に対して極めて強固でありながら、非常に大きなデータセットでも効率的に動作する協調手法の実現です。

多数の非公開リストの結合

ここで扱う課題は多者間プライベート集合和と呼ばれます。各参加者は口座番号や識別子などの機密アイテム集合を保持しており、全当事者のアイテムの和集合を知りたいと考えます。誰もどの当事者がどのアイテムを提供したかを学んではならず、最終和集合に含まれないアイテムを見てはなりません。既存の手法は、重い公開鍵暗号に依存するか、一般的な安全計算フレームワークを用いるため、集合の要素が数百万に達したり参加者が多数いると実用的でなくなります。Gaoらによる最近のプロトコルはスケーラビリティを改善し、「最大共謀」に耐え得る---つまり参加者の全員が一人を除いて秘密裏に協力しても安全性を維持する---点で優れていましたが、それでも非常に大容量の暗号化メッセージを送受信する必要がありました。

賢い手法の組合せで通信量を削減

著者らは、Gaoらの強い共謀耐性を保持しつつ通信量を大幅に削減し、実行時間を短縮する新しいプロトコルを提案します。主な着想は、公開鍵暗号のような高コストな暗号化を、後で共同復号が必要な重大な部分だけに限定し、中間データの大部分には軽量で高速な共通鍵暗号を使うことです。彼らは二段階の「ワンリーダー」プロトコルを設計し、すべての当事者が自分の集合に基づくハッシュ化データ構造を準備し、その後相互作用して最終的に指定されたリーダーだけが和集合を得る仕組みです。中心的な構成要素であるバッチ等価性検査付き盲目乱数生成は、二者が隠されたアイテムが等しいときに一致するランダムマスクを生成できるようにし、どのアイテムが一致したかを明かさずに済みます。これにより、プロトコル中の情報フローにおける重複の効率的でプライバシー保護されたフィルタリングが可能になります。

単一リーダーからより公平な共有結果へ

協調の場面によっては、結果を単独で受け取るリーダーが一人いることがリスクや政治的に受け入れがたい場合があります。そこで著者らは、各参加者が直接和集合を得られる「リーダーレス」版へと設計を拡張します。同じ準備作業を維持しつつ、相互作用フェーズを複数回繰り返し、各実行でリーダー役を順番に回します。各ラウンドは異なる参加者向けに和集合を生成し、共同復号とシャッフルを用いて誰もアイテムの起源を辿れないようにします。このリーダーレス設計は、単一の当事者が結果を差し止めたりボトルネックになることを防ぎ、堅牢性と公平性を改善しますが、通信量は概ね参加者数倍に増えるというコストを伴います。

実世界でのプロトコルのスケーリング

研究チームはプロトコルを実装し、さまざまな集合サイズと参加者数の下で最良の既存方式と比較しました。公開鍵部品はしきい値型ElGamal暗号で実装し、ハッシュ、等価性検査、基本的暗号プリミティブには既存ライブラリを組み込みます。現実的なパラメータ選択の範囲で、ワンリーダープロトコルは通信量を概ね4〜5倍削減し、実行時間は参加者数とアイテム数に応じて約1.3〜1.8倍高速化しました。リーダーレスプロトコルは当然ながらより多くの帯域を使いますが、同じ設計上の効率性の恩恵を受け続け、復号ステップを重ね合わせて処理できるため総実行時間の増加は通信コストほど急激ではありません。

プライバシー保護型協調の意義

専門外の読者にとっての要点は、本研究が多くの独立組織にとって、ほとんど全員が共謀したとしても生のデータを明かすことなく機密リストを結合する実用性を高めたことです。重厚な暗号を使うべき場面と軽量手段で十分な場面を慎重に選ぶことで、著者らは帯域を大幅に節約しつつ強力な安全性を維持するプロトコルを提示しています。さらにリーダーレス版は結果配布の単一障害点依存を排除します。これらの進展により、プライバシー保護されたデータ和集合は理論上の演習から、金融、サイバーセキュリティ、データ分析などの分野で導入可能な実用ツールへと近づきます。

引用: Liu, Q., Lee, JW. Efficient multi-party private set union resistant to maximum collusion attacks. Sci Rep 16, 13230 (2026). https://doi.org/10.1038/s41598-026-41069-2

キーワード: プライベート集合和, 安全なデータ協調, 多者計算, プライバシー保護暗号化, 共謀耐性プロトコル