論文の概要: Local Private Information Retrieval for Graph-Based Replicated Systems

• arxiv url: http://arxiv.org/abs/2608.31150v1
• Date: Mon, 31 Aug 2026 17:50:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-01 18:31:31.545596
• Title: Local Private Information Retrieval for Graph-Based Replicated Systems
• Title（参考訳）: グラフベースレプリケーションシステムのためのローカルプライベート情報検索
• Abstract要約: マルチサーバ,グラフ対応のプライベート情報検索(PIR)システムにおけるプライバシの定義を再考する。 提案したプライバシ設定では,ユーザは特定のサーバからメッセージインデックスを隠蔽することに関心がある。 この緩和されたプライバシ要件を,ローカルユーザのプライバシと結果のPIR問題をグラフ上のローカルPIRとして生成する。
• 参考スコア（独自算出の注目度）: 39.20087907351314
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems, by introducing a novel setting where the user's privacy is governed by the servers' storage structure. In classical graph-replicated PIR, the user retrieves a single message stored at the servers, while hiding the message index from each server. In our proposed privacy setting, the user is concerned with hiding the message index from a particular server, only if that server stores the message being retrieved, and privacy is not imposed otherwise. We coin this relaxed privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph. Our focus is on two-replicated PIR systems, where every message is replicated twice and stored on two distinct servers. Specifically, we study local PIR systems where the storage is represented by simple graphs, i.e., every pair of vertices is associated with at most one edge, and by their multigraph extension, i.e., $r$ parallel edges replace every edge. For these settings, we establish bounds on the local PIR capacity, defined as the maximum number of message symbols retrieved, per downloaded symbol. The local privacy requirement yields significant capacity gain over the classical PIR capacity under the same storage structure. For instance, in settings where the graph is a disjoint union of multiple identical sub-graphs, the gain in the local PIR capacity over classical PIR capacity is multiplicative in the number of sub-graphs. Further, for connected graphs, we derive capacity lower bounds for edge-transitive and bipartite graphs, which are greater than the best-known PIR capacity bounds. From these and by establishing matching upper bounds, we exactly characterize the capacity for star graphs, cyclic graphs, and path graphs with odd number of vertices. We introduce two local PIR schemes for general graphs.
• Abstract（参考訳）: 我々は,ユーザのプライバシがサーバのストレージ構造によって管理される新しい設定を導入することで,マルチサーバ,グラフレプリケーションされたプライベート情報検索(PIR)システムにおけるプライバシの定義を再考する。 古典的なグラフ複製PIRでは、ユーザーは各サーバからメッセージインデックスを隠しながら、サーバに格納された1つのメッセージを取得する。 提案したプライバシ設定では,サーバが検索したメッセージを保存する場合にのみ,特定のサーバからメッセージインデックスを隠蔽することに関心があり,それ以外はプライバシを課さない。 この緩和されたプライバシ要件を,ローカルユーザのプライバシと結果のPIR問題をグラフ上のローカルPIRとして生成する。 各メッセージは2回複製され、2つの異なるサーバに格納される。 具体的には、ストレージが単純なグラフで表されるローカルPIRシステム、すなわち、各頂点のペアが少なくとも1つのエッジに関連付けられており、それらのマルチグラフ拡張によって、すなわち$r$並列エッジがすべてのエッジを置き換える。 これらの設定のために、我々は、ダウンロードされたシンボルごとに、検索されたメッセージシンボルの最大数として定義されるローカルPIR容量のバウンダリを確立する。 ローカルなプライバシ要件は、同じストレージ構造の下での古典的なPIR容量よりも大きなキャパシティ向上をもたらす。 例えば、グラフが複数の同一のサブグラフの非連結結合である場合、古典的なPIR容量に対する局所的なPIR容量のゲインは、サブグラフの数に乗じる。 さらに、連結グラフに対しては、最もよく知られたPIRキャパシティ境界よりも大きいエッジ遷移グラフと二部グラフのキャパシティローバウンドを導出する。 これらから、一致する上界を確立することにより、奇数の頂点を持つ星グラフ、巡回グラフ、および経路グラフの容量を正確に特徴づける。 一般グラフに対する2つの局所的PIRスキームを導入する。

関連論文リスト

• Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results [39.20087907351314]
  グラフベースのストレージシステムにおいて、任意のプライバシ要件の下でプライベート情報検索(PIR)の問題を導入する。 この定式化は、サーバーストレージの制限、大量のデータ(メッセージ)、および不均一なデータプライバシ要件によって動機付けられている。 我々は、特定のプライバシー要件の下で、一般的なグラフに対するPIR容量の一般的な下限と上限を導出する。
  論文  参考訳（メタデータ） (2026-09-14T17:03:36Z)
• Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems [39.20087907351314]
  本稿では,ユーザのプライバシがサーバのストレージ構造によって管理される,新たな環境を提案する。 特に、サーバからメッセージを取得する一方で、ユーザは、サーバから所望のメッセージインデックスを隠すことに関心があります。 このプライバシ要件を,ローカルユーザのプライバシと結果のPIR問題を,グラフ上のローカルPIRとして定義する。
  論文  参考訳（メタデータ） (2026-05-11T17:25:10Z)
• The Role of Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
  グラフ関連データベースシステムにおけるSPIRの問題点について検討する。 各メッセージは、正確に2つのサーバで複製される。 キャパシティを実現するのに必要な共通乱数最小量を定量化する。
  論文  参考訳（メタデータ） (2026-02-18T18:46:58Z)
• 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)
• Align-GRAG: Reasoning-Guided Dual Alignment for Graph Retrieval-Augmented Generation [79.75818239774952]
  大きな言語モデル(LLM)は目覚ましい能力を示しているが、幻覚や時代遅れの情報といった問題に苦戦している。 Retrieval-augmented Generation (RAG) は、情報検索システム(IR)を用いて、外部知識のLLM出力を基底にすることで、これらの問題に対処する。 本稿では、検索後句における新しい推論誘導二重アライメントフレームワークであるAlign-GRAGを提案する。
  論文  参考訳（メタデータ） (2025-05-22T05:15:27Z)
• 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)

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

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