論文の概要: Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems
- arxiv url: http://arxiv.org/abs/2605.10872v1
- Date: Mon, 11 May 2026 17:25:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-12 23:28:51.027427
- Title: Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems
- Title（参考訳）: ローカルプライベート情報検索:グラフベースのレプリケーションシステムのための新しいプライバシ視点
- Authors: Shreya Meel, Mohamed Nomeir, Sennur Ulukus,
- Abstract要約: 本稿では,ユーザのプライバシがサーバのストレージ構造によって管理される,新たな環境を提案する。
特に、サーバからメッセージを取得する一方で、ユーザは、サーバから所望のメッセージインデックスを隠すことに関心があります。
このプライバシ要件を,ローカルユーザのプライバシと結果の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, and introduce a novel setting where the user's privacy is governed by the servers' storage structure. In particular, while retrieving a message from a server, the user is concerned with hiding their desired message index from the server, only if the server stores the corresponding message. We coin this privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph. Our goal is to measure the gain in communication efficiency of local PIR, compared to that of canonical PIR, by establishing its capacity, i.e., the maximum number of message symbols retrieved, per downloaded symbol. To this end, we observe a remarkable gain in the local PIR capacity of graphs, that are disjoint union of distinct graphs, which is multiplicative, compared to the PIR capacity, when the individual graphs are identical. For connected graphs, we propose schemes to establish capacity lower bounds for edge-transitive and bipartite graphs, which are greater than the best-known PIR capacity bounds. Finally, we derive the exact local PIR capacity for the cyclic graph, and the path graph with an odd number of vertices.
- Abstract（参考訳）: 我々は、マルチサーバにおけるプライバシの定義を再考し、グラフレプリケーションされたプライベート情報検索(PIR)システムを導入し、ユーザのプライバシがサーバのストレージ構造によって管理される新しい設定を導入する。
特に、サーバからメッセージを検索している間、サーバが対応するメッセージを格納している場合に限り、ユーザはサーバから所望のメッセージインデックスを隠すことに関心がある。
このプライバシ要件を,ローカルユーザのプライバシと結果のPIR問題を,グラフ上のローカルPIRとして定義する。
我々のゴールは、その容量、すなわちダウンロードされたシンボルあたりのメッセージシンボルの最大数を確立することで、標準PIRと比較して、ローカルPIRの通信効率の上昇を測定することである。
この目的のために、グラフの局所的なPIR容量の顕著な増加は、個々のグラフが同一であるときのPIR容量と比較して乗法的に異なるグラフの解離結合である。
連結グラフに対しては、最もよく知られたPIRキャパシティ境界よりも大きいエッジ遷移グラフと二部グラフのキャパシティローバウンドを確立するスキームを提案する。
最後に、巡回グラフの正確な局所的PIR容量と、奇数の頂点を持つ経路グラフを導出する。
関連論文リスト
- 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) - New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage [39.51026717015587]
グラフベースおよびマルチグラフベースの複製システムにおけるプライベート情報検索(PIR)の問題について検討する。
このような系に対するPIR容量の上限を導出し、これらの境界に近づくPIRスキームを構築する。
論文 参考訳（メタデータ） (2025-04-29T16:05:42Z) - Communication-Efficient Graph Neural Networks with Probabilistic
Neighborhood Expansion Analysis and Caching [59.8522166385372]
大規模グラフ上でのグラフニューラルネットワーク(GNN)のトレーニングと推論は、GNNの登場以来活発に研究されている。
本稿では,分散環境におけるノードワイドサンプリングを用いたGNNによるミニバッチ学習と推論について述べる。
分割された特徴データを扱うために,従来のSALIENTシステムを拡張したSALIENT++を提案する。
論文 参考訳（メタデータ） (2023-05-04T21:04:01Z) - Privatized Graph Federated Learning [57.14673504239551]
グラフによって連結された複数の単位からなるグラフフェデレーション学習を導入する。
グラフ準同型摂動はアルゴリズムが微分プライベートであることを保証するためにどのように使用できるかを示す。
論文 参考訳（メタデータ） (2022-03-14T13:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。