論文の概要: The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems

• arxiv url: http://arxiv.org/abs/2602.16700v1
• Date: Wed, 18 Feb 2026 18:46:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-19 15:58:30.690891
• Title: The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems
• Title（参考訳）: グラフベースレプリケーションシステムにおける対称PIRにおける共通乱数複製の役割
• Authors: Shreya Meel, Sennur Ulukus,
• Abstract要約: グラフ関連データベースシステムにおけるSPIRの問題点について検討する。 各メッセージは、正確に2つのサーバで複製される。 キャパシティを実現するのに必要な共通乱数最小量を定量化する。
• 参考スコア（独自算出の注目度）: 43.914623898157856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In symmetric private information retrieval (SPIR), a user communicates with multiple servers to retrieve from them a message in a database, while not revealing the message index to any individual server (user privacy), and learning no additional information about the database (database privacy). We study the problem of SPIR on graph-replicated database systems, where each node of the graph represents a server and each link represents a message. Each message is replicated at exactly two servers; those at which the link representing the message is incident. To ensure database privacy, the servers share a set of common randomness, independent of the database and the user's desired message index. We study two cases of common randomness distribution to the servers: i) graph-replicated common randomness, and ii) fully-replicated common randomness. Given a graph-replicated database system, in i), we assign one randomness variable independently to every pair of servers sharing a message, while in ii), we assign an identical set of randomness variable to all servers, irrespective of the underlying graph. In both settings, our goal is to characterize the SPIR capacity, i.e., the maximum number of desired message symbols retrieved per downloaded symbol, and quantify the minimum amount of common randomness required to achieve the capacity. To this goal, in setting i), we derive a general lower bound on the SPIR capacity, and show it to be tight for path and regular graphs through a matching converse. Moreover, we establish that the minimum size of common randomness required for SPIR is equal to the message size. In setting ii), the SPIR capacity improves over the first, more restrictive setting. We show this through capacity lower bounds for a class of graphs, by constructing SPIR schemes from PIR schemes.
• Abstract（参考訳）: 対称プライベート情報検索(SPIR)では、ユーザは複数のサーバと通信してデータベース内のメッセージを取得するが、個々のサーバ(ユーザのプライバシ)にメッセージインデックスを公開せず、データベースに関する追加情報(データベースプライバシ)を学習しない。 本研究では,各ノードがサーバであり,各リンクがメッセージであるグラフ複製データベースシステムにおけるSPIRの問題について検討する。 各メッセージは、正確に2つのサーバで複製される。 データベースのプライバシを確保するため、サーバはデータベースとユーザの希望するメッセージインデックスとは独立して、一連の共通ランダム性を共有する。 サーバに対する共通乱数分布の2例について検討する。 一 グラフ関連共通無作為性及び ii) 完全複製された共通ランダム性。 グラフレプリケートデータベースシステム、in i) メッセージを共有するすべてのサーバに独立して1つのランダム性変数を割り当てる。 i) 基礎となるグラフに関係なく、すべてのサーバに同じランダム性変数のセットを割り当てる。 どちらの設定でも、SPIRのキャパシティ、すなわちダウンロードされたシンボルごとに検索される所望のメッセージシンボルの最大数を特徴付け、そのキャパシティを達成するのに必要な共通乱数最小量を定量化する。 この目的のために、設定する i)SPIR容量の一般下界を導出し、一致する逆を通して経路グラフと正則グラフに対して厳密であることを示す。 さらに,SPIRに必要な共通乱数最小サイズがメッセージサイズに等しいことを示す。 設定 ii) SPIR容量は、最初のより制限的な設定よりも改善される。 PIRスキームからSPIRスキームを構築することにより、グラフのクラスに対するキャパシティ・ローバウンドを通してこれを示す。

関連論文リスト

• Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
  データベースの複製を単純なグラフでモデル化した環境で、対称なプライベート情報検索の問題を再考する。 メッセージとは独立して、すべてのサーバに共通するランダム性を共有させます。 所望シンボル数とダウンロードシンボル数の最大比であるSPIR容量の改善を定量化する。
  論文  参考訳（メタデータ） (2025-10-29T17:40:40Z)
• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [43.914623898157856]
  単純なグラフでモデル化された複製されたデータベース上の対称プライベート情報検索。 本研究では,SPIRを実現するのに必要なサーバ側の共通乱数性も,そのグラフに従ってサーバに複製されるような設定について考察する。
  論文  参考訳（メタデータ） (2025-07-23T17:51:08Z)
• Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
  多重グラフを用いた複製システムにおけるプライベート情報検索問題について考察する。 我々の目標は、$r$-multigraphのPIR容量の上下境界を確立することです。
  論文  参考訳（メタデータ） (2025-01-29T18:48:22Z)
• Privatized Graph Federated Learning [57.14673504239551]
  グラフによって連結された複数の単位からなるグラフフェデレーション学習を導入する。 グラフ準同型摂動はアルゴリズムが微分プライベートであることを保証するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2022-03-14T13:48:23Z)
• Jointly Cross- and Self-Modal Graph Attention Network for Query-Based Moment Localization [77.21951145754065]
  本稿では,共同グラフを渡る反復的メッセージのプロセスとして,このタスクをリキャストするクロスモーダルグラフ注意ネットワーク(CSMGAN)を提案する。 CSMGANは2つのモード間の高次相互作用を効果的に捉えることができ、より正確な局所化を可能にします。
  論文  参考訳（メタデータ） (2020-08-04T08:25:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。